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

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

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

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

Применения

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

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

[math]\displaystyle{ Ax=b }[/math]

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

[math]\displaystyle{ LUx=b . }[/math]

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

[math]\displaystyle{ Ly=b . }[/math]

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

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

[math]\displaystyle{ Ux=y . }[/math]

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

Обращение матриц

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

[math]\displaystyle{ AX=I }[/math],

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

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

Вычисление определителя матрицы

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

[math]\displaystyle{ A=LU }[/math],

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

[math]\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) }[/math],

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

Вывод формулы

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

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

[math]\displaystyle{ a_{11} = l_{11} u_{11} }[/math]

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

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

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

[math]\displaystyle{ A = \begin{pmatrix} a_{11} & w^T \\ v & A' \\ \end{pmatrix} }[/math],

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

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

[math]\displaystyle{ L = \begin{pmatrix} 1 & 0 \\ v_l & L' \\ \end{pmatrix},\ U = \begin{pmatrix} a_{11} & w_u^T \\ 0 & U' \\ \end{pmatrix} . }[/math]

Уравнение [math]\displaystyle{ A=LU }[/math] принимает вид

[math]\displaystyle{ w^T=w^T_u, }[/math]

[math]\displaystyle{ v=a_{11}v_l, }[/math]

[math]\displaystyle{ A' = v_l w_u^T + L' U'. }[/math]

Решая систему уравнений относительно [math]\displaystyle{ v_l }[/math], [math]\displaystyle{ w_u }[/math], [math]\displaystyle{ L' }[/math], [math]\displaystyle{ U' }[/math], получаем:

[math]\displaystyle{ w_u = w, }[/math]

[math]\displaystyle{ v_l = v / a_{11}, }[/math]

[math]\displaystyle{ L'U' = A' - v w^T / a_{11}. }[/math]

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

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

[math]\displaystyle{ U = \begin{pmatrix} a_{11} & w^T \\ 0 & U' \\ \end{pmatrix} , }[/math]

[math]\displaystyle{ L'U' = A' - v w^T / a_{11}. }[/math]

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

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

Алгоритм

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

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

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

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: [math]\displaystyle{ u_{ij}=a_{ij} - \sum^{i}_{k=1} l_{ik}*u_{kj} }[/math]
      2. Если i>j: [math]\displaystyle{ l_{ij}=(a_{ij}-\sum^{j}_{k=1} l_{ik}*u_{kj})/u_{jj} }[/math]

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

См. также

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

Литература

• Ортега Дж. Введение в параллельные и векторные методы решения линейных систем. — М.: Мир, 1991. — 376 с. — ISBN 5-03-001941-3.
• Шаблон:Source