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

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

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

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

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

${\displaystyle Ax=b}$

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

${\displaystyle LUx=b.}$

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

${\displaystyle Ly=b.}$

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

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

${\displaystyle Ux=y.}$

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

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

${\displaystyle AX=I}$,

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

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

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

${\displaystyle A=LU}$,

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

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

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

Исходя из области применения, LU-разложение может быть применено только к невырожденной матрице, поэтому далее будем считать что матрица ${\displaystyle A}$ невырождена.

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

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

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

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

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

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

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

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

${\displaystyle L={\begin{pmatrix}1&0\\v_{l}&L'\\\end{pmatrix}},\ U={\begin{pmatrix}a_{11}&w_{u}^{T}\\0&U'\\\end{pmatrix}}.}$

Уравнение ${\displaystyle A=LU}$ принимает вид

${\displaystyle w^{T}=w_{u}^{T},}$

${\displaystyle v=a_{11}v_{l},}$

${\displaystyle A'=v_{l}w_{u}^{T}+L'U'.}$

Решая систему уравнений относительно ${\displaystyle v_{l}}$, ${\displaystyle w_{u}}$, ${\displaystyle L'}$, ${\displaystyle U'}$, получаем:

${\displaystyle w_{u}=w,}$

${\displaystyle v_{l}=v/a_{11},}$

${\displaystyle L'U'=A'-vw^{T}/a_{11}.}$

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

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

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

${\displaystyle L'U'=A'-vw^{T}/a_{11}.}$

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

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

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

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

Найти матрицы ${\displaystyle L}$ и ${\displaystyle 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: ${\displaystyle u_{ij}=a_{ij}-\sum _{k=1}^{i}l_{ik}*u_{kj}}$
      2. Если i>j: ${\displaystyle l_{ij}=(a_{ij}-\sum _{k=1}^{j}l_{ik}*u_{kj})/u_{jj}}$

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

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

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