LU-разложение

LU-разложение (LU-декомпозиция, LU-факторизация) — представление матрицы в виде произведения двух матриц, , где  — нижняя треугольная матрица, а  — верхняя треугольная матрица.

LU-разложение используется для решения систем линейных уравнений, обращения матриц и вычисления определителя. LU-разложение существует только в том случае, когда матрица обратима, а все главные миноры матрицы невырождены[1].

Этот метод является одной из разновидностей метода Гаусса.

Применения

Решение систем линейных уравнений

Полученное LU-разложение матрицы   (матрица коэффициентов системы) может быть использовано для решения семейства систем линейных уравнений с различными векторами   в правой части[2]:

 

Если известно LU-разложение матрицы  ,  , исходная система может быть записана как

 

Эта система может быть решена в два шага. На первом шаге решается система

 

Поскольку   — нижняя треугольная матрица, эта система решается непосредственно прямой подстановкой.

На втором шаге решается система

 

Поскольку   — верхняя треугольная матрица, эта система решается непосредственно обратной подстановкой.

Обращение матриц

Обращение матрицы   эквивалентно решению линейной системы

 ,

где   — неизвестная матрица,   — единичная матрица. Решение   этой системы является обратной матрицей  .

Систему можно решить описанным выше методом LU-разложения.

Вычисление определителя матрицы

Имея LU-разложение матрицы  ,

 ,

можно непосредственно вычислить её определитель,

 ,

где   — размер матрицы  ,   и   — диагональные элементы матриц   и  .

Вывод формулы

Исходя из области применения LU-разложение может быть применено только к невырожденной матрице, поэтому далее будем считать что матрица   невырождена.

Поскольку и в первой строке матрицы  , и в первом столбце матрицы  , все элементы, кроме, возможно, первого, равны нулю, имеем

 

Если  , то   или  . В первом случае целиком состоит из нулей первая строка матрицы  , во втором — первый столбец матрицы  . Следовательно,   или   вырождена, а значит, вырождена  , что приводит к противоречию. Таким образом, если  , то невырожденная матрица   не имеет LU-разложения.

Пусть  , тогда   и  . Поскольку L и U определены с точностью до умножения U на константу и деления L на ту же константу, мы можем потребовать, чтобы  . При этом  .

Разделим матрицу A на клетки:

 ,

где   имеют размерность соответственно  ,  ,  .

Аналогично разделим на клетки матрицы   и  :

 

Уравнение   принимает вид

 
 
 

Решая систему уравнений относительно  ,  ,  ,  , получаем:

 
 
 

Окончательно имеем:

 
 
 

Итак, мы свели LU-разложение матрицы размера   к LU-разложению матрицы размера  .

Выражение   называется дополнением Шура элемента   в матрице A[1].

Алгоритм

Один из алгоритмов для вычисления LU-разложения приведён ниже.

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

 

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

  1.  
  2.  

Для  

  1.  
  2.  

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

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

 

См. также

Примечания

  1. 1 2 Е. Е. Тыртышников. Матричный анализ и линейная алгебра. — 2004-2005.
  2. Левитин, 2006.

Литература