LU-разложение
Для улучшения этой статьи желательно:
|
LU-разложение (LU-декомпозиция, LU-факторизация) — представление матрицы в виде произведения двух матриц, , где — нижняя треугольная матрица, а — верхняя треугольная матрица.
LU-разложение используется для решения систем линейных уравнений, обращения матриц и вычисления определителя.
Этот метод является одной из разновидностей метода Гаусса.
Содержание
ПримененияПравить
Решение систем линейных уравненийПравить
Полученное LU-разложение матрицы (матрица коэффициентов системы) может быть использовано для решения семейства систем линейных уравнений с различными векторами в правой части[1]:
Если известно LU-разложение матрицы , , исходная система может быть записана как[1]
Эта система может быть решена в два шага. На первом шаге решается система[1]
Поскольку — нижняя треугольная матрица, эта система решается непосредственно прямой подстановкой.
На втором шаге решается система
Поскольку — верхняя треугольная матрица, эта система решается непосредственно обратной подстановкой.
Обращение матрицПравить
Обращение матрицы эквивалентно решению линейной системы
- ,
где — неизвестная матрица, — единичная матрица. Решение этой системы является обратной матрицей .
Систему можно решить описанным выше методом LU-разложения[1].
Вычисление определителя матрицыПравить
Имея LU-разложение матрицы ,
- ,
можно непосредственно вычислить её определитель,
- ,
где — размер матрицы , и — диагональные элементы матриц и .
Вывод формулыПравить
В силу назначения LU-разложения нас будет интересовать только случай, когда матрица A невырождена.
Поскольку и в первой строке матрицы L, и в первом столбце матрицы U, все элементы, кроме, возможно, первого, равны нулю, имеем
Если , то или . В первом случае целиком состоит из нулей первая строка матрицы L, во втором — первый столбец матрицы U. Следовательно, L или U вырождена, а значит, вырождена A, что противоречит предположению. Таким образом, если , то невырожденная матрица A не имеет LU-разложения.
Пусть , тогда и . Поскольку L и U определены с точностью до умножения U на константу и деления L на ту же константу, мы можем потребовать, чтобы . При этом .
Разделим матрицу A на клетки:
- ,
где имеют размерность соответственно (N-1)×1, 1×(N-1), (N-1)×(N-1). Аналогично разделим на клетки матрицы L и U:
Уравнение
принимает вид
Решая систему уравнений относительно , получаем:
Окончательно имеем:
Итак, мы свели LU-разложение матрицы N×N к LU-разложению матрицы (N-1)×(N-1).
Выражение называется дополнением Шура элемента в матрице A.
Заметим, что — не скаляр, а матрица (N-1)×(N-1).
АлгоритмПравить
В этом разделе не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете отредактировать эту статью, добавив ссылки на авторитетные источники. Эта отметка установлена 12 мая 2011 года. |
Один из алгоритмов для вычисления LU-разложения приведён ниже.
Будем использовать следующие обозначения для элементов матриц , , ; причём диагональные элементы матрицы : , . Тогда, если известно LU-разложение матрицы, её определитель можно вычислить по формуле = произведению элементов на диагонали матрицы U.
Найти матрицы и можно следующим образом (выполнять шаги следует строго по порядку, так как следующие элементы находятся с использованием предыдущих):
Для
В итоге мы получим матрицы — и . В программной реализации данного метода (компактная схема Гаусса) для представления матриц и можно обойтись всего одним массивом, в котором совмещаются матрицы и . Например, так (для матрицы размером ):
См. такжеПравить
ЛитератураПравить
- Ортега Дж. Введение в параллельные и векторные методы решения линейных систем. — М.: Мир, 1991. — 376 с. — ISBN 5-03-001941-3.
- Левитин А. В. Алгоритмы. Введение в разработку и анализ — М.: Вильямс, 2006. — 576 с. — ISBN 978-5-8459-0987-9
- ↑ 1 2 3 4 Левитин, 2006.