 |
Классы задач линейной алгебры
|
|
|
|
При численном решении большого круга задач в конечном итоге происходит их линеаризация, в связи с чем в соответствующих алгоритмах весьма широко используются методы линейной алгебры. В их числе:
- решение систем линейных алгебраических уравнений (СЛАУ);
- вычисление определителей матриц
; - нахождение обратных матриц
; - определение собственных значений и собственных векторов матриц
;
Постановка задачи решения СЛАУ: 
, (1) где 
– квадратная матрица коэффициентов размерности n, 
– вектор неизвестных, 
– вектор свободных коэффициентов. Иногда СЛАУ представляют в виде расширенной матрицы размерности n × n +1, где в качестве последнего столбца фигурирует вектор свободных коэффициентов. В координатном представлении такая СЛАУ выглядит следующим образом:
. (2)
Для решения СЛАУ применяют в основном два класса методов: прямые (выполняемые за заранее известное количество действий) и итерационные (обеспечивающие постепенную сходимость к корню уравнения, зависящую от многих факторов). Прямые методы обычно применяются для решения систем порядка n < 200, для бóльших n используются итерационные методы. Перед решением СЛАУ требуется проанализировать корректную постановку задачи:
1) Если 
– решение существует и единственно. Если же определитель равен нулю, то тогда, если матрица вырождена (т.е. ее можно преобразовать к виду, когда как минимум одна строка коэффициентов – нули) решений бесконечное множество, иначе решения не существует.
2) Если не имеет элементов с большими по модулю значениями – решение устойчиво (см. пример к главе 1). Показателем плохо обусловленных систем является 
.
Алгоритм метода Гаусса
|
|
|
1) Прямой ход.
Идея метода состоит в последовательном исключении неизвестных из системы n линейных уравнений. На примере первого уравнения системы (2) рассмотрим выражение для x 1:
.
Подставим выражение для x 1 во второе и все остальные уравнения системы:
.
Для расширенной матрицы коэффициентов это означает, что каждый элемент первой строки следует поделить на диагональный элемент, а все остальные строки преобразовать, как показано выше. Таким образом, станут равны нулю все коэффициенты первого столбца, лежащие ниже главной диагонали. Затем аналогичная процедура проводится со второй строкой матрицы и нижележащими строками, при этом первая строка и первый столбец уже не изменяются. И так далее до тех пор, пока все коэффициенты, лежащие ниже главной диагонали, не будут равны нулю.
Общие формулы прямого хода:
, (3)
k = 1… n, j = 1… n +1. Звездочкой отмечены элементы k -й строки с измененными значениями, которые будут подставлены в следующую формулу. Для определенности будем считать первый индекс – по строкам, второй – по столбцам.
, (4)
i = k +1… n, j = 1… n +1, k фиксировано в уравнении (3). Для уменьшения количества действий достаточно изменять значения элементов, находящихся выше главной диагонали.
2) Обратный ход.
Второй этап решения СЛАУ методом Гаусса называется обратным ходом и состоит в последовательном определении x k, начиная с x n, так как для последнего решение фактически получено. Общая формула:
. (5)
Таким образом, вычисление корней происходит за 2/3 n 3 арифметических действий.
3) Выбор главного элемента.
Для уменьшения погрешности вычислений следует стремиться к тому, чтобы на главной диагонали матрицы стояли максимальные по модулю значения коэффициентов. Алгоритмически этого можно добиться, переставляя строки таким образом, чтобы на диагонали стоял наибольший по модулю элемент текущего столбца. Такая процедура называется выбором главного элемента и осуществляется всякий раз при переходе к новой строке в прямом цикле метода Гаусса.
|
|
|
4) Погрешность метода. Расчет невязок.
Точность результатов будет определяться только точностью выполнения арифметических операций при преобразовании элементов матрицы, т.е. ошибкой округления. Контроль правильности полученного решения осуществляется подстановкой полученных значений x 1… x n в исходную систему уравнений и вычислением невязок, т.е. разностей между правыми и левыми частями уравнений:
, где k = 1… n. (6)
Специально отметим, что подставлять найденные значения следует в исходную (не преобразованную к верхнетреугольному виду) систему.
5) Преимущества и недостатки метода.
Преимущество метода в том, что он позволяет достичь результата за заранее известное и фиксированное число действий. Точность результатов будет определяться правильным выбором порядка коэффициентов в матрице и ее размерностью. Недостатком метода является резкое увеличение времени и погрешности вычислений с ростом n.
Блок-схема алгоритма метода Гаусса без выбора главного элемента.
|
|
|
