Меню Главная Случайная статья Настройки LU-разложение Материал из https://ru.wikipedia.org LU-разложение (LU-декомпозиция, LU-факторизация) — представление матрицы ${\displaystyle A}$ в виде произведения двух матриц, ${\displaystyle A=LU}$, где ${\displaystyle L}$ — нижняя треугольная матрица, а ${\displaystyle U}$ — верхняя треугольная матрица. LU-разложение используется для решения систем линейных уравнений, обращения матриц и вычисления определителя. LU-разложение существует только в том случае, когда матрица ${\displaystyle A}$ обратима, а все ведущие (угловые) главные миноры матрицы ${\displaystyle A}$ невырождены[1]. Этот метод является одной из разновидностей метода Гаусса. Содержание 1 Применения 1.1 Решение систем линейных уравнений 1.2 Обращение матриц 1.3 Вычисление определителя матрицы 2 Вывод формулы 3 Алгоритм 4 См. также 5 Примечания 6 Литература Применения Решение систем линейных уравнений Полученное LU-разложение матрицы ${\displaystyle A}$ (матрица коэффициентов системы) может быть использовано для решения семейства систем линейных уравнений с различными векторами ${\displaystyle b}$ в правой части[2]: ${\displaystyle Ax=b}$ Если известно LU-разложение матрицы ${\displaystyle A}$, ${\displaystyle A=LU}$, исходная система может быть записана как ${\displaystyle LUx=b.}$ Эта система может быть решена в два шага. На первом шаге решается система ${\displaystyle Ly=b.}$ Поскольку ${\displaystyle L}$ — нижняя треугольная матрица, эта система решается непосредственно прямой подстановкой. На втором шаге решается система ${\displaystyle Ux=y.}$ Поскольку ${\displaystyle U}$ — верхняя треугольная матрица, эта система решается непосредственно обратной подстановкой. Обращение матриц Обращение матрицы ${\displaystyle A}$ эквивалентно решению линейной системы ${\displaystyle AX=I}$, где ${\displaystyle X}$ — неизвестная матрица, ${\displaystyle I}$ — единичная матрица. Решение ${\displaystyle X}$ этой системы является обратной матрицей ${\displaystyle A^{-1}}$. Систему можно решить описанным выше методом LU-разложения. Вычисление определителя матрицы Имея LU-разложение матрицы ${\displaystyle A}$, ${\displaystyle A=LU}$, можно непосредственно вычислить её определитель, ${\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)}$, где ${\displaystyle n}$ — размер матрицы ${\displaystyle A}$, ${\displaystyle L_{ii}}$ и ${\displaystyle U_{ii}}$ — диагональные элементы матриц ${\displaystyle L}$ и ${\displaystyle U}$. Вывод формулы Исходя из области применения, 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]. Алгоритм Один из алгоритмов для вычисления LU-разложения приведён ниже.[3] Будем использовать следующие обозначения для элементов матриц: ${\displaystyle A=(a_{ij})}$, ${\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}$. Найти матрицы ${\displaystyle L}$ и ${\displaystyle U}$ можно следующим образом (выполнять шаги следует строго по порядку, так как следующие элементы находятся с использованием предыдущих): Цикл i от 1 до n Цикл j от 1 до n uij=0, lij=0 lii=1 Цикл i от 1 до n Цикл j от 1 до n Если i<=j: ${\displaystyle u_{ij}=a_{ij}-\sum _{k=1}^{i}l_{ik}*u_{kj}}$ Если i>j: ${\displaystyle l_{ij}=(a_{ij}-\sum _{k=1}^{j}l_{ik}*u_{kj})/u_{jj}}$ В итоге мы получим матрицы — ${\displaystyle L}$ и ${\displaystyle U}$. См. также LUP-разложение Разложение матрицы Примечания 1 2 Е. Е. Тыртышников. Матричный анализ и линейная алгебра. — 2004-2005. Левитин, 2006. Литература Левитин А. В. Алгоритмы. Введение в разработку и анализ — М.: Вильямс, 2006. — 576 с. — ISBN 978-5-8459-0987-9