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]

Будем использовать следующие обозначения для элементов матриц: , , , ; причём диагональные элементы матрицы : , .

Найти матрицы и можно следующим образом (выполнять шаги следует строго по порядку, так как следующие элементы находятся с использованием предыдущих):

  1. Цикл i от 1 до n
    1. Цикл j от 1 до n
      1. uij=0, lij=0
      2. lii=1
  2. Цикл i от 1 до n
    1. Цикл j от 1 до n
      1. Если i<=j:
      2. Если i>j:

В итоге мы получим матрицы — и .

См. также

Примечания

  1. Е. Е. Тыртышников. Матричный анализ и линейная алгебра. — 2004-2005.
  2. Левитин, 2006.
  3. Вержбицкий В.М. Основы численных методов. Учебник для вузов. — Высшая школа, 2002. — С. 63-64. — ISBN 5-06-004020-8.

Литература

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.