LU-разложение
LU-разложение (LU-декомпозиция, LU-факторизация) — представление матрицы в виде произведения двух матриц, , где — нижняя треугольная матрица, а — верхняя треугольная матрица.
LU-разложение используется для решения систем линейных уравнений, обращения матриц и вычисления определителя. LU-разложение существует только в том случае, когда матрица обратима, а все ведущие (угловые) главные миноры матрицы невырождены[1].
Этот метод является одной из разновидностей метода Гаусса.
Применения
Решение систем линейных уравнений
Полученное LU-разложение матрицы (матрица коэффициентов системы) может быть использовано для решения семейства систем линейных уравнений с различными векторами в правой части[2]:
Если известно LU-разложение матрицы , , исходная система может быть записана как
Эта система может быть решена в два шага. На первом шаге решается система
Поскольку — нижняя треугольная матрица, эта система решается непосредственно прямой подстановкой.
На втором шаге решается система
Поскольку — верхняя треугольная матрица, эта система решается непосредственно обратной подстановкой.
Обращение матриц
Обращение матрицы эквивалентно решению линейной системы
- ,
где — неизвестная матрица, — единичная матрица. Решение этой системы является обратной матрицей .
Систему можно решить описанным выше методом LU-разложения.
Вычисление определителя матрицы
Имея LU-разложение матрицы ,
- ,
можно непосредственно вычислить её определитель,
- ,
где — размер матрицы , и — диагональные элементы матриц и .
Вывод формулы
Исходя из области применения, LU-разложение может быть применено только к невырожденной матрице, поэтому далее будем считать что матрица невырождена.
Поскольку и в первой строке матрицы , и в первом столбце матрицы , все элементы, кроме, возможно, первого, равны нулю, имеем
Если , то или . В первом случае целиком состоит из нулей первая строка матрицы , во втором — первый столбец матрицы . Следовательно, или вырождена, а значит, вырождена , что приводит к противоречию. Таким образом, если , то невырожденная матрица не имеет LU-разложения.
Пусть , тогда и . Поскольку столбец L и строка U определены с точностью до умножения строки U на константу и деления столбца L на ту же константу, мы можем потребовать, чтобы . При этом .
Разделим матрицу A на клетки:
- ,
где имеют размерность соответственно , , .
Аналогично разделим на клетки матрицы и :
Уравнение принимает вид
Решая систему уравнений относительно , , , , получаем:
Окончательно имеем:
Итак, мы свели LU-разложение матрицы размера к LU-разложению матрицы размера .
Выражение называется дополнением Шура элемента в матрице A[1].
Алгоритм
Один из алгоритмов для вычисления 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
В итоге мы получим матрицы — и .
См. также
Примечания
- ↑ 1 2 Е. Е. Тыртышников. Матричный анализ и линейная алгебра. — 2004-2005.
- ↑ Левитин, 2006.
- ↑ Вержбицкий В.М. Основы численных методов. Учебник для вузов. — Высшая школа, 2002. — С. 63-64. — ISBN 5-06-004020-8.
Литература
- Ортега Дж. Введение в параллельные и векторные методы решения линейных систем. — М.: Мир, 1991. — 376 с. — ISBN 5-03-001941-3.
- Левитин А. В. Алгоритмы. Введение в разработку и анализ — М.: Вильямс, 2006. — 576 с. — ISBN 978-5-8459-0987-9