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

Исходя из области применения 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-1}l_{ik}*u_{kj}}$
      2. Если i>j: ${\displaystyle l_{ij}=(a_{ij}-\sum _{k=1}^{j-1}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