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

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

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

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

Содержание

ПримененияПравить

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

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

Ax=b

Если известно LU-разложение матрицы $A$ , $A=LU$ , исходная система может быть записана как^[1]

LUx=b.

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

Ly=b.

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

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

Ux=y.

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

Обращение матрицПравить

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

AX=I

,

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

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

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

Имея 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$ .

Вывод формулыПравить

В силу назначения LU-разложения нас будет интересовать только случай, когда матрица A невырождена.

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

a_{11}=l_{11}u_{11}

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

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

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

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

,

где $v,w^{T},A'$ имеют размерность соответственно (N-1)×1, 1×(N-1), (N-1)×(N-1). Аналогично разделим на клетки матрицы L и U:

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

Уравнение

A=LU

принимает вид

w^{T}=w_{u}^{T}\

v=a_{11}v_{l}\

A'=v_{l}w_{u}^{T}+L'U'

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

w_{u}=w\

v_{l}=v/a_{11}\

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

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

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

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

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

Итак, мы свели LU-разложение матрицы N×N к LU-разложению матрицы (N-1)×(N-1).

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

Заметим, что $vw^{T}\$ — не скаляр, а матрица (N-1)×(N-1).

АлгоритмПравить

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

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

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

$u_{1j}=a_{1j},\ j=1\dots n$
$l_{j1}={\frac {a_{j1}}{u_{11}}},\ j=1\dots n\ (u_{11}\neq 0)$

Для $i=2\dots n$

$u_{ij}=a_{ij}-\sum _{k=1}^{i-1}l_{ik}u_{kj},\ j=i\dots n$
$l_{ji}={\frac {1}{u_{ii}}}(a_{ji}-\sum _{k=1}^{i-1}l_{jk}u_{ki}),\ j=i\dots n$

В итоге мы получим матрицы — $L$ и $U$ . В программной реализации данного метода (компактная схема Гаусса) для представления матриц $L$ и $U$ можно обойтись всего одним массивом, в котором совмещаются матрицы $L$ и $U$ . Например, так (для матрицы размером $3\times 3$ ):