Лучшие вопросы
Таймлайн
Чат
Перспективы
LU-разложение
представление в виде произведения нижней и верхней треугольной матрицы Из Википедии, свободной энциклопедии
Remove ads
LU-разложение (LU-декомпозиция, LU-факторизация) — представление матрицы в виде произведения двух матриц, , где — нижняя треугольная матрица, а — верхняя треугольная матрица.
![]() | Для улучшения этой статьи желательно: |
LU-разложение используется для решения систем линейных уравнений, обращения матриц и вычисления определителя. LU-разложение существует только в том случае, когда матрица обратима, а все ведущие (угловые) главные миноры матрицы невырождены[1].
Этот метод является одной из разновидностей метода Гаусса.
Remove ads
Применения
Суммиров вкратце
Перспектива
Решение систем линейных уравнений
Полученное LU-разложение матрицы (матрица коэффициентов системы) может быть использовано для решения семейства систем линейных уравнений с различными векторами в правой части[2]:
Если известно LU-разложение матрицы , , исходная система может быть записана как
Эта система может быть решена в два шага. На первом шаге решается система
Поскольку — нижняя треугольная матрица, эта система решается непосредственно прямой подстановкой.
На втором шаге решается система
Поскольку — верхняя треугольная матрица, эта система решается непосредственно обратной подстановкой.
Обращение матриц
Обращение матрицы эквивалентно решению линейной системы
- ,
где — неизвестная матрица, — единичная матрица. Решение этой системы является обратной матрицей .
Систему можно решить описанным выше методом LU-разложения.
Вычисление определителя матрицы
Имея LU-разложение матрицы ,
- ,
можно непосредственно вычислить её определитель,
- ,
где — размер матрицы , и — диагональные элементы матриц и .
Remove ads
Вывод формулы
Суммиров вкратце
Перспектива
Исходя из области применения, LU-разложение может быть применено только к невырожденной матрице, поэтому далее будем считать что матрица невырождена.
Поскольку и в первой строке матрицы , и в первом столбце матрицы , все элементы, кроме, возможно, первого, равны нулю, имеем
Если , то или . В первом случае целиком состоит из нулей первая строка матрицы , во втором — первый столбец матрицы . Следовательно, или вырождена, а значит, вырождена , что приводит к противоречию. Таким образом, если , то невырожденная матрица не имеет LU-разложения.
Пусть , тогда и . Поскольку столбец L и строка U определены с точностью до умножения строки U на константу и деления столбца L на ту же константу, мы можем потребовать, чтобы . При этом .
Разделим матрицу A на клетки:
- ,
где имеют размерность соответственно , , .
Аналогично разделим на клетки матрицы и :
Уравнение принимает вид
Решая систему уравнений относительно , , , , получаем:
Окончательно имеем:
Итак, мы свели LU-разложение матрицы размера к LU-разложению матрицы размера .
Выражение называется дополнением Шура элемента в матрице A[1].
Remove ads
Алгоритм
Суммиров вкратце
Перспектива
Один из алгоритмов для вычисления LU-разложения приведён ниже.[3]
Будем использовать следующие обозначения для элементов матриц: , , , ; причём диагональные элементы матрицы : , .
Найти матрицы и можно следующим образом (выполнять шаги следует строго по порядку, так как следующие элементы находятся с использованием предыдущих):
- Цикл i от 1 до n
- Цикл j от 1 до n
- uij=0, lij=0
- lii=1
- Цикл j от 1 до n
- Цикл i от 1 до n
- Цикл j от 1 до n
- Если i<=j:
- Если i>j:
- Цикл j от 1 до n
В итоге мы получим матрицы — и .
Remove ads
См. также
Примечания
Литература
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads