LU-разложение матрицы и основанный на нем метод решения системы

Теорема об LU-разложении матрицы

Рассматривается неоднородная система линейных алгебраических уравнений (СЛАУ):

, (5)

где - матрица системы, - вектор неизвестных и правой части соответственно, .

Теорема. Пусть все ведущие подматрицы , , матрицы являются невырожденными. Тогда единственным образом представима в виде:

, (10)

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

. (15)

Представление (10) называется LU-разложением матрицы .

Доказательство. Доказательство проведем конструктивно, т.е. построим непосредственно разложение (10). Напомним, что главные подматрицы - это

.

Предположим, что разложение (10) уже построено, т.е. матрица представлена в виде:

Элементы матрицы известны, а элементы матриц необходимо найти. Построим систему уравнений относительно неизвестных элементов матриц , записывая уравнения для соответствующих элементов матрицы :

(20)

или, учитывая, что

систему (20) можно записать в виде:

. (22)

Записывая последовательно уравнения системы (20), получим:

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

,

откуда сразу получаем значение для .

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

,

откуда .

Идя последовательно по элементам первой строки матрицы , получим, что

.

Переходим на вторую строку матрицы :

.

,

и т.д. Проводя вычисления, составляя уравнения для элементов матрицы в порядке

,

получим следующие формулы для вычисления неизвестных элементов матриц :

(25)

Ясно, что вычисления по формулам (25) можно вести только тогда, когда . Проверим выполнение этого условия. Из (22) следует, что

,

поэтому

. (30)

Поскольку нижняя и верхняя треугольные матрицы соответственно, то их определители равны произведению элементов, стоящих на главной диагонали, поэтому

,

и, как следует из (30)

.

По условию теоремы все , невырожденные, т.е.

,

кроме того ,

что и требовалось доказать.

LU-разложение матрицы и основанный на нем метод решения системы

Пусть решается СЛАУ (5), при этом имеется LU-разложением матрицы системы. Тогда метод решения СЛАУ, основанный на LU-разложении заключается в следующем. Исходная система представляется в эквивалентном виде:

. (35)

Обозначим произведение матрицы на вектор неизвестных через вектор новых неизвестных :

, (40)

тогда система (35) примет вид:

. (45)

Таким образом, чтобы решить исходную систему (5) общего вида в методе, основанном на LU-разложении, надо решить последовательно две системы, но с треугольными матрицами: сначала СЛАУ (45), в результате получим вектор , а затем СЛАУ (40), подставив в правую часть уже известный .

СЛАУ (45) – система с нижней треугольной матрицей с единицами на главной диагонали:

.

Ее решение происходит сверху вниз путем последовательной подстановки уже найденных значений . После того, как найден, решается СЛАУ (40):

.

Решение производится снизу вверх путем выполнения последовательной подстановки уже найденных на предыдущих шагах значений .

Таким образом, основные шаги метода решения СЛАУ (5), основанного на LU-разложении матрицы системы, следующие:

Шаг 1. Построить LU-разложение матрицы СЛАУ: ;

Шаг 2. Решить СЛАУ , в результате решения получить вектор ;

Шаг 3. Решить СЛАУ , в результате решения получить искомый вектор .