LU-факторизация алгоритмом Краута

Схема Халецкого (LU-факторизация)

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

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

В методе решения систем линейных уравнений, основанном на факторизации, предполагается, что исходная система (6.12)

может быть представлена в виде

, (6.13)

т.е.

. (6.14)

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

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

. (6.15)

Ограничившись для наглядности порядком , запишем - и -матрицы

Схема Халецкого. Предполагая возможным разложение (6.14), вводя вспомогательный вектор

(6.16)

и подставив данное выражение в уравнение (6.13), получим

­- (6.17)

две треугольные системы, эквивалентные исходной системе. Поскольку обе системы (6.16) и (6.17) треугольные, их решения достаточно тривиальны, причем в начале решаем систему (6.17) и находим вектор , а затем из (6.16) окончательно находим .

Распишем подробнее алгоритм решения. Записывая систему (6.17) в виде

Для первых компонент вектора можем записать

,

,

.

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

; , (6.18)

при .

Для того чтобы соотношение (6.18) имело смысл, не должны равняться нулю.

Теперь решим систему (6.16) в координатной форме:

,

,

,

,

.

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

,

,

.

Обобщая эту последовательность действий, называемую обратной подстановкой или обратным ходом, запишем

, (6.19)

при .

Число операций, требуемых для выполнения как прямой, так и обратной подстановок, равно примерно , а в сумме для решения вместе с разложением требуется примерно операций.

Изучение соотношений (6.16) и (6.17) показывает, что компоненты используются только для определения и позднее не требуются. Аналогично не нужны после вычисления . Следовательно, при такой системе расчетов векторы и могут быть размещены в одних и тех же ячейках памяти ЭВМ. Коэффициенты треугольных систем – матрицы и , если не хранить единичную диагональ матрицы , могут быть размещены на месте исходной матрицы коэффициентов . Следует также отметить эквивалентность обратных подстановок в схеме Халецкого и в методе Гаусса.

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

Суть алгоритма Краута. Предполагая, что разложение существует, запишем произведение :

.

Сравнивая компоненты этого произведения с компонентами матрицы , видим, что первый столбец произведения равен первому столбцу матрицы , т.е. , при . Первая строка произведения может быть использована для определения первой строки матрицы . Действительно, т.к.

,

при , получаем

.

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

,

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

,

при . Далее, чередуя строки и столбцы, можно аналогичным образом найти остальные элементы матриц и .

Чтобы получить общие соотношения, запишем произвольный элемент произведения :

,

где верхний предел суммы учитывает наличие нулевых элементов в матрицах и . Рассмотрим произвольный элемент на или под главной диагональю матрицы , для которого , и заменим индекс на . Учитывая при этом, что , получим

,

откуда

, (6.20)

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

,

откуда

, (6.21)

при и .

Эти соотношения для и есть алгоритм разложения на треугольные матрицы – алгоритм Краута. Заметим, что текущие элементы матриц и определяются текущим элементом матрицы и предыдущими элементами матриц и . Отсюда, т.к. нулевые элементы и единичную диагональ матрицы запоминать не нужно, в процессе вычислений матрицы и могут быть записаны на месте матрицы , причем расположена в нижнем треугольнике , а – соответственно в верхнем треугольнике матрицы .

Коротко алгоритм Краута как вариант чередования столбцов и строк можно представить следующей последовательностью действий:

1) положим и перейдем к пункту 3;

2) используя выражение (6.20), рассчитываем -ый столбец матрицы и, если , закончим процедуру разложения;

3) используя выражение (6.21), рассчитываем -ую строку матрицы ;

4) положим и перейдем к пункту 2.

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

Если последовательно обходить ()-произведение по строкам, то можно заметить, что, используя предыдущие соотношения (6.20) для при и (6.21) для при , можно беспрепятственно определить все элементы матриц и . Аналогично можно организовать алгоритм вычисления элементов матриц и , совершая обход по столбцам.

Преимущества этих вариантов алгоритма Краута проявляются при матрицах большого размера.

Известен также вариант алгоритма -факторизации, основанный на приведении исходной матрицы к верхней треугольной форме по Гауссу [1], однако по сравнению с алгоритмом Краута он требует более частого обращения к матрице .