LU dekompozicija

U linearnoj algebri, LU dekompozicija ili LU faktorizacija (od engleskih reči lower - donje i upper - gornje) je dekompozicija matrice koja zapisuje matricu kao proizvod donje trougaone i gornje trougaone matrice. Proizvod nekada uključuje i permutacionu matricu. Ova dekompozicija se koristi u numeričkoj analizi da se reši sistem linearnih jednačina ili da se izračuna determinanta matrice. LU dekompozicija semože smatrati i kao matrični oblik Gausove eliminacije. LU dekompoziciju je uveo Alan Tjuring.

Definicija

Neka je A kvadratna matrica. LU dekompozicija je razlaganje oblika

$A=LU,\,$

gde su L i U donje i gornje trougaone matrice istih dimenzija. To znači da L ima nule samo iznad glavne dijagonale, dok U ima nule ispod glavne dijagonale. Za matricu $3\times 3$ , ovo postaje:

${\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 dekompozicija Volšove matrice

LDU dekompozicija je dekompozicija oblika

$A=LDU,\,$

gde je D dijagonalna matrica a L i U su jedinične trougaone matrice, što znači da su sve vrednosti na glavnim dijagonalama L i U jednake jedinici.

LUP dekompozicija (takođe se naziva LU dekompozicija sa parcijalnim pivotiranjem) je dekompozicija oblika

$PA=LU,\,$

gde su L i U opet donje i gornje trougaone matrice, a P je permutaciona matrica, tj, matrica od nula i jedinica gde se nalazi tačno jedna jedinica u svakoj vrsti i koloni.

LU dekompozicija sa potpunim pivotiranjem je oblika

$PAQ=LU,\,$

Gore je pretpostavljeno da je A kvadratna matrica, ali ove dekompozicije se mogu generalizovati i na pravougaone matrice. U tom slučaju, L i P su kvadratne matrice koje imaju isti broj vrsta kao i A, dok je U istog oblika kao A. Gornja trougaona forma se interpetira kao postojanje nultih elemenata ispod glavne dijagonale, koja počinje u gornjem levom uglu.

Postojanje i jedinstvenost

Regularna matrica dozvoljava LU faktorizaciju ako i samo ako su svi njeni vodeći glavni minori različiti od nule. Faktorizacija je jedinstvena ako zahtevamo da se dijagonale od L (ili U) sastoje od jedinica. Matrica ima jedinstvenu LDU faktorizaciju pod istim uslovima.

Ako je matrica singularna, LU faktorizacija može opet postojati. Zapravo, kvadratna matrica ranga k ima LU faktorizaciju ako je k glavnih vodećih minora različit od nule, mada ne važi obrnuto.

Dovoljni i potrebni uslovi pod kojima neka ne obavezno regularna matrica nad nekim poljem ima LU su poznati. Ovi uslovi su izraženi preko ranga određenih podmatrica. Gausov eliminacioni algoritam za dobijanje LU faktorizacije je takođe proširen na ovaj najopštiji slučajOkunev & Johnson 1997.

Svaka regularna matrica dozvoljava LUP faktorizaciju.

Pozitivno definitne matrice

Ako je matrica A samoajdungovana i pozitivno-definititna, onda možemo da organizovati stvari tako da je U konjugovani transponent od L. U tom slučaju, možemo napisati A kao

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

Ova dekompozicija se naziva metod Holeskog. Metod Holeskog uvek postoji i jedinstven je. Dalje, računanjem metoda Holekskog je efikasnije i numerički stabilnije od računanja nekih drugih LU dekompozicija.

Eksplicitna formulacija

Kada postoji LDU faktorizacija i kada je ona jedinstvena, tada postoji zatovrena (eksplicinta formula) za elemente matrica L, D, i U u vidu količnika determinanti određenih podmatrica originalne matrice A (Householder 1975). Na primer, $D_{1}=A_{1,1}$ i za $i=2,\ldots ,n$, $D_{i}$ je količnik $i$-te glavne podmatrice i $(i-1)$-te glavne podmatrice.

Algoritmi

LU dekompozicija je u osnovi modifikovani oblik Gausove eliminacije. Matrica A se transformiše u gornju trougaonu matricu U eliminisanjem vrednosti ispod glavne dijagonale. Dulitlov algoritam vrši eliminaciju kolone po kolone, idući sa leva, množenjem A sa leve strane atomskom donjem trougaonom matricom. Rezultat ovoga je jedinična donja trougaona matrica i gornja trougaona matrica. Krutov algoritam je malo drugačiji i daje donju trougaonu matricu i jediničnu gornju trougaonu matricu.

Računanje LU faktorizacije korišćenjem bilo kog od ova dva algoritma zahteva 2n³ / 3 operacija sa pokretnim zarezom, ako se ignorišu članovi nižeg reda. Parcijalno pivotiranje dodaje samo kvadratni član; ovo nije slučaj kod punog pivotiranja.

Dulitlov algoritam

Ako imamo matricu dimenzija N × N

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

definišemo početno stanje

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

i zatim sledi n iteracija (n = 1,...,N-1).

Elementi matrice ispod glavne dijagonale u n-oj koloni od A^(n-1) se eliminišu sabiranjem i-te vrste ove matrice pomnožene sa

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

za $i=n+1,\ldots ,N$. Ovo se može uraditi množenjem A^(n-1) sa donjom trougaonom matricom

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

Određujemo

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

Posle N-1 koraka, eliminisani su svi elementi matrice ispod glavne dijagonale, pa se dobija gornja trougaona matrica A^(N-1). Dobija se faktorizacija

$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)}.$

Ako se gornja trougaona matrica A^(N-1) označi sa U, i $L=L_{1}^{-1}\ldots L_{N-1}^{-1}$. Pošto je inverzna vrednost donje trougaone matrice L_n opet donja trougaona matrica, a proizvod dve donje trougaone matrice je opet donja trougaona matrica, dobija se da je L takođe donja trougana matrica. Štaviše, može se videti da je

$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}}.$

Dobijamo $A=LU$.

Jasno je da bi ovaj algoritam pravilno radio, potrebno je imati $a_{n,n}^{(n-1)}\not =0$ u svakom koraku (pogledati definiciju $l_{i,n}$). Ako ovaj uslov nije zadovoljen u nekom trenutku, samo je potrebno zameniti n-tu vrstu sa drugom vrstom ispod nje pre nego što algoritam nastavi dalje. To je razlog zašto LU dekompozicija u opštem slučaju piše kao $P^{-1}A=LU$.

Krutov i LUP algoritmi

LUP faktorizacioni algoritam uopštava Krutovu dekompoziciju matrice. Može se opisati u sledećim koracima.

1. Ako $A$ ima nenulti element u svojoj prvoj vrsti, onda uzeti permutacionu matricu $P_{1}$ tako da $AP_{1}$ ima nenulti element u svom gornjem levom uglu. U suprotnom slučaju, za $P_{1}$ se uzima jedinična matrica. Neka je $A_{1}=AP_{1}$.
2. Neka je $A_{2}$ matrica koja se dobija od matrice $A_{1}$ brisanjem prve vrste i prve kolone. Faktorizovati $A_{2}=L_{2}U_{2}P_{2}$ rekurzivno. Dobiti $L$ od $L_{2}$ prvo dodavanjem nultog reda gore, a zatim dodavanjem prve kolone $A_{1}$ sleva.
3. Dobiti $U_{3}$ od $U_{2}$ prvo dodavanjem nultog reda gore i nulte kolone sa leva, a zatim zamenom gornje leve vrednosti (koja je jednaka 0 u ovom trenutku) jedinicom. Dobiti $P_{3}$ od $P_{2}$ na sličan način i definisati $A_{3}=A_{1}/P_{3}=AP_{1}/P_{3}$. Neka je $P$ inverzna matrica $P_{1}/P_{3}$.
4. U ovom trenutku, $A_{3}$ je isto kao i $LU_{3}$, osim (možda) u prvoj vrsti. Ako je prva vrsta $A$ jednaka nuli, onda $A_{3}=LU_{3}$, pošto obe imaju nultu prvu kolonu, a $A=LU_{3}P$ sledo, kao željeno. U suprotnom slučaju, $A_{3}$ i $LU_{3}$ imaju iste nenulte vrednosti u gornjem levom uglu, i $A_{3}=LU_{3}U_{1}$ za neku gornje-trougaonu kvadratnu matricu $U_{1}$ sa jedinicama na dijagonali ($U_{1}$ briše elemente $LU_{3}$ i dodaje elemente $A_{3}$ pomoću gornjeg levog ugla). Sada je $A=LU_{3}U_{1}P$ dekompozicija željenog oblika.

Teorijska složenost

Ako se dve matrice reda n mogu pomnožiti za vreme M(n), gde je M(n)≥n^a za neko a>2, onda se LU dekompozicija može izračunati za vreme O(M(n)). Ovo na primer znači da O(n^2.376) algoritam postoji zasnovan na Kopersmit-Vinogradovom algoritmu.

Primer

${\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}}.$

Jedan način za pronalaženje LU faktorizacije ove proste matrice je da se prosto inspekcijom reše linearne jednačine. Iz operacije množenja matrica dobija se:

$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.$

Takav sistem jednačina je neodređen. U ovom slučaju bilo koji od dva nenulta elementa matrica L i U su parametri rešenja i mogu se proizvoljno postaviti na neku nenultu vrednost. Stoga, da bi našli jedinstvenu LU faktorizaciju, neophodno je da se postave neka ograničenja na matrice L i U. Na primer, možemo zahtevati da je donja trougaona matrica L jedinična (ima sve jedinice na glavnoj dijagonali). Onda sistem jednačina ima sledeća rešenja:

$l_{21}=1.5$

$u_{11}=4$

$u_{12}=3$

$u_{22}=-1.5.$

Zamenov ovih verednosti u LU dekompoziciju iznad dobijamo:

${\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}}.$

Faktorizacija retkih matrica

Razvijeni su specijalni algoritmi za faktorizaciju velikih retkih matrica. Ovi algoritmi pokušavaju da pronađu retke faktore L i U. U idealnom slučaju, cena njihovog izračunavanja (memorijamemorisko zauzeće i broj operacija) je određen brojem nenultih elemenata, a ne veličinom matrice.

Ovi algoritmi koriste slobodu zamene vrsta i kolona da minimalizuju generisanje nenultih elemenata na mestu nultih tokom izvršavanja algoritma.

Uopšteni postupak ređanja koji smanjuje generisanje nenultih elemenata se moće odrediti korišćenjem teorije grafova.

Primene

Rešavanje sistema linearnih jednačina

Imajući u vidu matričnu jednačinu

$Ax=LUx=b\,$

želimo da odredimo x za određeno A i b. U ovom slučaju rešenje će biti određeno u dva logička koraka:

1. prvo je potrebno rešiti jednačinu $Ly=b$ za y
2. drugo, potrebno je rešiti jednačinu $Ux=y$ za x.

Primetiti da u oba slučaja postoje trougaone matrice (donja i gornja) koje se mogu rešiti direktnom koristeći zamene unapred i unazad bet korišćenja Gausove eliminacije (ipak, Gausova eliminacije ili neki njen ekvivalent je potreban da se izračuna sama LU faktorizacija). Stoga LU faktorizacija je računski efikasna samo kada je potrebno rešavati matrične jednačine za različite vrednosti b; brže je jednom uraditi LU dekompoziciju matrice A, i zatim rešavati trougaone matrice za svako b, nego koristiti Gausovu eliminaciju svaki put.

Inverzna matrica

Kada se rešava sistem jednačina, b se obično smatra kao vektor-kolona dugačka kao visina matrice A. Umesto vektor-kolone b, možemo imati matricu B, gde je B matrica tipa nxp, pa pokušavamo naći matricu X (koja je isto tipa n-x-p):

$AX=LUX=B$

Isti agloritam ranije pokazan se može koristiti da se reši svaka kolona matrice X. Može se pretpostaviti da je B jedinična matrica dimenzija n. Iz toga bi sledilo da je rešenje X inverzna vrednost matrice A.

Determinanta

Matrice $L$ i $U$ se mogu iskoristi da se vrlo brzo izračuna determinanta matrice $A$, pošto je det(A) = det(L) det(U) a determinanta trougaonih matrica je prost proizvod njenih dijagonalnih elemenata. Na primer, ako je L jedinična trougaona matrica, onda je

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

Isti pristup važi i za LUP faktorizaciju. Determinanta permutacione matrice P је (−1)^S, gde je $S$ broj zamena vrsta u dekompoziciji.

Vidi još

• Blokovska LU dekompozicija
• Metod Holeskog
• Dekompozicija matrice
• QR faktorizacija
• LU redukcija

Literatura

• Golub, Gene H.; Van Loan, Charles F. (1996). Matrix Computations (3rd izd.). Baltimore: Johns Hopkins. ISBN 978-0-8018-5414-9. 
• Poole, David (2006). Linear Algebra: A Modern Introduction (2nd izd.). Canada: Thomson Brooks/Cole. ISBN 978-0-534-99845-5. 
• 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 978-0-521-38632-6. . 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 izd.). New York: Cambridge University Press. ISBN 978-0-521-88068-8. 

Spoljašnje veze

Reference

• LU dekompozicija na sajtu MathWorld.
• LU dekompozicija Arhivirano na sajtu Wayback Machine (5. mart 2013) na sajtu Math-Linux.
• Modul za LU faktorizaciju sa pivotiranjem, prof. Dž. H. Metjuz, Državni univerzitet u Kaliforniji, Fulerton
• LU dekompozicija na Institutu za holističke numeričke metode

Programski kod

• LAPACK, kolekcija FORTRAN subrutina za rešavanje problema iz linearne algebre
• ALGLIB uključuje delimičan port za LAPACK u C++, C#, Delphi, itd.
• C++ kod, prof. Dž. Lumis, Univerzitet u Dejtonu
• C kod, Izvorna matematička biblioteka
• LU na X10

Onlajn resursi

• Kalkulator za matrice, bluebit.gr
• Alat za LU dekompoziciju, uni-bonn.de
• LU dekompozicija, Ed Peg, mlađi, Volfram demonstracioni projekat, 2007.