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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

,

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

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

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

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

,

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

,

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

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

В силу назначения LU-разложения нас будет интересовать только случай, когда матрица A невырождена.

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

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

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

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

,

где имеют размерность соответственно (N-1)×1, 1×(N-1), (N-1)×(N-1). Аналогично разделим на клетки матрицы L и U:

Уравнение

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

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

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

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

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

Заметим, что  — не скаляр, а матрица (N-1)×(N-1).

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

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

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

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

Для

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

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

Литература[править | править вики-текст]

  1. 1 2 3 4 Левитин, 2006.