LU-разложение
- точное указание ограничений на применимость LU-разложения: какой должны быть матрица
, чтобы невозможно было её разложить (и нужно было бы переходить к РазложениеLUP)?
Содержание
Определение
LU-разложением матрицы называется её представление в виде произведения матриц 
:
![A =
left \[
matrix {
ccol {a sub 11 above vdots above a sub n1}
ccol {dots above ddots above dots}
ccol {a sub 1n above vdots above a sub nn}
}
right \] =
LU =
left \[
matrix {
ccol {l sub 11 above vdots above l sub n1}
ccol {dots above ddots above dots}
ccol {0 above vdots above l sub nn}
}
right \]
~
left \[
matrix {
ccol {u sub 11 above vdots above 0}
ccol {dots above ddots above dots}
ccol {u sub 1n above vdots above u sub 22}
}
right \]](/resources/images/9e8c455e03d5bd86e8863d94853c5dc1dcfff51a.svg)
Матрица 
(от англ. «lower» — «нижний») — нижняя треугольная матрица: все элементы, находящиеся строго выше главной диагонали, являются нулями.
Матрица 
(от англ. «upper» — «верхний») — верхняя треугольная матрица: все элементы, находящиеся строго ниже главной диагонали, являются нулями.
Например, для некоторой матрицы 
:
![B sub {(3 times 3)} =
left \[
matrix {
ccol {b sub 11 above b sub 21 above b sub 31}
ccol {b sub 12 above b sub 22 above b sub 32}
ccol {b sub 13 above b sub 23 above b sub 33}
}
right \] =
LU =
left \[
matrix {
ccol {l sub 11 above l sub 21 above l sub 31}
ccol {0 above l sub 22 above l sub 32}
ccol {0 above 0 above l sub 33}
}
right \]
~
left \[
matrix {
ccol {u sub 11 above 0 above 0}
ccol {u sub 12 above u sub 22 above 0}
ccol {u sub 13 above u sub 23 above u sub 33}
}
right \]](/resources/images/2315acbe366f01ddf7b07a298c863e3b5a0cc728.svg)
Нужно отметить, что в данном примере матрица должна быть невырожденной.
Использование LU-разложения
LU-разложение позволяет эффективно выполнять следующие действия:
- Решение систем линейных алгебраических уравнений (СЛАУ) вида
. - Вычисление определителя матрицы :
. - Обращение матрицы :
.
Решение матричных уравнений
Решение СЛАУ вида .
После LU-разложения матрицы можем записать исходное СЛАУ в виде:
Заменив 
получим систему, которую просто можно решить прямым ходом (прямой подстановкой):
Затем, получив решение предыдущего уравнения (
) можем разрешить систему обратным ходом (обратной подстановкой):
В итоге получив искомый вектор 
.
Вычисление определителя
Вычисление определителя матрицы : .
Если 
, то 
.
Определителем любой треугольной матрицы будет произведение ее диагональных элементов, поэтому
Получение обратной матрицы
Обращение матрицы : .
По основному свойству обратной матрицы 
, где 
— единичная матрица.
Разложив матрицу , можем записать:
и решить это СЛАУ тем же способом, что и описанный выше способ решения СЛАУ через LU-разложение.
Реализация метода
Алгоритмическая реализация метода
- Дописать.
Программная реализация метода
- Дописать.
Эффективность метода
Данное разложение является более вычислительно эффективным: как в аспекте алгоритмической сложности, так и в вопросе программной реализации, — чем стандартные методы решения СЛАУ (метод Крамера), вычисления определителей (разложением по строке или по столбцу или рекурсивное вычисление) и обращения матриц (через МетодГаусса? или матрицу алгебраических дополнений).
Необходимо отметить, что LU-разложение может применяться не к любой невырожденной матрице . Если LU-разложение неприменимо, то необходимо использовать РазложениеLUP.
Ограниченность метода
Не всякая невырожденная квадратная матрица может быть разложена с помощью LU-разложения.
- Дописать.
Важные частные случаи
Если матрица является симметрической (т. е. её элементы симметричны относительно главной диагонали) и положительно определенной, то этот частный случай LU-разложения называют РазложениеХолецкого.
Запись LU-разложения будет в этом случае следующей:
, причем 
.
КатегорияЛинейнаяАлгебра | КатегорияПрикладнаяМатематика