LU декомпозиција

У линеарној алгебри, LU декомпозиција или LU факторизација (од енглеских речи lower - доње и upper - горње) је декомпозиција матрице која записује матрицу као производ доње троугаоне и горње троугаоне матрице. Производ некада укључује и пермутациону матрицу. Ова декомпозиција се користи у нумеричкој анализи да се реши систем линеарних једначина или да се израчуна детерминанта матрице. LU декомпозиција семоже сматрати и као матрични облик Гаусове елиминације. LU декомпозицију је увео Алан Тјуринг.

Дефиниција

Нека је A квадратна матрица. LU декомпозиција је декомпозиција облика

$A=LU,\,$

где су L и U доње и горње троугаоне матрице истих димензија. То значи да L има нуле само изнад главне дијагонале, док U има нуле испод главне дијагонале. За матрицу $3\times 3$ , ово постаје:

${\begin{bmatrix}a_{11}&a_{12}&a_{13}\\a_{21}&a_{22}&a_{23}\\a_{31}&a_{32}&a_{33}\\\end{bmatrix}}={\begin{bmatrix}l_{11}&0&0\\l_{21}&l_{22}&0\\l_{31}&l_{32}&l_{33}\\\end{bmatrix}}{\begin{bmatrix}u_{11}&u_{12}&u_{13}\\0&u_{22}&u_{23}\\0&0&u_{33}\\\end{bmatrix}}.$

LDU декомпозиција Волшове матрице

LDU декомпозиција је докомпозиција облика

$A=LDU,\,$

где је D дијагонална матрица а L и U су јединичне троугаоне матрице, што значи да су све вредности на главним дијагоналама L и U једнаке јединици.

LUP декомпозиција (такође се назива LU декомпозиција са парцијалним пивотирањем) је декомпозиција облика

$PA=LU,\,$

где су L и U опет доње и горње троугаоне матрице, а P је пермутациона матрица, тј, матрица од нула и јединица где се налази тачно једна јединица у свакој врсти и колони.

LU декомпозиција са потпуним пивотирање је облика

$PAQ=LU,\,$

Горе је претпостављено да је A квадратна матрица, али ове декомпозиције се могу генералзизовати и на правоугаоне матрице. У том случају, L и P су квадратне матрице које имају исти број врста као и A, док је U истог облика као A. Горња троугаона форма се интерпетира као постојање нултих елемената испод главне дијагонале, која почиње у горњем левом углу.

Постојање и јединственост

Регуларна матрица дозвољава LU факторизацију ако и само ако су сви њени водећи главни минори различити од нуле. Факторизација је јединствена ако захтевамо да се дијагонале од L (или U) састоје од јединица. Матрица има јединствену LDU факторизацију под истим условима.

Ако је матрица сингуларна, LU факторизација може опет постојати. Заправо, квадратна матрица ранга k има LU факторизацију ако је k главних водећих минора различит од нуле, мада не важи обрнуто.

Довољни и потребни услови под којима нека не обавезно регуларна матрица над неким пољем има LU су познати. Ови услови су изражени преко ранга одређених подматрица. Гаусов елиминациони алгоритам за добијање LU факторизације је такође проширен на овај најопштији случајOkunev & Johnson 1997.

Свака регуларна матрица дозвољава LUP факторизацију.

Позитивнo дефинитне матрице

Ако је матрица A самоајдунгована и позитивно-дефинититна, онда можемо да организовати ствари тако да је U коњуговани транспонент од L. У том случају, можемо написати A као

$A=LL^{*}.\,$

Ова декомпозиција се назива метод Холеског. Метод Холеског увек постоји и јединствен је. Даље, рачунањем метода Холекског је ефикасније и нумерички стабилније од рачунања неких других LU декомпозиција.

Експлицитна формулација

Када постоји LDU факторизација и када је она јединствена, тада постоји затоврена (експлицинта формула) за елементе матрица L, D, и U у виду количника детерминанти одређених подматрица оригиналне матрице A (Householder 1975). На пример, $D_{1}=A_{1,1}$ и за $i=2,\ldots ,n$, $D_{i}$ је количник $i$-те главне подматрице и $(i-1)$-те главне подматрице.

Алгоритми

LU декомпозиција је у основи модификовани облик Гаусове елиминације. Матрица A се трансформише у горњу троугаону матрицу U елиминисањем вредности испод главне дијагонале. Дулитлов алгоритам врши елиминацију колоне по колоне, идући са лева, множењем A са леве стране атомском доњем троугаоном матрицом. Резултат овога је јединична доња троугаона матрица и горња троугаона матрица. Крутов алгиритам је мало другачији и даје доњу троугаону матрицу и јединичну горњу троугаону матрицу.

Рачунање LU факторизације коришћењем било ког од ова два алгоритма захтева 2n³ / 3 операција са покретним зарезом, ако се игноришу терми нижег реда. Парцијално пивотирање додаје само квадратни терм; ово није случај код пуног пивотирања.

Дулитлов алгоритам

Ако имамо матрицу диманзијаN × N

$A=(a_{n,n})$

дефинишемо почетно стање

$A^{(0)}:=A$

и затим следи n итерација (n = 1,...,N-1).

Елементи матрице испод главне дијагонале у n-ој колони од A^(n-1) се елиминишу сабирањем i-те врсте ове матрице помножене са

$l_{i,n}:=-{\frac {a_{i,n}^{(n-1)}}{a_{n,n}^{(n-1)}}}$

за $i=n+1,\ldots ,N$. Ово се може урадити множењем A^(n-1) са доњом троугаоном матрицом

$L_{n}={\begin{pmatrix}1&&&&&0\\&\ddots &&&&\\&&1&&&\\&&l_{n+1,n}&\ddots &&\\&&\vdots &&\ddots &\\0&&l_{N,n}&&&1\\\end{pmatrix}}.$

Одређујемо

$A^{(n)}:=L_{n}A^{(n-1)}.$

После N-1 корака, елиминисани су сви елементи матрице испод главне дијагонале, па се добија горња троугаона матрица A^(N-1). Добија се факторизација

$A=L_{1}^{-1}L_{1}A^{(0)}=L_{1}^{-1}A^{(1)}=L_{1}^{-1}L_{2}^{-1}L_{2}A^{(1)}=L_{1}^{-1}L_{2}^{-1}A^{(2)}=\ldots =L_{1}^{-1}\ldots L_{N-1}^{-1}A^{(N-1)}.$

Ако се горња троугаона матрица A^(N-1) означи са U, и $L=L_{1}^{-1}\ldots L_{N-1}^{-1}$. Пошто је инверзна вредност доње троугаоне матрице L_n опет доња троугаона матрица, а производ две доње троугаоне матрице је опет доња троугаона матрица, добија се да је L такође доња троугана матрица. Штавише, може се видети да је

$L={\begin{pmatrix}1&&&&&0\\-l_{2,1}&\ddots &&&&\\&&1&&&\\\vdots &&-l_{n+1,n}&\ddots &&\\&&\vdots &&1&\\-l_{N,1}&&-l_{N,n}&&-l_{N,N-1}&1\\\end{pmatrix}}.$

Добијамо $A=LU$.

Јасно је да би овај алгоритам правилно радио, потребно је имати $a_{n,n}^{(n-1)}\not =0$ у сваком кораку (погледати дефиницију $l_{i,n}$). Ако овај услов није задовољен у неком тренутку, само је потребно заманити n-ту врсту са другом врстом испод ње пре него што алгоритам настави даље. То је разлог зашто LU декомпозиција у општен случају пише као $P^{-1}A=LU$.

Крутов и LUP алгоритми

LUP факторизациони алгоритам уопштава Крутову декомпозицију матрице. Може се описати у следећим корацима.

1. Ако $A$ има ненулти елемент у својој првој врсти, онда узети пермутациону матрицу $P_{1}$ тако да $AP_{1}$ има ненулти елемнет у свом горњем левом углу. У супротном случају, за $P_{1}$ се узима јединична матрица. Нека је $A_{1}=AP_{1}$.
2. Нека је $A_{2}$ матрица која се добија од матрице $A_{1}$ брисањем прве врсте и прве колоне. Факторизовати $A_{2}=L_{2}U_{2}P_{2}$ рекурзивно. Добити $L$ од $L_{2}$ прво додавњем нултог реда горе, а затим додавањем прве колоне $A_{1}$ слева.
3. Добити $U_{3}$ од $U_{2}$ прво додавањем нулте колоне горе и нулте колоне са лева, а затим замењивањем горње леве вредности (која је једнака 0 у овом тренуткуt) јединицом. Добити $P_{3}$ од $P_{2}$ на сличан начин и дефинисати $A_{3}=A_{1}/P_{3}=AP_{1}/P_{3}$. Нека је $P$ инверзна матрица $P_{1}/P_{3}$.
4. У овом тренутку, $A_{3}$ је исто као и $LU_{3}$, осим (можда) у првој врсти. Ако је прва врста $A$ једнака нули, онда $A_{3}=LU_{3}$, пошто обе имају нулту прву колону, а $A=LU_{3}P$ следо, као жељено. У супротном случају, $A_{3}$ и $LU_{3}$ имају исте ненулте вредности у горњем левом углу, и $A_{3}=LU_{3}U_{1}$ за неку горње-троугаону квадратну матрицу $U_{1}$ са јединицама на дијагонали ($U_{1}$ брише елементе $LU_{3}$ и додаје елементе $A_{3}$ помоћу горњег левог угла). Сада је $A=LU_{3}U_{1}P$ декомпозиција жељеног облика.

Теоријска сложеност

Ако се две матрице реда n могу помножити за време M(n), где је M(n)≥n^a за неко a>2, онда се LU декомпозиција може израчунати за време O(M(n)). Ово на пример значи да O(n^2.376) алгоритам постоји заснован на Коперсмит-Виноградовом алгоритму.

Пример

${\begin{bmatrix}4&3\\6&3\\\end{bmatrix}}={\begin{bmatrix}l_{11}&0\\l_{21}&l_{22}\\\end{bmatrix}}{\begin{bmatrix}u_{11}&u_{12}\\0&u_{22}\\\end{bmatrix}}.$

Један начин за проналажење LU факторизације ове просте матрице је да се просто инспекцијом реше линеарне једначине. Из операције множења матрица добија се:

$l_{11}\cdot u_{11}+0\cdot 0=4$

$l_{11}\cdot u_{12}+0\cdot u_{22}=3$

$l_{21}\cdot u_{11}+l_{22}\cdot 0=6$

$l_{21}\cdot u_{12}+l_{22}\cdot u_{22}=3.$

Такав ситем једначина је неодређен. У овом случају било који од два ненулта елемента матрица L и U су параметри решења и могу се произвољно поставити на неку ненулту вредност. Стога, да би нашли јединствену LU факторизацију, неопходно је да се поставе нека ограничења на матрице L и U. На пример, можемо захтевати да је доња троугаона матрица L јединична (има све јединице на главној дијагонали). Онда систем једначина има следећа решења:

$l_{21}=1.5$

$u_{11}=4$

$u_{12}=3$

$u_{22}=-1.5.$

Заменов ових вередности у LU декомпозицију изнад добијамо:

${\begin{bmatrix}4&3\\6&3\\\end{bmatrix}}={\begin{bmatrix}1&0\\1.5&1\\\end{bmatrix}}{\begin{bmatrix}4&3\\0&-1.5\\\end{bmatrix}}.$

Факторизација ретких матрица

Развијени су специјални алгоритми за факторизацију великих ретких матрица. Ови алгоритми покушавају да пронађу ретке факторе L и U. У идеалном случају, цена њиховог израчунавања (меморијамемориско заузеће и број операција) је одређен бројем ненултих елемената, а не величином матрице.

Ови алгоритми користе слободу замене врста и колона да минимализују генерисање ненултих елемената на месту нултих током извршавања алгоритма.

Уопштени поступак ређања који смањује генерисање ненултих елемената се моће одредити коришћењем теорије графова.

Примене

Решавање система линеарних једначина

Имајући у виду матричну једначину

$Ax=LUx=b\,$

желимо да одредимо x за одређено A и b. У овом случају решење ће бити одређено у два логичка корака:

1. прво је потребно решити једначину $Ly=b$ за y
2. друго, потребно је решити једначину $Ux=y$ за x.

Приметити да у оба случаја постоје троугаоне матрице (доња и горња) које се могу решити директном користећи замене унапред и уназад бет коришћења Гаусове елиминације (ипак, Гаусова елиминације или неки њен еквивалент је потребан да се израчуна сама LU факторизација). Стога LU факторизација је рачунски ефикасна само када је потребно решавати матричне једначине за различите вредности b; брже је једном урадити LU декомпозицију матрице A, и затим решавати троугаоне матрице за свако b, него користити Гаусову елиминацију сваки пут.

Инверзна матрица

Када се решва систем јеначина, b се обично сматра као вектор-колона дугачка као висина матрице A. Уместо вектор-колоне b, можемо имати матрицу B, где је B матрица типа nxp, па покушавамо наћи матрицу X (која је исто типа n-x-p):

$AX=LUX=B$

Исти аглоритам ранијепоказан се може користити да се реши свака колона матрице X. Може се претпосатавити да је B јединична матрица диманзија n. Из тога би следило да је решење X инверзна вредност матрице A.

Детерминанта

Матрице $L$ и $U$ се могу искористи да се врло брзо израчуна детерминанта матрице $A$, пошто је det(A) = det(L) det(U) а детерминанта троугаоних матрица је прост производ њених дијагоналних елемената. На пример, ако је L јединична троугаона матрица, онда је

$\det(A)=\det(L)\det(U)=1\cdot \det(U)=\prod _{i=1}^{n}u_{ii}.$

Исти приступ важи и за LUP факторизацију. Детерминанта пермутационе матрице P је (−1)^S, где је $S$ број замена врста у декомпозицији.

Види још

• Блоковска LU декомпозиција
• Метод Холеског
• Декомпозиција матрице
• QR факторизација
• LU редукција

Литература

• Bau III, David; Trefethen, Lloyd N. (1997), Numerical linear algebra, Philadelphia: Society for Industrial and Applied Mathematics, ISBN 978-0-89871-361-9 
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), Introduction to Algorithms, MIT Press and McGraw-Hill, ISBN 978-0-262-03293-3 
• Horn, Roger A.; Johnson, Charles R. (1985), Matrix Analysis, Cambridge University Press, ISBN 0-521-38632-2 . See Section 3.5.
• Householder, Alston (1975), The Theory of Matrices in Numerical Analysis .
• Okunev, Pavel; Johnson, Charles (1997), Necessary And Sufficient Conditions For Existence of the LU Factorization of an Arbitrary Matrix, arXiv:math.NA/0506382  .
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), „Section 2.3”, Numerical Recipes: The Art of Scientific Computing (3rd изд.), New York: Cambridge University Press, ISBN 978-0-521-88068-8 

Спољашње везе

Референце

• LU декомпозиција на сајту MathWorld.
• LU декомпозиција на сајту Math-Linux.
• Модул за LU факторизацију са пивотирањем, проф. Џ. Х. Метјуз, Државни универзитет у Калифорнији, Фулертон
• LU декомпозиција на Институту за холистичке нумеричке методе

Програмски код

• LAPACK, колекција FORTRAN субрутина за решавање проблема из линеарне алгебре
• ALGLIB укључује делимичан порт за LAPACK у C++, C#, Delphi, итд.
• C++ код, проф. Џ. Лумис, Универзитете у Дејтону
• C код, Изворна математичка библиотека
• Псеудо-код: приступ Гаусове елиминације, проф. П. Вапером, Вирџинија тек
• Pseudo-code: Дулитлов алгоритам, проф. П. Вапером, Вирџинија тек
• LU на X10

Онлајн ресурси

• WebApp дескриптивно решавање система линеарних једначина помоћу LU декомпозиције
• Калкулатор за матрице, bluebit.gr
• Алат за LU декомпозицију, uni-bonn.de
• LU декомпозиција, Ед Пег, млађи, Волфрам демонстрациони пројекат, 2007.