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

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

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

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

Содержание

Применения

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

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

$Ax=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}\neq 0$, тогда $l_{11}\neq 0$ и $u_{11}\neq 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_{u}^{T}\$

$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'-vw^{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'-vw^{T}/a_{11}\$

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

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

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

Алгоритм

Один из алгоритмов для вычисления 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=1\dots n\ (u_{11}\neq 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\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.
• Левитин А. В. Алгоритмы. Введение в разработку и анализ — М.: Вильямс, 2006. — 576 с. — ISBN 978-5-8459-0987-9
  <a href="https://wikidata.org/wiki/Track:Q21694518"></a><a href="https://wikidata.org/wiki/Track:Q21694521"></a><a href="https://wikidata.org/wiki/Track:Q21694522"></a>