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

Для улучшения этой статьи желательно?: Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное. Проставив сноски, внести более точные указания на источники. Добавить иллюстрации.

LU-разложение — представление матрицы $A$ в виде произведения двух матриц, $A=LU$, где $L$ — нижняя треугольная матрица, а $U$ — верхняя треугольная матрица. LU-разложение еще называют LU-факторизацией.

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

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

Применения

Решение систем линейных уравнений

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

$Ax=b ,$

где $A$ — матрица коэффициентов системы, $x$ — вектор неизвестных величин системы, $b$ — вектор правых частей системы.

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

$LUx=b .$

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

$Ly=b .$

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

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

$Ux=y .$

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

Обращение матриц

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

$AX=I$,

где $X$ — неизвестная матрица, $I$ — единичная матрица. Решение $X$ этой системы является обратной матрицей $A^{-1}$.

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

Вычисление определителя матрицы

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

$A=LU$,

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

$\det(A)=\det(LU)=\det(L)\det(U)=\left( \prod_{i=1}^n L_{ii} \right) \left( \prod_{i=1}^n U_{ii} \right)$,

где $n$ — размер матрицы $A$, $L_{ii}$ и $U_{ii}$ — диагональные элементы матриц $L$ и $U$.

Вывод формулы

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

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

$a_{11} = l_{11} u_{11}$

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

Пусть $a_{11} \ne 0$, тогда $l_{11} \ne 0$ и $u_{11} \ne 0$. Поскольку L и U определены с точностью до умножения U на константу и деления L на ту же константу, мы можем потребовать, чтобы $l_{11} = 1$. При этом $u_{11} = a_{11}$.

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

$A = \begin{pmatrix} a_{11} & w^T \\ v & A' \\ \end{pmatrix}$,

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

$L = \begin{pmatrix} 1 & 0 \\ v_l & L' \\ \end{pmatrix},\ U = \begin{pmatrix} a_{11} & w_u^T \\ 0 & U' \\ \end{pmatrix}$

Уравнение

$A=LU$

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

$w^T=w^T_u\$

$v=a_{11}v_l\$

$A' = v_l w_u^T + L' U'$

Решая систему уравнений относительно $v_l, w_u, L', U'\$, получаем:

$w_u = w\$

$v_l = v / a_{11}\$

$L'U' = A' - v w^T / a_{11}\$

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

$L = \begin{pmatrix} 1 & 0 \\ v/a_{11} & L' \\ \end{pmatrix}$

$U = \begin{pmatrix} a_{11} & w^T \\ 0 & U' \\ \end{pmatrix}$

$L'U' = A' - v w^T / a_{11}\$

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

Выражение $A' - v w^T / a_{11}$ называется дополнением Шура элемента $a_{11}$ в матрице A.

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

Алгоритм

В этом разделе не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете отредактировать эту статью, добавив ссылки на авторитетные источники. Эта отметка установлена 12 мая 2011.

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

Будем использовать следующие обозначения для элементов матриц $L=(l_{ij})$, $U=(u_{ij})$, $i,j = 1\dots n$; причём диагональные элементы матрицы $L$: $l_{ii} = 1$, $i = 1\dots n$. Тогда, если известно LU-разложение матрицы, её определитель можно вычислить по формуле $\det(A) = \det(LU) = \det(L) \det(U) = \det(U)$ = произведению элементов на диагонали матрицы U.

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

1. $u_{1j} = a_{1j},\ j = 1\dots n$
2. $l_{j1} = \frac {a_{j1}} {u_{11}},\ j = 2\dots n\ (l_{11} \ne 0)$

Для $i = 2\dots n$

1. $u_{ij} = a_{ij} - \sum_{k=1}^{i-1} l_{ik}u_{kj},\ j = i\dots n$
2. $l_{ji} = \frac {1} {u_{ii}}(a_{ji} - \sum_{k=1}^{i-1} l_{jk}u_{ki}),\ j = i+1\dots n$

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

$\begin{pmatrix} u_{11} & u_{12} & u_{13} \\ l_{21} & u_{22} & u_{23} \\ l_{31} & l_{32} & u_{33} \\ \end{pmatrix}$

См. также

• LUP-разложение
• Разложение матрицы

Литература

• Ортега Дж. Введение в параллельные и векторные методы решения линейных систем. — М.: Мир, 1991. — 376 с. — ISBN 5-03-001941-3