Метод Гаусса упорядоченного исключения переменных используется для приведения СЛАУ к верхней треугольной форме с последующим решением методом обратной подстановки. Оценка общего числа необходимых операций равна (2/3)п3, где п— число уравнений.
Метод Гаусса основан на разложении
L1СL2С… LkС… Ln-1,СU=A,
где U— верхняя треугольная матрица; Lk,С— нижние столбцовые элементарные матрицы, поддиагональные элементы k-го столбца которых находятся на k-м шаге факторизации следующим образом:
Обращение таких матриц осуществляется заменой знаков внедиа-гональных ненулевых элементов. Умножение матрицы А слева на обращает в ноль поддиагональные элементы k-го столбца матрицы А. Приведенное выше разложение может быть получено умножением матрицы А и получающихся из нее матриц на пары . Тогда
,
где .
Таким образом, исходную СЛАУ АХ = В привели к виду
далее, последовательно умножив левую и правую части на затем на и т.д., получим систему с матрицей коэффициентов при неизвестных в верхней треугольной форме:
.
Решение осуществляется по следующему алгоритму:
1) Положить А(°) = А и выполнить шаги факторизации для k = 1,2,..., п - 1 в coответствии со следующими пунктами:
а)для каждого шага определить элементы матрицы LkС , которые записывают на место обращаемых в ноль элементовматрицы
б)выполнить вычисление значений элементов преобразованной матрицы путем умножения на матрицу, обратную кLkС:
| i=k+1, k+2,…, n; j=k+1, k+2,…, n. |
в) выполнить вычисление вектора правых частейВ(k) путем
умножения на матрицу, обратную кLkС:
| , i=k+1, k+2,…, n. |
2) Полученную систему решить методом обратной подстановки, учитывая, что .
3) Конец алгоритма.
С целью повышения численной устойчивости реализуют алгоритм метода Гаусса с выбором главного элемента по столбцу. Для этого перед выполнением пункта 1а алгоритма необходимо найти т такое, что и переставить местами строки с номерами т и k.
Данный пункт в матричной форме соответствует использованию матриц перестановок Ртk- Тогда факторизация принимает вид
.
Поскольку элементы матриц Lkcв данном алгоритме записывают на место обращенных в ноль элементов матрицыА, то можно решать много СЛАУ с различными правыми частями, не выполняя повторную. Учитывая свойства элементарных нижних столбцовыхматриц можно, заметить, что на месте матрицыА получено ее разложение в виде произведения нижней и верхней треугольных матриц:
LU = А,
где , называемогоLU— разложением.
Следует иметь в виду, что в результате применения алгоритма на главной диагонали матрицыАи над ней будут записаны элементы матрицы U, под диагональю — элементы матрицы L, но в силу того, что диагональные элементы заняты U, то для диагональных элементов Lместа нет. Однако в силу свойств нижних столбцовых элементарных матриц, на диагонали Lдолжны находиться только единицы, для их хранения отводить место не обязательно, достаточно просто иметь в виду, что они существуют и не забывать в расчетах.
Для получения LU—разложения необходимо опустить в приведенном алгоритме пункты 1в, 2. Исходная система принимает вид
LUX= В
и может быть решена на основе типовых подходов.Обозначим Y = — UX, решим методом прямой подстановки систему LU = В, а затем методом обратной подстановки систему UX= Y. Получим искомый вектор X.
К недостаткам метода Гаусса можно отнести повышенную чувствительность к особенностям матрицыА, невозможность его использования для решения переопределенных систем, в которых число уравнений больше числа неизвестных.