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

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

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

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

Применения

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

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

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

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

$A=\left(\begin{array}{cc}{a}_{11}& w^T\\ v& A^{\prime }\end{array}\right)$,

где $v,w^T,A^{\prime }$ имеют размерность соответственно $(N-1)\times 1$, $1\times (N-1)$, $(N-1)\times (N-1)$.

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

$L=\left(\begin{array}{cc}1& 0\\ v_l& L^{\prime }\end{array}\right),U=\left(\begin{array}{cc}{a}_{11}& w_u^T\\ 0& U^{\prime }\end{array}\right).$

Уравнение $A=LU$ принимает вид

$w^T=w_u^T,$

$v=a_{11}{v}_l,$

$A^{\prime }=v_l{w}_u^T+L^{\prime }{U}^{\prime }.$

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

$w_u=w,$

$v_l=v/a_{11},$

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

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

$L=\left(\begin{array}{cc}1& 0\\ v/a_{11}& L^{\prime }\end{array}\right),$

$U=\left(\begin{array}{cc}{a}_{11}& w^T\\ 0& U^{\prime }\end{array}\right),$

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

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

Выражение $A^{\prime }-v{w}^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-разложение
• Разложение матрицы

Литература

• Шаблон:Книга
• Шаблон:Source