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

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

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

Применения

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

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

${\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 .

Алгоритм

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

Будем использовать следующие обозначения для элементов матриц: ${\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