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


Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

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



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

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

L1c L2c… Lkc… Ln-1,c U=A,

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

 

 

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

,

где .

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

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

.

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

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

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

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

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

 

 

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

, 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.

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

 



Поделиться:


Последнее изменение этой страницы: 2017-01-19; просмотров: 298; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 54.224.70.148 (0.005 с.)