Метод Гаусса и LU — разложение

Метод Гаусса упорядоченного исключения переменных использу­ется для приведения СЛАУ к верхней треугольной форме с последую­щим решением методом обратной подстановки. Оценка общего числа необходимых операций равна (2/3) п ³, где п — число уравнений.

Метод Гаусса основан на разложении

L_1c L_2c… L_kc… L_n-1,c U=A,

где U — верхняя треугольная матрица; L_kc — нижние столбцовые элементарные матрицы, поддиагональные элементы k -го столбца ко­торых находятся на k-м шаге факторизации следующим образом:

 

 

Обращение таких матриц осуществляется заменой знаков внедиа-гональных ненулевых элементов. Умножение матрицы А слева на обращает в ноль поддиагональные элементы k -го столбца матрицы А. Приведенное выше разложение может быть получено умножением матрицы А и получающихся из нее матриц на пары . Тогда

,

где .

Таким образом, исходную СЛАУ АХ = В привели к виду

далее, последовательно умножив левую и правую части на затем на и т.д., получим систему с матрицей коэффициентов при неиз­вестных в верхней треугольной форме:

^.

Решение осуществляется по следующему алгоритму:

1) Положить А(°) = А и выполнить шаги факторизации для k = 1,2,..., п - 1 в coответствии со следующими пунктами:

а)для каждого шага определить элементы матрицы L_kc, которые записывают на место обращаемых в ноль элементов матрицы

б)выполнить вычисление значений элементов преобразованной матрицы путем умножения на матрицу, обратную к L_kc:

i=k+1, k+2,…, n; j=k+1, k+2,…, n.

 

 

в) выполнить вычисление вектора правых частей В^(k) путем
умножения на матрицу, обратную к L_kc:

, i=k+1, k+2,…, n.

 

 

2) Полученную систему решить методом обратной подстановки, учитывая, что .

3) Конец алгоритма.

С целью повышения численной устойчивости реализуют алгоритм метода Гаусса с выбором главного элемента по столбцу. Для этого пе­ред выполнением пункта 1а алгоритма необходимо найти т такое, что и переставить местами строки с номерами т и k.

Данный пункт в матричной форме соответствует использованию матриц перестановок Р_тk - Тогда факторизация принимает вид

^.

Поскольку элементы матриц L_kc в данном алгоритме записывают на место обращенных в ноль элементов матрицы А, то можно решать много СЛАУ с различными правыми частями, не выполняя повторную. Учитывая свойства элементарных нижних столбцовых матриц можно, заметить, что на месте матрицы А получено ее разложение в виде про­изведения нижней и верхней треугольных матриц:

LU = А,

где , называемого LU — разложением.

Следует иметь в виду, что в результате применения алгоритма на главной диагонали матрицы А и над ней будут записаны элементы мат­рицы U, под диагональю — элементы матрицы L, но в силу того, что диагональные элементы заняты U, то для диагональных элементов L места нет. Однако в силу свойств нижних столбцовых элементарных матриц, на диагонали L должны находиться только единицы, для их хра­нения отводить место не обязательно, достаточно просто иметь в виду, что они существуют и не забывать в расчетах.

Для получения LU —разложения необходимо опустить в приве­денном алгоритме пункты 1в, 2. Исходная система принимает вид

LUX = В

и может быть решена на основе типовых подходов. Обозначим Y = — UX, решим методом прямой подстановки систему LU = В, а затем методом обратной подстановки систему UX = Y. Получим искомый вектор X.

К недостаткам метода Гаусса можно отнести повышенную чувстви­тельность к особенностям матрицы А, невозможность его использова­ния для решения переопределенных систем, в которых число уравне­ний больше числа неизвестных.