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

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

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

LU-разложение является обратной операцией по отношению к последовательному исключению неизвестных с помощью матрицы исключения. Матрица $L$ является обратной матрице исключения $E^{-1}=L$. В отличии от матрицы исключения $E$, обратная ей матрица $L$ дает удобную формулу с множителями Невозможно разобрать выражение (синтаксическая ошибка): {\displaystyle ℓ_{ij}} , расположенными каждый на своем месте (См. Матрица, обратная матрице исключения).

Метод LU-разложения является одной из разновидностей метода Гаусса.

Применения

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

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

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

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

Первый способ

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

Так в примере (См. Матрица исключения):

Невозможно разобрать выражение (неизвестная функция «\begin{bmatrix}»): {\displaystyle E=E_{32}E_{31}E_{21}= \begin{bmatrix} 1 & 0 & 0 \\0 & 1 & 0 \\ 0 & -ℓ_{32} & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 \\0 & 1 & 0 \\ -ℓ_{31} & 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 \\-ℓ_{21} & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}= \begin{bmatrix} 1 & 0 & 0 \\-ℓ_{21} & 1 & 0 \\(ℓ_{32}ℓ_{21}-ℓ_{31}) & -ℓ_{32} & 1 \end{bmatrix}}

при вычислении третьей строки $U$ производится вычитание кратных количеств полученных ранее, предыдущих ведущих строк матрицы $U$ (но не матрицы $A$):

Невозможно разобрать выражение (синтаксическая ошибка): {\displaystyle \text{Строка}\ 3\ \text{матрицы}\ U\ = (\text{Строка}\ 3\ \text{матрицы}\ A)\ - ℓ_{31}\times(\text{Строка}\ 1\ \text{матрицы}\ U)\ - ℓ_{32}\times(\text{Строка}\ 2\ \text{матрицы}\ U)\ }

	Исходная матрица	Приводим элемент {3,1} матрицы, находящийся под ведущим элементом первой строки, к нулю	Приводим элемент {3,2} матрицы, находящийся под ведущим элементом второй строки, к нулю
$\text{Строка}3\text{матрицы}U=$	$(\text{Строка}3\text{матрицы}A)$	Невозможно разобрать выражение (синтаксическая ошибка): {\displaystyle - ℓ_{31}(\text{Строка}\ 1\ \text{матрицы}\ U)}	Невозможно разобрать выражение (синтаксическая ошибка): {\displaystyle - ℓ_{32}(\text{Строка}\ 2\ \text{матрицы}\ U) }

Таким образом строка Невозможно разобрать выражение (синтаксическая ошибка): {\displaystyle [ℓ_{31},ℓ_{32},1]} умножается на матрицу $U$, что видно если мы перепишем равенство:

Невозможно разобрать выражение (синтаксическая ошибка): {\displaystyle \text{Строка}\ 3\ \text{матрицы}\ A\ = ℓ_{31}\times(\text{Строка}\ 1\ \text{матрицы}\ U)\ + ℓ_{32}\times(\text{Строка}\ 2\ \text{матрицы}\ U)\ +1\times(\text{Строка}\ 3\ \text{матрицы}\ U)\ }

Это равенство соответствует равенству $A=LU$ для третьей строки $A$, где третья строка $L$ содержит Невозможно разобрать выражение (синтаксическая ошибка): {\displaystyle ℓ_{31},ℓ_{32},1} . Все строки имеют аналогичный вид независимо от размера матрицы $A$. Таким образом без перестановки строк мы имеем $A=LU$.

Второй способ. Умножение столбцов кратно строкам

Суть этого способа вывода формулы в последовательном исключении осуществленном посредством вычитания одного столбца матрицы $L$ из матрицы $A$ количеством раз равного одной строке матрицы $U$.

Последовательное исключение неизвестных начинается с ведущей строки матриц $L$ и $U$, которая равна первой строке матрицы $A$. Ведущую строку умножаем на числа Невозможно разобрать выражение (синтаксическая ошибка): {\displaystyle ℓ_{21}} и Невозможно разобрать выражение (синтаксическая ошибка): {\displaystyle ℓ_{31}} и, в конечном итоге, на число Невозможно разобрать выражение (синтаксическая ошибка): {\displaystyle ℓ_{n1}} . Следующим действием производим ее вычитание из строки 2 и строки 3 и, в конечном итоге, из строки $n$ матрицы $A$. Если в первом действии, с умножением, мы выбрали числа Невозможно разобрать выражение (синтаксическая ошибка): {\displaystyle ℓ_{21}=a_{21}/a_{11}} , Невозможно разобрать выражение (синтаксическая ошибка): {\displaystyle ℓ_{31}=a_{31}/a_{11}} и, в конечном итоге, Невозможно разобрать выражение (синтаксическая ошибка): {\displaystyle ℓ_{n1}=a_{n1}/a_{11}} , то результом вычитания в столбце 1 будут нули.

Первый шаг удаляет Невозможно разобрать выражение (неизвестная функция «\begin{bmatrix}»): {\displaystyle \begin{bmatrix} 1\times(\text{строка}\ 1) \\ ℓ_{21}\times(\text{строка}\ 1) \\ ℓ_{31}\times(\text{строка}\ 1) \\ℓ_{41}\times(\text{строка}\ 1) \end{bmatrix}} из $A$, чтобы получить $A_2=\left[\begin{array}{cccc}0& 0& 0& 0\\ 0& \times & \times & \times \\ 0& \times & \times & \times \\ 0& \times & \times & \times \end{array}\right]$

То есть мы удалили одноранговую матрицу, произведя умножение столбца Невозможно разобрать выражение (синтаксическая ошибка): {\displaystyle ℓ_{1}=(1,ℓ_{21},ℓ_{31},ℓ_{41})} на строку 1 матрицы $A$ - первая ведущая строка $u_1$ матрицы math>U</math>.

Следующий шаг - осуществляем подобные операции с матрицей $A_2$, чтобы получить матрицу $A_3$:

Второй шаг удаляет Невозможно разобрать выражение (неизвестная функция «\begin{bmatrix}»): {\displaystyle \begin{bmatrix} 0\times(\text{строка}\ 1) \\ 1\times(\text{строка}\ 1) \\ ℓ_{32}\times(\text{строка}\ 1) \\ℓ_{42}\times(\text{строка}\ 1) \end{bmatrix}} из $A_2$, чтобы получить $A_3=\left[\begin{array}{cccc}0& 0& 0& 0\\ 0& 0& 0& 0\\ 0& 0& \times & \times \\ 0& 0& \times & \times \end{array}\right]$

Строка 2 матрицы $A_2$ это вторая ведущая строка и одновременно вторая ведущая строка $u_2$ матрицы math>U</math>. Мы удалили столбец Невозможно разобрать выражение (синтаксическая ошибка): {\displaystyle ℓ_{1}=(0,1,ℓ_{32},ℓ_{42})} количество раз равное этой второй ведущей строке. Проводя дальшейшие шаги подобным же образом, мы на каждом шаге удаляем столбец Невозможно разобрать выражение (синтаксическая ошибка): {\displaystyle ℓ_{j}} матрицы $L$ количество раз равное ведущей строке $u_j$ матрицы $U$. Если произвести обратную операцию сложения этих произведений столбцов Невозможно разобрать выражение (синтаксическая ошибка): {\displaystyle ℓ_{j}} матрицы $L$ и ведущих строк $u_j$ матрицы $U$ мы получим:

Невозможно разобрать выражение (синтаксическая ошибка): {\displaystyle A=ℓ_{1}u_{1}+ℓ_{2}u_{2}+\cdots+ℓ_{n}u_{n}= \begin{bmatrix} & & \\ ℓ_{1} & \cdots & ℓ_{n} \\& & \end{bmatrix} \begin{bmatrix} &u_{1} & \\ & \vdots & \\&u_{n} & \end{bmatrix} =LU }

Выражение Невозможно разобрать выражение (синтаксическая ошибка): {\displaystyle ℓ_{1}u_{1}+ℓ_{2}u_{2}+\cdots+ℓ_{n}u_{n}} является сложением одноранговых матрицы.

Третий способ

Исходя из области применения LU-разложение может быть применено только к невырожденной матрице, поэтому далее будем считать что матрица $A$ невырождена. Поскольку и в первой строке матрицы $L$, так как она является нижней треугольной матрицей, и в первом столбце матрицы $U$, так как она является верхней треугольной матрицей, все элементы, кроме, возможно, первого, равны нулю, имеем

Невозможно разобрать выражение (синтаксическая ошибка): {\displaystyle a_{11} = ℓ_{11} u_{11}}

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

Пусть $a_{11}\ne 0$, тогда Невозможно разобрать выражение (синтаксическая ошибка): {\displaystyle ℓ_{11} \ne 0} и $u_{11}\ne 0$. Поскольку L и U определены с точностью до умножения U на константу и деления L на ту же константу, мы можем потребовать, чтобы Невозможно разобрать выражение (синтаксическая ошибка): {\displaystyle ℓ_{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)$ ($N$ - число строк и столбов матрицы $A$).

Аналогично разделим на блоки матрицы $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=LU$ возможно без перестановки и без нулей на месте ведущих элементов если все верхние левые $k\times k$, где $k$ равно от 1 до $N$ подматрицы-блоки матрицы $A$ являются невырожденными.

$\left[\begin{array}{cc}{A}_k& *\\ *& *\\ \end{array}\right]=\left[\begin{array}{cc}{L}_k& 0\\ *& *\\ \end{array}\right]\left[\begin{array}{cc}{U}_k& *\\ 0& *\\ \end{array}\right]$

То есть $A_k=L_k{U}_k$. Каждая подматрица $A_k$ должна быть невырожденной, чтобы в конечном итоге можно было получить равенство $A=LU$.

Выражение $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$.

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

LDU-разложение представление матрицы $A$ в виде произведения трех матриц, $A=LDU$, где $L$ — нижняя треугольная матрица обратная матрице исключения, $D$ - диагональная матрица а $U$ — верхняя треугольная матрица. LDU-разложение это продолжение LU-разложения, когда диагональные эелементы матриц LU-факторизации определнным образом выносятся в отдельную, диагональную матрицу $D$.

Например:$A=\left[\begin{array}{ccc}1& 4& 0\\ 4& 12& 4\\ 0& 4& 0\end{array}\right]=\left[\begin{array}{ccc}1& 0& 0\\ 4& 1& 0\\ 0& -1& 1\end{array}\right]\left[\begin{array}{ccc}1& 4& 0\\ 0& -4& 4\\ 0& 0& 0\end{array}\right]=LU=\left[\begin{array}{ccc}1& 0& 0\\ 4& 1& 0\\ 0& -1& 1\end{array}\right]\left[\begin{array}{ccc}1& 0& 0\\ 0& -4& 0\\ 0& 0& 4\end{array}\right]\left[\begin{array}{ccc}1& 4& 0\\ 0& 1& -1\\ 0& 0& 1\end{array}\right]=LDU$

См. также

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

Литература

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