Метод lu-разложения

Можно показать, что применение метода Гаусса эквивалентно LU-разложению матрицы А, т.е. ее представлению в виде произведения , где

.

Элементы этих матриц находятся по формулам в том порядке, в котором здесь эти формулы выписаны:

,

Такое разложение дает следующий результат:

. Положим , тогда. Получили треугольную систему уравнений

Из этой системы последовательно находим ,. Знаяy, находим x из треугольной системы

Откуда ,.

И в методе Гаусса при решении систем линейных уравнений, и в LU-разложении матрицы приходится выполнять деление на элемент матрицы. Если этот элемент нуль, то процесс остановится, хотя матрица А не вырождена, и решение системы существует. Проблемы возникают и в том случае, когда элемент, на который приходится делить, очень маленький. В этой ситуации предыдущие ошибки, возникающие неизбежно при округлении чисел компьютером, резко увеличиваются и могут стать недопустимо большими. Если действия выполняются на бумаге, то вы просто меняете строки матрицы местами. Аналогично поступают и при программировании метода Гаусса и LU-разложения. При этом обычно выбирают такую строку, где элемент, на который нужно делить, является наибольшим по модулю.

При таком алгоритме при LU-разложении уже получается три матрицы P, L, U. Матрицы L, U – нижняя и верхняя треугольные соответственно, ,,P – матрица перестановок, т.е. квадратная матрица порядка n, в каждой строке и в каждом столбце которой только один элемент равен 1, а все остальные элементы – нули. Эти матрицы связаны соотношением . Такое разложение всегда возможно, если.

Если мы получим такое разложение, то для решения системы обе части умножим слева на матрицуP, , и заменимPA на LU, . Далее действия такие же, как описано выше. ИменноLU-разложение используется в системе MATHCAD для решения систем линейных уравнений.