Priame metódy pre riešenie veľkých sústav rovníc
Obsah
Priame metódy pre riešenie veľkých sústav rovníc
Priame metódy vedú k presnému riešeniu danej sústavy po konečnom počte krokov. Pri priamych metódach sa väčšinou daná matica systému zjednoduší použitím niektorého rozkladu a potom sa ďalej pracuje s týmto zjednodušeným systémom . Pri použití rozkladov pre zjednodušenie veľkých matíc dostávame väčšinou trojuholníkové systémy. V tejto kapitole sú opísané niektoré známe rozklady ako aj riešenie trojuholníkových systémov, ktoré vzniknú pri použití týchto rozkladov.
LU rozklad
Táto metóda slúži na rozklad matice A na dve trojuholníkové matice. Kde
L je dolná trojuholníková matica a U je horná trojuholníková matica. Existuje viacero spôsobov určenia LU rozkladu matice.
LU rozklad (Right-Looking LU Factorization)
Táto forma LU rozkladu využíva Gaussovu elimináciu opísanú v kapitole 1.3.3.
Odvodenie tejto metódy rozkladu začína nasledovnou maticovou rovnicou:
Súbor:Untitled 1 html m2f318df1.png = Súbor:Untitled 1 html 75b531c3.png (3.1)
kde l11=1 je skalár a všetky tri matice sú štvorcové matice. Sú možné aj iné varianty ako zvoliť l11. V tomto prípade dostaneme dolnú trojuholníkovú maticu a štyri rovnice.
Súbor:Untitled 1 html me6e6cab.png (3.2)
Súbor:Untitled 1 html 3bb15cf3.png (3.3)
Súbor:Untitled 1 html 4a22611f.png (3.4)
Súbor:Untitled 1 html 24abbc4b.png (3.5)
Možno dokázať, že existuje rozklad LU = A so základným argumentom (3.4) a induktívny predpoklad z rovnice (3.5) [3].Súbor:Untitled 1 html 2b18e193.png (3.6)
Rozklad LU = A existuje len vtedy, ak každý diagonálny prvok ukk je nenulový. Čiastočný výber hlavného prvku vedie k stabilnejšej variante LU = PA , kde P je matica permutácií . Pri čiastočnom výbere hlavného prvku, riadky matice A sú vymenené, a preto je 
maximalizované v každom kroku. Táto výmena môže byť určená pre prvý stĺpec matice A zostaví zostávajúce permutácie matice A. Nech P1, patriace do oboru reálnych čísel o rozmeroch Súbor:Untitled 1 html m7ba66b87.pngn, je permutačná matica ktorá vymieňa dva riadky A tak, že
a Súbor:Untitled 1 html c0f008f.png. Ak rovnica (3.1) a jej ekvivalentné formy (3.2) až (3.5) sú použité priamo na Súbor:Untitled 1 html m200aba46.png, vtedy nemožno použiť induktívny predpoklad (3.6). Ak LU = PA je výrok ktorého platnosť dokazujeme, induktívny predpoklad treba aplikovať na maticu menších rozmerov ale rovnakej formy. Rovnica (3.6) nemá permutačnú maticu. Potom induktívny predpoklad vyzerá nasledovne Súbor:Untitled 1 html m51508616.png (3.8)
kde P2 je permutačná matica [3].
Výraz (3.8) možno rozložiť na blokovú maticu aplikovaním rovníc (3.2) až (3.5) na Súbor:Untitled 1 html m200aba46.png a vynásobením obidvoch strán rovnice (3.4) permutačnou maticou Súbor:Untitled 1 html m16474b3d.png. Potom dostávame
Súbor:Untitled 1 html 62dd0f35.png (3.9)
Súbor:Untitled 1 html 6d4675c9.png (3.10)
Súbor:Untitled 1 html m30970a6.png (3.11)
Súbor:Untitled 1 html 70e7494c.png (3.12)
Tieto štyri rovnice možno zapísať ako maticové rovnice rozmeru Súbor:Untitled 1 html m12e42899.png
Súbor:Untitled 1 html 551d27d1.png = Súbor:Untitled 1 html m46f9d020.png=Súbor:Untitled 1 html m675955a8.png (3.13)
A úpravou rovnice (3.13) podľa (3.11) dostávame
Súbor:Untitled 1 html 551d27d1.png Súbor:Untitled 1 html m560fee59.png (3.14)
Teraz je rovnica (3.14) v požadovanom tvare Súbor:Untitled 1 html 4befde2d.png , kde
Súbor:Untitled 1 html mb417c47.png Súbor:Untitled 1 html m35ea2b1c.png
Algoritmus LU rozkladu vyžaduje Súbor:Untitled 1 html m65f83ebb.png operácií [2][3].
Choleského rozklad
Choleského rozklad je špeciálny rozklad matíc, ktorý možno použiť len na rozklad symetrických kladne definitných matíc. Takéto matice sa ale v určitých aplikáciách vyskytujú dosť často. Choleského rozklad je rýchlejší ako tradičný LU rozklad, pretože využíva špeciálne vlastnosti matíc[8].
Majme systém lineárnych rovníc Ax = b, kde A je Súbor:Untitled 1 html m1f50f11c.pngsymetrická kladne definitná matica, b je známy vektor pravých strán, a x je hľadaný vektor riešení. Jedným so spôsobov riešenia je použitie Choleského rozkladu.
Veta: Ak je matica symetrická kladne definitná, potom existuje dolná trojuholníková matica L, s kladnými diagonálnymi prvkami tak, že Súbor:Untitled 1 html 2a2d7a63.png
Rovnica (3.20)Súbor:Untitled 1 html m3770d2cb.png sa nazýva Choleského rozkladom. Vektor riešení dostaneme vyriešením trojuholníkových systémov Súbor:Untitled 1 html 26e14bbd.png aSúbor:Untitled 1 html bac0f1e.png [3].
Pri LU rozkladu prvky matíc L a U nemajú takmer žiadnu vzájomnú väzbu okrem toho, že ich súčinom dostaneme maticu A. Naopak pri Choleského rozklade pre prvky matíc platí Súbor:Untitled 1 html 75600095.png [8] .
Nech matica A a hľadaná matica L sú blokové matice Súbor:Untitled 1 html 696253c7.png so štvorcovými diagonálnymi blokmi . Vyjadrením (i,j) v rovnici Súbor:Untitled 1 html m4a983f88.png , pre ktoré platí Súbor:Untitled 1 html m35199ff4.png, dostávame
Súbor:Untitled 1 html 69681b68.pngDefinujme S, pre ktoré platí nasledovný vzťah:
Potom podľa (3.16) platí že, Súbor:Untitled 1 html m329aecfb.pngak Súbor:Untitled 1 html 3805e7f9.png a Súbor:Untitled 1 html 6eb573bb.png ak Súbor:Untitled 1 html m304d7ffe.png . Tieto rovnice možno použiť pre výpočet všetkých Súbor:Untitled 1 html 1d0d5994.png [3] [8].
Algoritmus Choleského rozkladu vyžaduje Súbor:Untitled 1 html 289b77e.png operácií, čo je v porovnaní s LU rozkladom o polovicu menej [3].
Riešenie trojuholníkových systémov
Riešenie trojuholníkových systémov lineárnych rovníc, či už hustých alebo riedkych, sa vyskytuje v mnohých aplikáciách. Pretože proces riešenia vyžaduje podstatne menší čas ako príslušný rozklad na trojuholníkový tvar, často požadujeme riešiť dané systémy s rôznymi pravými stranami ale pritom rovnakou trojuholníkovou maticou. Preto je potrebné ich riešiť čo možno najefektívnejšie.
Algoritmy riešenia trojuholníkových systémov
Existujú dva klasické sekvenčné algoritmy pre riešenie trojuholníkových systémov Lx=b . Odlišujú sa v tom že jeden pristupuje k matici L po riadkoch a druhý algoritmus pristupuje po stĺpcoch.
Majme rozklad : Súbor:Untitled 1 html m6664c1d2.png = Súbor:Untitled 1 html 2091c33a.png , kde Súbor:Untitled 1 html m5e5abdc8.png je štvorcová pravá dolná submatica matice L o rozmeroch n-1. Súbor:Untitled 1 html m1e0dd299.png sú stĺpcové vektory o dĺžke n-1. Súbor:Untitled 1 html m6ac242f3.png sú skaláry. Toto vedie k dvom rovniciam Súbor:Untitled 1 html 1c78ceb1.png (3.17) a Súbor:Untitled 1 html m458f3c1c.png (3.18)
Vyriešime prvú rovnicu (3.17) a získame tak x1 :
Druhá rovnica (3.18) je dolný trojuholníkový systém vo forme Súbor:Untitled 1 html 6f51f94b.png. Tento systém možno riešiť rekurzívne a získať tak x2. Tento algoritmus využíva iteráciu cez stĺpce matice L. Môžeme si všimnúť, že b1 a b2 sú použité len raz . Preto môžeme v algoritme priradiť x do b a používame ďalej v algoritme už len x.
Algoritmus s prístupom po stĺpcoch
x=b;
for j=1,... n-1 do
xj= xj / ljj
for i > j, lijSúbor:Untitled 1 html m6647c5ea.png do
xj= xj – lij xj;
end for
end for
Algoritmus prístupom po riadkoch
x=b;
x1 = x1 / l11 ;
for i=2,... n do
for j=1 ...i-1 do
xj= xj – lij xj;
end for
xi= xi / lii;
end for
Pre riešenie Ux = b , kde U je uložená po stĺpcoch, použijeme ďalší rozklad
Súbor:Untitled 1 html m7f281dea.png = Súbor:Untitled 1 html 2091c33a.png
Kde Súbor:Untitled 1 html 7829c687.png je štvorcová submatica matice U o rozmeroch n-1. Dostávame dve rovnice Súbor:Untitled 1 html m471c1329.png(3.19) a Súbor:Untitled 1 html 2c7f31f8.png. Druhú rovnicu (3.20) možno riešiť ako Súbor:Untitled 1 html 376bc6c7.png a z prvej (3.19) dostávame Súbor:Untitled 1 html m254a4557.png<nowiki>. Tento horný trojuholníkový systém riešime podobne ako v predchádzajúcom prípade dolný trojuholníkový systém prostredníctvom algoritmu s prístupom po stĺpcoch [1][2].
