Алгоритм LU-разложения

Данный алгоритм можно рассматривать как конкретную форму метода Гаусса. Алгоритм LU -разложения используется не только для решения СЛАУ, но и также для обращения матрицы, т.е. вычисления матрицы, обратной данной.

Пусть и , (2.1)

где L и U – соответственно нижняя и верхняя треугольные матрицы вида

.

Известно, что если все угловые миноры матрицы A отличны от нуля, т.е.

то разложение вида (2.1) существует и единственно, однако на доказательстве этого факта мы останавливаться не будем. Для того чтобы получить расчётные формулы, поступим следующим образом. Обозначим как произведение i -й строки матрицы L на j -й столбец матрицы U, причём будем считать в начале, что .

Тогда .

Выразим из последней формулы .

. (2.2)

Как это принято, будем считать в формуле (2.2) и далее, что сумма вида равна нулю, если значение верхней границы индекса суммирования меньше нижней границы.

В случае i =j имеем

Учитывая, что и, выражая из последнего соотношения , получаем

(2.3)

Наконец, при получаем

откуда, с учетом того, что u_jj º 1, приходим к формуле

(2.4)

Итак, расчетные формулы (2.2) – (2.4) получены. Для того чтобы при их применении не использовались неизвестные (не вычисленные) величины, необходимо выбрать соответствующий порядок вычисления элементов матриц L и U.

Например, можно рекомендовать порядок расчета элементов матриц L и U, схематически изображенный на рис.1. На нем цифры слева для матрицы L и сверху - для матрицы U означают, что на первом шаге рассчитывается по формуле (2.3), затем вычисляется элемент по формуле (2.2).

Далее (3 шаг) определяются элементы второй строки матрицы L в порядке, указанном стрелкой: и (по формулам (2.4) и (2.3) соответственно).

На 4 шаге выполняется расчет элементов 3 столбца матрицы U в порядке, обозначенном стрелкой: , (формулы (2.2)) и т.д.

Рис. 2.1

Пример 1. LU – разложение матрицы.

.

По формуле (2.3) для определяем . В соответствии с рис. 2.1 далее вычисляем по формуле (2.2)

Переходим к определению элементов второй строки матрицы L (рис. 2.1) по формулам (2.4) и (2.3)

,

Следующий этап – расчет элементов третьего столбца матрицы по формуле (2.2)

Завершающий этап – определение элементов 3 строки матрицы L

; ,

Выпишем полученное разложение, учитывая, что по определению

Рассмотрим теперь применение LU -разложения для решения СЛАУ вида

,

где .

Введем вспомогательный вектор y,

. (2.5)

Тогда исходную систему можно записать так

. (2.6)

В силу формул (2.5) и (2.6) решение исходной СЛАУ сводится к последовательному решению систем (2.6) и (2.5) соответственно с верхней и нижней треугольной матрицами.

Пример 2. Используя метод LU -разложения, решить СЛАУ вида

.

Заметим, что матрица данной системы совпадает с матрицей A из примера 1, для которой требуемое разложение уже получено. Таким образом, решение данной системы сводится к последовательному решению систем

и

Из первой системы последовательно находим

,

,

.

Подставляя найденные значения , и во вторую систему, и последовательно определяем , , :

;

;

.

Непосредственной подстановкой найденных значений , и в исходную систему можно убедиться, что решения найдены верно.