WikiSort.ru - Не сортированное

Для улучшения этой статьи желательно: Проставив сноски, внести более точные указания на источники. Добавить иллюстрации.

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

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

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

Применения

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

Исходя из области применения 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].

Алгоритм

В этом разделе не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете отредактировать эту статью, добавив ссылки на авторитетные источники. Эта отметка установлена 12 мая 2011 года.

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

Будем использовать следующие обозначения для элементов матриц: ${\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}$ . Тогда, если известно LU-разложение матрицы, её определитель можно вычислить по формуле

${\displaystyle \det(A)=\det(LU)=\det(L)\det(U)=\det(U)=\prod _{i=1}^{n}U_{ii}.}$

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

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

Для ${\displaystyle i=2\dots n}$

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

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

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

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

См. также

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

Примечания

Литература

• Ортега Дж. Введение в параллельные и векторные методы решения линейных систем. — М.: Мир, 1991. — 376 с. — ISBN 5-03-001941-3.
• Левитин А. В. Алгоритмы. Введение в разработку и анализ — М.: Вильямс, 2006. — 576 с. — ISBN 978-5-8459-0987-9
  <a href='https://wikidata.org/wiki/Track:Q21694518'></a><a href='https://wikidata.org/wiki/Track:Q21694521'></a><a href='https://wikidata.org/wiki/Track:Q21694522'></a>