LU-разложение. LUP-разложение

LU-разложение матрицы A - это представление матрицы A в виде произведения

A=LU,

где L-нижняя треугольная матрица, U - верхняя треугольная или ступенчатая матрица.

Процедура LU - разложения

Пусть A прямоугольная матрица порядка m×n любого ранга. С правой стороны матрицы А приписываем единичную матрицу E порядка m×m. Применяем к матрице A|E метод исключения Гаусса. Если на каком то этапе Гауссово исключения ведущий элемент равен нулю, и существует ненулевой элемент, расположенный ниже ведущего элемента, то LU - разложение данной матрицы невозможно. Если же элементы ниже ведущего элемента нулевые, то выбираем новый ведущий элемент той же строки и следующего столбца.

Приводим матрицу A|E к треугольному или ступенчатому виду. Получим матрицу U|L₀, где U- верхняя треугольная или ступенчатая матрица, а L₀- нижняя треугольная матрица. Заметим, что полученная матрица L₀ приводит A к треугольному или ступенчатому виду:

L₀A=U.

(1)

Так как L₀ квадратная невырожденная матрица, следовательно имеет обратную матрицу . Тогда

(2)

или

(3)

где .

Как мы отметили, не всегда можно проводить LU -разложение матрицы. Но LUP- разложение всегда возможно.

LUP-разложение матрицы A - это представление матрицы A в виде произведения

PA=LU,

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

Процедура LUP - разложения

Пусть A прямоугольная матрица порядка m×n любого ранга. С правой стороны матрицы А приписываем единичную матрицу E порядка m×m. Применяем к матрице A|E матод исключения Гаусса c выбором наибольшего по модулю ведущего элемента. Если на каком то этапе исключения ведущий элемент равен нулю, то процедуру останавливаем. Получим матрицу U|L₀. Тогда имеют место равенства (1) и (2). Но в общем случае L₀ и, следовательно, не являются нижними треугольными матрицами, если при применении Гауссово исключения строки переставлялись.

Далее допустим, что мы знаем, как построить матрицу A₁ из матрицы A переставляя строки так, что при применении Гауссово исключения c выбором максимального по модулю ведущего элемента относительно матрицы A₁ не понадобилась переставление строк. Выбираем матрицу перестановок так, что

(4)

Строим матрицу A₁|E и применяем Гауссово исключение. Получим матрицу U|L₁. Тогда

(5)

где L₁ и нижние треугольные матрицы т.к. при применении Гауссово исключения строки матрицы A₁ не переставлялись.

Из (4) и (5) имеем:

(6)

Обозначим.

Наша задача найти L и U, без построения A₁.

Из (2) и (4) имеем:

(7)

Тогда, учитывая второе равенство (5), получим:

(8)

Следовательно

(9)

Получили, что для LUP-разложения нужно применить Гауссово исключение c выбором максимального по модулю ведущего элемента относительно матрицы A|E. Получим матрицу . Вычисляем обратную матрицу . Вычисляем L из выражения (9).