LU-разложение
<imagemap>: неверное или отсутствующее изображение |
Для улучшения этой статьи желательно?:
|
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).
Алгоритм
<imagemap>: неверное или отсутствующее изображение |
В этом разделе не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена.
Вы можете отредактировать эту статью, добавив ссылки на авторитетные источники. Эта отметка установлена 12 мая 2011 года. |
Один из алгоритмов для вычисления 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> можно следующим образом (выполнять шаги следует строго по порядку, так как следующие элементы находятся с использованием предыдущих):
- <math>u_{1j} = a_{1j},\ j = 1\dots n </math>
- <math>l_{j1} = \frac {a_{j1}} {u_{11}},\ j = 2\dots n\ (u_{11} \ne 0) </math>
Для <math>i = 2\dots n</math>
- <math>u_{ij} = a_{ij} - \sum_{k=1}^{i-1} l_{ik}u_{kj},\ j = i\dots n </math>
- <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 2 3 4 Левитин, 2006.
Отрывок, характеризующий LU-разложение
В Ольмюце он не застал в этот день князя Андрея. Но вид Ольмюца, где стояла главная квартира, дипломатический корпус и жили оба императора с своими свитами – придворных, приближенных, только больше усилил его желание принадлежать к этому верховному миру.Он никого не знал, и, несмотря на его щегольской гвардейский мундир, все эти высшие люди, сновавшие по улицам, в щегольских экипажах, плюмажах, лентах и орденах, придворные и военные, казалось, стояли так неизмеримо выше его, гвардейского офицерика, что не только не хотели, но и не могли признать его существование. В помещении главнокомандующего Кутузова, где он спросил Болконского, все эти адъютанты и даже денщики смотрели на него так, как будто желали внушить ему, что таких, как он, офицеров очень много сюда шляется и что они все уже очень надоели. Несмотря на это, или скорее вследствие этого, на другой день, 15 числа, он после обеда опять поехал в Ольмюц и, войдя в дом, занимаемый Кутузовым, спросил Болконского. Князь Андрей был дома, и Бориса провели в большую залу, в которой, вероятно, прежде танцовали, а теперь стояли пять кроватей, разнородная мебель: стол, стулья и клавикорды. Один адъютант, ближе к двери, в персидском халате, сидел за столом и писал. Другой, красный, толстый Несвицкий, лежал на постели, подложив руки под голову, и смеялся с присевшим к нему офицером. Третий играл на клавикордах венский вальс, четвертый лежал на этих клавикордах и подпевал ему. Болконского не было. Никто из этих господ, заметив Бориса, не изменил своего положения. Тот, который писал, и к которому обратился Борис, досадливо обернулся и сказал ему, что Болконский дежурный, и чтобы он шел налево в дверь, в приемную, коли ему нужно видеть его. Борис поблагодарил и пошел в приемную. В приемной было человек десять офицеров и генералов.
В то время, как взошел Борис, князь Андрей, презрительно прищурившись (с тем особенным видом учтивой усталости, которая ясно говорит, что, коли бы не моя обязанность, я бы минуты с вами не стал разговаривать), выслушивал старого русского генерала в орденах, который почти на цыпочках, на вытяжке, с солдатским подобострастным выражением багрового лица что то докладывал князю Андрею.
– Очень хорошо, извольте подождать, – сказал он генералу тем французским выговором по русски, которым он говорил, когда хотел говорить презрительно, и, заметив Бориса, не обращаясь более к генералу (который с мольбою бегал за ним, прося еще что то выслушать), князь Андрей с веселой улыбкой, кивая ему, обратился к Борису.
Борис в эту минуту уже ясно понял то, что он предвидел прежде, именно то, что в армии, кроме той субординации и дисциплины, которая была написана в уставе, и которую знали в полку, и он знал, была другая, более существенная субординация, та, которая заставляла этого затянутого с багровым лицом генерала почтительно дожидаться, в то время как капитан князь Андрей для своего удовольствия находил более удобным разговаривать с прапорщиком Друбецким. Больше чем когда нибудь Борис решился служить впредь не по той писанной в уставе, а по этой неписанной субординации. Он теперь чувствовал, что только вследствие того, что он был рекомендован князю Андрею, он уже стал сразу выше генерала, который в других случаях, во фронте, мог уничтожить его, гвардейского прапорщика. Князь Андрей подошел к нему и взял за руку.
– Очень жаль, что вчера вы не застали меня. Я целый день провозился с немцами. Ездили с Вейротером поверять диспозицию. Как немцы возьмутся за аккуратность – конца нет!
Борис улыбнулся, как будто он понимал то, о чем, как об общеизвестном, намекал князь Андрей. Но он в первый раз слышал и фамилию Вейротера и даже слово диспозиция.
– Ну что, мой милый, всё в адъютанты хотите? Я об вас подумал за это время.
– Да, я думал, – невольно отчего то краснея, сказал Борис, – просить главнокомандующего; к нему было письмо обо мне от князя Курагина; я хотел просить только потому, – прибавил он, как бы извиняясь, что, боюсь, гвардия не будет в деле.
– Хорошо! хорошо! мы обо всем переговорим, – сказал князь Андрей, – только дайте доложить про этого господина, и я принадлежу вам.
В то время как князь Андрей ходил докладывать про багрового генерала, генерал этот, видимо, не разделявший понятий Бориса о выгодах неписанной субординации, так уперся глазами в дерзкого прапорщика, помешавшего ему договорить с адъютантом, что Борису стало неловко. Он отвернулся и с нетерпением ожидал, когда возвратится князь Андрей из кабинета главнокомандующего.
– Вот что, мой милый, я думал о вас, – сказал князь Андрей, когда они прошли в большую залу с клавикордами. – К главнокомандующему вам ходить нечего, – говорил князь Андрей, – он наговорит вам кучу любезностей, скажет, чтобы приходили к нему обедать («это было бы еще не так плохо для службы по той субординации», подумал Борис), но из этого дальше ничего не выйдет; нас, адъютантов и ординарцев, скоро будет батальон. Но вот что мы сделаем: у меня есть хороший приятель, генерал адъютант и прекрасный человек, князь Долгоруков; и хотя вы этого можете не знать, но дело в том, что теперь Кутузов с его штабом и мы все ровно ничего не значим: всё теперь сосредоточивается у государя; так вот мы пойдемте ка к Долгорукову, мне и надо сходить к нему, я уж ему говорил про вас; так мы и посмотрим; не найдет ли он возможным пристроить вас при себе, или где нибудь там, поближе .к солнцу.