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

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

LU-разложение — представление матрицы A в виде произведения двух матриц, A=LU, где L — нижняя треугольная матрица, а U — верхняя треугольная матрица. LU-разложение еще называют LU-факторизацией.

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

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

Содержание

Применения

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

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

Ax=b ,

где A — матрица коэффициентов системы, x — вектор неизвестных величин системы, b — вектор правых частей системы.

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

LUx=b .

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

Ly=b .

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

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

Ux=y .

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

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

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

AX=I,

где X — неизвестная матрица, I — единичная матрица. Решение X этой системы является обратной матрицей A^{-1}.

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

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

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

A=LU,

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

\det(A)=\det(LU)=\det(L)\det(U)=\left( \prod_{i=1}^n L_{ii} \right)  \left( \prod_{i=1}^n U_{ii} \right),

где n — размер матрицы A, L_{ii} и U_{ii} — диагональные элементы матриц L и U.

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

В силу назначения LU-разложения нас будет интересовать только случай, когда матрица A невырождена.

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

a_{11} = l_{11} u_{11}

Если a_{11} = 0, то l_{11} = 0 или u_{11} = 0. В первом случае целиком состоит из нулей первая строка матрицы L, во втором — первый столбец матрицы U. Следовательно, L или U вырождена, а значит, вырождена A, что противоречит предположению. Таким образом, если a_{11} = 0, то невырожденная матрица A не имеет LU-разложения.

Пусть a_{11} \ne 0, тогда l_{11} \ne 0 и u_{11} \ne 0. Поскольку L и U определены с точностью до умножения U на константу и деления L на ту же константу, мы можем потребовать, чтобы l_{11} = 1. При этом u_{11} = a_{11}.

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

 A = 
\begin{pmatrix}
     a_{11} & w^T \\
     v & A' \\
\end{pmatrix}
,

где v, w^T, A' имеют размерность соответственно (N-1)×1, 1×(N-1), (N-1)×(N-1). Аналогично разделим на клетки матрицы L и U:


L = \begin{pmatrix}
     1 & 0 \\
     v_l & L' \\
\end{pmatrix},\ 
U = \begin{pmatrix}
     a_{11} & w_u^T \\
     0 & U' \\
\end{pmatrix}

Уравнение

A=LU

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

w^T=w^T_u\
v=a_{11}v_l\
A' = v_l w_u^T + L' U'

Решая систему уравнений относительно v_l, w_u, L', U'\ , получаем:

w_u = w\
v_l = v / a_{11}\
L'U' = A' - v w^T / a_{11}\

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


L = \begin{pmatrix}
     1 & 0 \\
     v/a_{11} & L' \\
\end{pmatrix}
 U = \begin{pmatrix}
     a_{11} & w^T \\
     0 & U' \\
\end{pmatrix}
L'U' = A' - v w^T / a_{11}\

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

Выражение A' - v w^T / a_{11} называется дополнением Шура элемента a_{11} в матрице A.

Заметим, что  v w^T \  — не скаляр, а матрица (N-1)×(N-1).

Алгоритм

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

Будем использовать следующие обозначения для элементов матриц L=(l_{ij}), U=(u_{ij}), i,j = 1\dots n; причём диагональные элементы матрицы L: l_{ii} = 1, i = 1\dots n. Тогда, если известно LU-разложение матрицы, её определитель можно вычислить по формуле \det(A) = \det(LU) = \det(L) \det(U) = \det(U) = произведению элементов на диагонали матрицы U.

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

  1. u_{1j} = a_{1j},\ j = 1\dots n
  2. l_{j1} = \frac {a_{j1}} {u_{11}},\  j = 2\dots n\  (l_{11} \ne 0)

Для i = 2\dots n

  1. u_{ij} = a_{ij} - \sum_{k=1}^{i-1} l_{ik}u_{kj},\  j = i\dots n
  2. l_{ji} = \frac {1} {u_{ii}}(a_{ji} - \sum_{k=1}^{i-1} l_{jk}u_{ki}),\  j = i+1\dots n

В итоге мы получим матрицы — L и U. В программной реализации данного метода (компактная схема Гаусса) для представления матриц L и U можно обойтись всего одним массивом, в котором совмещаются матрицы L и U. Например, так (для матрицы размером 3\times 3):

\begin{pmatrix}
  u_{11} & u_{12} & u_{13} \\
  l_{21} & u_{22} & u_{23} \\
  l_{31} & l_{32} & u_{33} \\
\end{pmatrix}

См. также

Литература

  • Ортега Дж. Введение в параллельные и векторные методы решения линейных систем. — М.: Мир, 1991. — 376 с. — ISBN 5-03-001941-3

Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Полезное


Смотреть что такое "LU-разложение" в других словарях:

  • РАЗЛОЖЕНИЕ — РАСПАД И РАЗЛОЖЕНИЕ В словарь общерусского литературного языка впиталось много научных и специальных терминов. Выйдя за пределы профессиональной речи, эти термины расширяют свои значения и вовлекаются в новые фразеологические контексты.… …   История слов

  • РАЗЛОЖЕНИЕ — РАЗЛОЖЕНИЕ, разложения, мн. нет, ср. (книжн.). 1. Действие по гл. разложить в 6, 7 и 8 знач. разлагать. Разложение воды на составные части. Разложение множителя. Разложение окиси на ртуть и кислород. Разложение армии врага. 2. Состояние по гл.… …   Толковый словарь Ушакова

  • разложение — См. испытание …   Словарь синонимов

  • РАЗЛОЖЕНИЕ — • РАЗЛОЖЕНИЕ, в биологии естественная деградация органического вещества с образованием более простых веществ, например, углекислого газа и воды. Разложение обычно является результатом деятельности таких организмов, как бактерии и грибки. За счет… …   Научно-технический энциклопедический словарь

  • разложение в ряд Фурье — преобразование в ряд Фурье гармоническое разложение — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Тематики информационные технологии в целом Синонимы преобразование в ряд Фурьегармоническое… …   Справочник технического переводчика

  • разложение по степеням — разложение в ряд — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Тематики информационные технологии в целом Синонимы разложение в ряд EN power expansion …   Справочник технического переводчика

  • разложение Карунена-Лоэва — Представление случайного процесса второго порядка в виде суперпозиции ряда детерминированных функций, причем коэффициенты такого разложения являются взаимно некоррелированными случайными переменными. Данное разложение широко используется в теории …   Справочник технического переводчика

  • разложение на множители — Разложение целого числа на его наибольшие сомножители (главные факторы). [http://www.rfcmd.ru/glossword/1.8/index.php?a=index d=23] Тематики защита информации EN factoring …   Справочник технического переводчика

  • разложение — 1. Разложение органического вещества на его более простые составляющие. 2. Ослабление и разрушение горных пород вследствие химического выветривания. Syn.: распад …   Словарь по географии

  • РАЗЛОЖЕНИЕ НА МНОЖИТЕЛИ — многочлена представление его в виде произведения двух или большего числа многочленов низших степеней. Напр.: х2 1 = (х 1)(х + 1) …   Большой Энциклопедический словарь

  • РАЗЛОЖЕНИЕ СИЛЫ — замена одной силы, приложенной к телу, системой сил, производящей такое же механическое воздействие на тело, как и данная сила …   Большой Энциклопедический словарь


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»