4.3 Связь метода гаусса с разложением матрицы на множители. Схема халецкого
Мы видели, что прямой ход метода Гаусса преобразует СЛАУ Ax=b в Ux= , где
Найдем связь между компонентами векторов b и . Для этого обратимся к уравнениям (4.3):
при k=1 
при k=2
и т.д.
,
j=1…n,
где
.
Таким образом, получили систему уравнений вида b=L, где L – нижняя треугольная матрица.
Перепишем эту систему в виде =L–1b, тогда Ux= L–1b или
LUx= b.
Сравнивая с исходным уравнением, получаем A=LU, или в координатном виде
, (4.4)
то есть матрица А представлена в виде произведения двух треугольных матриц: нижней треугольной матрицы с ненулевыми диагональными элементами и верхней треугольной матрицы с единичной главной диагональю (LU – разложение).
Существует теорема об LU–разложении [6].
Если все угловые миноры матрицы А отличны от нуля, то матрицу А можно единственным образом представить в виде LU – разложения, т.е. произведения A=LU.
Следствие. Метод Гаусса можно применять тогда и только тогда, когда угловые миноры матрицы отличны от нуля.
Получим формулы для определения элементов этих треугольных матриц.
Для этого преобразуем правую часть формулы (4.4) двумя способами.
1.
.
Так
как
,
а последняя сумма равна нулю (
при j<k),
то
при i
j. (4.5)
Имеем рекуррентную формулу для нахождения коэффициентов нижней треугольной матрицы. Здесь l11=a11 , u11=1.
2.
.
Так
как последняя сумма равна нулю (
при k> i),
то
при i <
j . (4.6)
Имеем рекуррентную формулу для нахождения коэффициентов верхней треугольной матрицы. Обратите внимание на то, что эта формула работает в связке с формулой (4.5).
Таким образом, матрицы разложения определены формулами (4.5–4.6).
Но не забываем, что наша конечная цель – решение уравнения Ах=b. Поэтому назовем разложение матрицы на множители первым этапом поиска решения.
Второй этап – решение уравнения L=b. Найти вектор довольно просто, так как L – треугольная матрица:
.
Третий этап – решение уравнения Ux=. Так как U – тоже треугольная матрица, то
Этот процесс носит название схемы Халецкого (Cholesky). Она весьма экономна, когда надо найти решение систем линейных алгебраических уравнений с постоянной матрицей А и переменным вектором правых частей b.
4.4 Вычисление определителя и обратной матрицы
Представим матрицу А в виде LU-разложения. Тогда
Таким образом, определитель матрицы можно найти как произведение диагональных элементов нижней треугольной матрицы в LU-разложении или как произведение ведущих элементов в схеме Гаусса. Следует только иметь в виду: если в процессе реализации схемы Гаусса производились перестановки строк или столбцов, то при нечетном числе перестановок det(A) = – det(L).
Пусть
А–1 ={
ij }–
матрица, обратная матрице А = {a
ij },
то есть АА–1
= 1, или
,
где
i,j
= 1… n. (4.7)
Пусть j = 1. Тогда i1 и i1 – векторы-столбцы и вид уравнения (4.7) ничем не отличается от координатного вида (4.1) уравнения Ах=b.
Следовательно, если мы каким-либо способом решим уравнение
,
то найдем первый вектор-столбец обратной матрицы {i1}.
Аналогично, полагая j = 2 и решая уравнение
,
получим второй столбец обратной матрицы { i2}.
Вывод: чтобы получить n столбцов обратной матрицы, необходимо n раз решить систему уравнений (4.7) с постоянной матрицей А и переменной правой частью, представляющей собой столбец с последовательно сдвигаемой единичкой. В этом поможет схема Халецкого.
Посмотрим на эту процедуру с точки зрения LU-разложения.
Этап 1. Находим элементы матриц L и U.
Этап
2. Решаем систему уравнений
.
Этап
3. Решаем систему уравнений
и
находим первый столбец обратной матрицы.
Этап 4. Повторяем этапы 2 и 3 n раз, сдвигая единицу в правой части.
Отметим,
что, зная обратную матрицу, легко получить
решение СЛАУ в виде
.