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

Поделись знанием:
Перейти к: навигация, поиск

LU-разложение (LU-декомпозиция, LU-факторизация) — представление матрицы <math>A</math> в виде произведения двух матриц, <math>A=LU</math>, где <math>L</math> — нижняя треугольная матрица, а <math>U</math> — трапециевидная матрица.

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

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





Применения

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

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

<math>Ax=b</math>

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

<math>LUx=b .</math>

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

<math>Ly=b .</math>

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

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

<math>Ux=y .</math>

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

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

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

<math>AX=I</math>,

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

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

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

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

<math>A=LU</math>,

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

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

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

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

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

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

<math>a_{11} = l_{11} u_{11}</math>

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

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

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

<math> A =

\begin{pmatrix}

    a_{11} & w^T \\
    v & A' \\

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

<math>

L = \begin{pmatrix}

    1 & 0 \\
    v_l & L' \\

\end{pmatrix},\ U = \begin{pmatrix}

    a_{11} & w_u^T \\
    0 & U' \\

\end{pmatrix} </math> Уравнение

<math>A=LU</math>

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

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

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

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

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

<math>

L = \begin{pmatrix}

    1 & 0 \\
    v/a_{11} & L' \\

\end{pmatrix} </math>

<math> U = \begin{pmatrix}
    a_{11} & w^T \\
    0 & U' \\

\end{pmatrix} </math>

<math>L'U' = A' - v w^T / a_{11}\ </math>

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

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

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

Алгоритм

К:Википедия:Статьи без источников (тип: не указан)

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

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

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

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

Для <math>i = 2\dots n</math>

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

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

<math>\begin{pmatrix}

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

\end{pmatrix} </math>

См. также

Напишите отзыв о статье "LU-разложение"

Литература

  • Ортега Дж. Введение в параллельные и векторные методы решения линейных систем. — М.: Мир, 1991. — 376 с. — ISBN 5-03-001941-3.
  • Ошибка Lua : attempt to index local 'entity' (a nil value).
  1. 1 2 3 4 Левитин, 2006.

Отрывок, характеризующий LU-разложение

В Ольмюце он не застал в этот день князя Андрея. Но вид Ольмюца, где стояла главная квартира, дипломатический корпус и жили оба императора с своими свитами – придворных, приближенных, только больше усилил его желание принадлежать к этому верховному миру.
Он никого не знал, и, несмотря на его щегольской гвардейский мундир, все эти высшие люди, сновавшие по улицам, в щегольских экипажах, плюмажах, лентах и орденах, придворные и военные, казалось, стояли так неизмеримо выше его, гвардейского офицерика, что не только не хотели, но и не могли признать его существование. В помещении главнокомандующего Кутузова, где он спросил Болконского, все эти адъютанты и даже денщики смотрели на него так, как будто желали внушить ему, что таких, как он, офицеров очень много сюда шляется и что они все уже очень надоели. Несмотря на это, или скорее вследствие этого, на другой день, 15 числа, он после обеда опять поехал в Ольмюц и, войдя в дом, занимаемый Кутузовым, спросил Болконского. Князь Андрей был дома, и Бориса провели в большую залу, в которой, вероятно, прежде танцовали, а теперь стояли пять кроватей, разнородная мебель: стол, стулья и клавикорды. Один адъютант, ближе к двери, в персидском халате, сидел за столом и писал. Другой, красный, толстый Несвицкий, лежал на постели, подложив руки под голову, и смеялся с присевшим к нему офицером. Третий играл на клавикордах венский вальс, четвертый лежал на этих клавикордах и подпевал ему. Болконского не было. Никто из этих господ, заметив Бориса, не изменил своего положения. Тот, который писал, и к которому обратился Борис, досадливо обернулся и сказал ему, что Болконский дежурный, и чтобы он шел налево в дверь, в приемную, коли ему нужно видеть его. Борис поблагодарил и пошел в приемную. В приемной было человек десять офицеров и генералов.
В то время, как взошел Борис, князь Андрей, презрительно прищурившись (с тем особенным видом учтивой усталости, которая ясно говорит, что, коли бы не моя обязанность, я бы минуты с вами не стал разговаривать), выслушивал старого русского генерала в орденах, который почти на цыпочках, на вытяжке, с солдатским подобострастным выражением багрового лица что то докладывал князю Андрею.
– Очень хорошо, извольте подождать, – сказал он генералу тем французским выговором по русски, которым он говорил, когда хотел говорить презрительно, и, заметив Бориса, не обращаясь более к генералу (который с мольбою бегал за ним, прося еще что то выслушать), князь Андрей с веселой улыбкой, кивая ему, обратился к Борису.
Борис в эту минуту уже ясно понял то, что он предвидел прежде, именно то, что в армии, кроме той субординации и дисциплины, которая была написана в уставе, и которую знали в полку, и он знал, была другая, более существенная субординация, та, которая заставляла этого затянутого с багровым лицом генерала почтительно дожидаться, в то время как капитан князь Андрей для своего удовольствия находил более удобным разговаривать с прапорщиком Друбецким. Больше чем когда нибудь Борис решился служить впредь не по той писанной в уставе, а по этой неписанной субординации. Он теперь чувствовал, что только вследствие того, что он был рекомендован князю Андрею, он уже стал сразу выше генерала, который в других случаях, во фронте, мог уничтожить его, гвардейского прапорщика. Князь Андрей подошел к нему и взял за руку.
– Очень жаль, что вчера вы не застали меня. Я целый день провозился с немцами. Ездили с Вейротером поверять диспозицию. Как немцы возьмутся за аккуратность – конца нет!
Борис улыбнулся, как будто он понимал то, о чем, как об общеизвестном, намекал князь Андрей. Но он в первый раз слышал и фамилию Вейротера и даже слово диспозиция.
– Ну что, мой милый, всё в адъютанты хотите? Я об вас подумал за это время.
– Да, я думал, – невольно отчего то краснея, сказал Борис, – просить главнокомандующего; к нему было письмо обо мне от князя Курагина; я хотел просить только потому, – прибавил он, как бы извиняясь, что, боюсь, гвардия не будет в деле.
– Хорошо! хорошо! мы обо всем переговорим, – сказал князь Андрей, – только дайте доложить про этого господина, и я принадлежу вам.
В то время как князь Андрей ходил докладывать про багрового генерала, генерал этот, видимо, не разделявший понятий Бориса о выгодах неписанной субординации, так уперся глазами в дерзкого прапорщика, помешавшего ему договорить с адъютантом, что Борису стало неловко. Он отвернулся и с нетерпением ожидал, когда возвратится князь Андрей из кабинета главнокомандующего.
– Вот что, мой милый, я думал о вас, – сказал князь Андрей, когда они прошли в большую залу с клавикордами. – К главнокомандующему вам ходить нечего, – говорил князь Андрей, – он наговорит вам кучу любезностей, скажет, чтобы приходили к нему обедать («это было бы еще не так плохо для службы по той субординации», подумал Борис), но из этого дальше ничего не выйдет; нас, адъютантов и ординарцев, скоро будет батальон. Но вот что мы сделаем: у меня есть хороший приятель, генерал адъютант и прекрасный человек, князь Долгоруков; и хотя вы этого можете не знать, но дело в том, что теперь Кутузов с его штабом и мы все ровно ничего не значим: всё теперь сосредоточивается у государя; так вот мы пойдемте ка к Долгорукову, мне и надо сходить к нему, я уж ему говорил про вас; так мы и посмотрим; не найдет ли он возможным пристроить вас при себе, или где нибудь там, поближе .к солнцу.