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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

LU-разложение (LU-декомпозиция, LU-факторизация) — представление матрицы в виде произведения двух матриц, , где  — нижняя треугольная матрица, а  — верхняя треугольная матрица.

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

Этот метод является одной из разновидностей метода Гаусса.

Применения[править | править код]

Решение систем линейных уравнений[править | править код]

Полученное LU-разложение матрицы (матрица коэффициентов системы) может быть использовано для решения семейства систем линейных уравнений с различными векторами в правой части[2]:

Если известно LU-разложение матрицы , , исходная система может быть записана как

Эта система может быть решена в два шага. На первом шаге решается система

Поскольку  — нижняя треугольная матрица, эта система решается непосредственно прямой подстановкой.

На втором шаге решается система

Поскольку  — верхняя треугольная матрица, эта система решается непосредственно обратной подстановкой.

Обращение матриц[править | править код]

Обращение матрицы эквивалентно решению линейной системы

,

где  — неизвестная матрица,  — единичная матрица. Решение этой системы является обратной матрицей .

Систему можно решить описанным выше методом LU-разложения.

Вычисление определителя матрицы[править | править код]

Имея LU-разложение матрицы ,

,

можно непосредственно вычислить её определитель,

,

где  — размер матрицы , и  — диагональные элементы матриц и .

Вывод формулы[править | править код]

Исходя из области применения LU-разложение может быть применено только к невырожденной матрице, поэтому далее будем считать что матрица невырождена.

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

Если , то или . В первом случае целиком состоит из нулей первая строка матрицы , во втором — первый столбец матрицы . Следовательно, или вырождена, а значит, вырождена , что приводит к противоречию. Таким образом, если , то невырожденная матрица не имеет LU-разложения.

Пусть , тогда и . Поскольку L и U определены с точностью до умножения U на константу и деления L на ту же константу, мы можем потребовать, чтобы . При этом .

Разделим матрицу A на клетки:

,

где имеют размерность соответственно , , .

Аналогично разделим на клетки матрицы и :

Уравнение принимает вид

Решая систему уравнений относительно , , , , получаем:

Окончательно имеем:

Итак, мы свели LU-разложение матрицы размера к LU-разложению матрицы размера .

Выражение называется дополнением Шура элемента в матрице A[1].

Алгоритм[править | править код]

Один из алгоритмов для вычисления LU-разложения приведён ниже.

Будем использовать следующие обозначения для элементов матриц: , , ; причём диагональные элементы матрицы : , . Тогда, если известно LU-разложение матрицы, её определитель можно вычислить по формуле

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

Для

В итоге мы получим матрицы — и .

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

См. также[править | править код]

Примечания[править | править код]

  1. 1 2 Е. Е. Тыртышников. Матричный анализ и линейная алгебра. — 2004-2005.
  2. Левитин, 2006.

Литература[править | править код]