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} \ne 0, тогда l_{11} \ne 0 и u_{11} \ne 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^T_u\
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' - v w^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' - v w^T / a_{11}\

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

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

Заметим, что  v w^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 можно следующим образом (выполнять шаги следует строго по порядку, так как следующие элементы находятся с использованием предыдущих):

  1. u_{1j} = a_{1j},\ j = 1\dots n
  2. l_{j1} = \frac {a_{j1}} {u_{11}},\  j = 2\dots n\  (l_{11} \ne 0)

Для i = 2\dots n

  1. u_{ij} = a_{ij} - \sum_{k=1}^{i-1} l_{ik}u_{kj},\  j = i\dots n
  2. l_{ji} = \frac {1} {u_{ii}}(a_{ji} - \sum_{k=1}^{i-1} l_{jk}u_{ki}),\  j = i+1\dots n

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

\begin{pmatrix}
  u_{11} & u_{12} & u_{13} \\
  l_{21} & u_{22} & u_{23} \\
  l_{31} & l_{32} & u_{33} \\
\end{pmatrix}

См. также[править | править вики-текст]

Литература[править | править вики-текст]

  • Ортега Дж. Введение в параллельные и векторные методы решения линейных систем. — М.: Мир, 1991. — 376 с. — ISBN 5-03-001941-3.
  • Левитин, Ананий В. Алгоритмы: введение в разработку и анализ = Introduction to The Design & Analysis of Algorithms. — М.: Издательский дом «Вильямс», 2006. — 576 с. — ISBN 5-8459-0987-2.
  1. 1 2 3 4 Левитин, 2006