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

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

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

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

Применения

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

Полученное 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)\times 1$, $1\times (N-1)$, $(N-1)\times (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\times N$ к LU-разложению матрицы размера $(N-1)\times (N-1)$.

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

Алгоритм

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

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

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

1. Цикл i от 1 до n
   1. Цикл j от 1 до n
      1. u_ij=0, l_ij=0
      2. l_ii=1
2. Цикл i от 1 до n
   1. Цикл j от 1 до n
      1. Если i<=j: $u_{ij}=a_{ij}-\sum _{k=1}^{i}l_{ik}*u_{kj}$
      2. Если i>j: $l_{ij}=(a_{ij}-\sum _{k=1}^{j}l_{ik}*u_{kj})/u_{jj}$

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

См. также

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

Литература

• Ортега Дж. Введение в параллельные и векторные методы решения линейных систем. — М.: Мир, 1991. — 376 с. — ISBN 5-03-001941-3.
• Левитин А. В. Алгоритмы. Введение в разработку и анализ — М.: Вильямс, 2006. — 576 с. — ISBN 978-5-8459-0987-9