Zobrazenie zdroja stránky Priame metódy pre riešenie veľkých sústav rovníc

[[Kategória:Študentské práce]]
[[Kategória:Ročníkové práce]]
[[Kategória:Matematika]]
{{Praca_uvod|3|Moderné metódy riešenia veľkých sústav lineárnych rovníc|Sústavy lineárnych rovníc a matice|Klasické metódy riešenia sústav lineárnych rovníc|Priame metódy pre riešenie veľkých sústav rovníc|Moderné metódy riešenia veľkých sústav rovníc|Softvérové balíky pre riešenie veľkých lineárnych systémov||||||||||}}
__TOC__
= =


'''Priame metódy pre riešenie veľkých sústav rovníc'''

Priame metódy vedú k&nbsp;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&nbsp;potom sa ďalej pracuje s&nbsp;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&nbsp;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&nbsp;na dve trojuholníkové matice. Kde 

L je dolná trojuholníková matica a&nbsp;U&nbsp;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&nbsp;kapitole 1.3.3. 

Odvodenie tejto metódy rozkladu začína nasledovnou maticovou rovnicou:

[[Image:Untitled%201_html_m2f318df1.png]] = [[Image:Untitled%201_html_75b531c3.png]] (3.1)

kde l11<nowiki>=1 je skalár a&nbsp;všetky tri matice sú štvorcové matice. Sú možné aj iné varianty ako zvoliť l</nowiki>11. V&nbsp;tomto prípade dostaneme dolnú trojuholníkovú maticu a&nbsp;štyri rovnice.

[[Image:Untitled%201_html_me6e6cab.png]] (3.2)

[[Image:Untitled%201_html_3bb15cf3.png]] (3.3)

[[Image:Untitled%201_html_4a22611f.png]] (3.4)

[[Image:Untitled%201_html_24abbc4b.png]] (3.5)

<nowiki>Možno dokázať, že existuje rozklad LU = A&nbsp;so základným argumentom (3.4) a&nbsp;induktívny predpoklad z&nbsp;rovnice (3.5) [3].</nowiki>[[Image:Untitled%201_html_2b18e193.png]] (3.6) 

Rozklad LU = A&nbsp;existuje len vtedy, ak každý diagonálny prvok ukk je nenulový. Čiastočný výber hlavného prvku vedie k&nbsp;stabilnejšej variante LU = PA , kde P je matica permutácií . Pri čiastočnom výbere hlavného prvku, riadky matice A&nbsp;sú vymenené, a preto je [[Image:Untitled%201_html_bc4ade2.png]] maximalizované v&nbsp;každom kroku. Táto výmena môže byť určená pre prvý stĺpec matice A&nbsp;zostaví zostávajúce permutácie matice A. Nech P1, patriace do oboru reálnych čísel o&nbsp;rozmeroch [[Image:Untitled%201_html_m7ba66b87.png]]n, je permutačná matica ktorá vymieňa dva riadky A&nbsp;tak, že 

<center>[[Image:Untitled%201_html_m4f626776.png]] (3.7)</center>

a [[Image:Untitled%201_html_c0f008f.png]]. Ak rovnica (3.1) a&nbsp;jej ekvivalentné formy (3.2) až (3.5) sú použité priamo na [[Image:Untitled%201_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 [[Image:Untitled%201_html_m51508616.png]] (3.8) 

kde P2<nowiki> je permutačná matica [3]. </nowiki>


Výraz (3.8) možno rozložiť na blokovú maticu aplikovaním rovníc (3.2) až (3.5) na [[Image:Untitled%201_html_m200aba46.png]] a&nbsp;vynásobením obidvoch strán rovnice (3.4) permutačnou maticou [[Image:Untitled%201_html_m16474b3d.png]]. Potom dostávame 

[[Image:Untitled%201_html_62dd0f35.png]] (3.9)

[[Image:Untitled%201_html_6d4675c9.png]] (3.10)

[[Image:Untitled%201_html_m30970a6.png]] (3.11)

[[Image:Untitled%201_html_70e7494c.png]] (3.12)

Tieto štyri rovnice možno zapísať ako maticové rovnice rozmeru [[Image:Untitled%201_html_m12e42899.png]]

[[Image:Untitled%201_html_551d27d1.png]] = [[Image:Untitled%201_html_m46f9d020.png]]<nowiki>=</nowiki>[[Image:Untitled%201_html_m675955a8.png]] (3.13)

A&nbsp;úpravou rovnice (3.13) podľa (3.11) dostávame 

[[Image:Untitled%201_html_551d27d1.png]] [[Image:Untitled%201_html_m560fee59.png]] (3.14)


Teraz je rovnica (3.14) v&nbsp;požadovanom tvare [[Image:Untitled%201_html_4befde2d.png]] , kde

[[Image:Untitled%201_html_mb417c47.png]] [[Image:Untitled%201_html_m35ea2b1c.png]]

Algoritmus LU rozkladu vyžaduje [[Image:Untitled%201_html_m65f83ebb.png]]<nowiki> operácií [2][3].</nowiki>





== Choleského rozklad ==
<nowiki>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&nbsp;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]. </nowiki>

Majme systém lineárnych rovníc ''Ax = b'', kde ''A''&nbsp;je [[Image:Untitled%201_html_m1f50f11c.png]]symetrická kladne definitná matica, ''b'' je známy vektor pravých strán, a&nbsp;''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&nbsp;kladnými diagonálnymi prvkami tak, že [[Image:Untitled%201_html_2a2d7a63.png]] 

Rovnica (3.20)[[Image:Untitled%201_html_m3770d2cb.png]] sa nazýva Choleského rozkladom. Vektor riešení dostaneme vyriešením trojuholníkových systémov [[Image:Untitled%201_html_26e14bbd.png]] a[[Image:Untitled%201_html_bac0f1e.png]]<nowiki> [3].</nowiki>

Pri LU rozkladu prvky matíc L a&nbsp;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í [[Image:Untitled%201_html_75600095.png]]<nowiki> [8] .</nowiki>

Nech matica A&nbsp;a&nbsp;hľadaná matica L sú blokové matice [[Image:Untitled%201_html_696253c7.png]] so štvorcovými diagonálnymi blokmi . Vyjadrením (i,j) v&nbsp;rovnici [[Image:Untitled%201_html_m4a983f88.png]] , pre ktoré platí [[Image:Untitled%201_html_m35199ff4.png]], dostávame 


[[Image:Untitled%201_html_69681b68.png]]Definujme S,&nbsp;pre ktoré platí nasledovný vzťah:


Potom podľa (3.16) platí že, [[Image:Untitled%201_html_m329aecfb.png]]ak [[Image:Untitled%201_html_3805e7f9.png]] a [[Image:Untitled%201_html_6eb573bb.png]] ak [[Image:Untitled%201_html_m304d7ffe.png]] . Tieto rovnice možno použiť pre výpočet všetkých [[Image:Untitled%201_html_1d0d5994.png]]<nowiki> [3] [8]. </nowiki>

Algoritmus Choleského rozkladu vyžaduje [[Image:Untitled%201_html_289b77e.png]]<nowiki> operácií, čo je v&nbsp;porovnaní s&nbsp;LU rozkladom o&nbsp;polovicu menej [3]. </nowiki>


== 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&nbsp;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&nbsp;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&nbsp;tom že jeden pristupuje k&nbsp;matici L po riadkoch a&nbsp;druhý algoritmus pristupuje po stĺpcoch. 

Majme rozklad : [[Image:Untitled%201_html_m6664c1d2.png]] = [[Image:Untitled%201_html_2091c33a.png]] , kde [[Image:Untitled%201_html_m5e5abdc8.png]] je štvorcová pravá dolná submatica matice L o&nbsp;rozmeroch n-1. [[Image:Untitled%201_html_m1e0dd299.png]] sú stĺpcové vektory o&nbsp;dĺžke n-1. [[Image:Untitled%201_html_m6ac242f3.png]] sú skaláry. Toto vedie k&nbsp;dvom rovniciam [[Image:Untitled%201_html_1c78ceb1.png]] (3.17) a [[Image:Untitled%201_html_m458f3c1c.png]] (3.18)

Vyriešime prvú rovnicu (3.17) a&nbsp;získame tak x<sub>1</sub> :


Druhá rovnica (3.18) je dolný trojuholníkový systém vo forme [[Image:Untitled%201_html_6f51f94b.png]]. Tento systém možno riešiť rekurzívne a&nbsp;získať tak x<sub>2</sub>. Tento algoritmus využíva iteráciu cez stĺpce matice L. Môžeme si všimnúť, že b<sub>1</sub> a&nbsp;b<sub>2</sub> sú použité len raz . Preto môžeme v&nbsp;algoritme priradiť x do b a&nbsp;používame ďalej v&nbsp;algoritme už len x.


'''Algoritmus s prístupom po stĺpcoch''' 

x=b;

'''for''' j=1,... n-1 '''do'''

x<sub>j</sub><nowiki>= </nowiki> x<sub>j</sub> / l<sub>jj</sub> 

'''for''' i > j, l<sub>ij</sub>[[Image:Untitled%201_html_m6647c5ea.png]] '''do'''

x<sub>j</sub><nowiki>= </nowiki>x<sub>j</sub> – l<sub>ij</sub> x<sub>j</sub><nowiki>;</nowiki>

'''end for'''

'''end for''' 


'''Algoritmus prístupom po riadkoch''' 

x=b;

x<sub>1</sub> <nowiki>= </nowiki>x<sub>1</sub> / l<sub>11</sub> <nowiki>;</nowiki>

'''for''' i=2,... n '''do'''

'''for '''j=1 ...i-1 '''do'''

x<sub>j</sub><nowiki>= </nowiki> x<sub>j</sub> – l<sub>ij</sub> x<sub>j</sub><nowiki>;</nowiki>

'''end for'''

xi<nowiki>= x</nowiki>i / l<sub>ii</sub><nowiki>;</nowiki>
 
'''end for'''


Pre riešenie Ux = b , kde U&nbsp;je uložená po stĺpcoch, použijeme ďalší rozklad 

[[Image:Untitled%201_html_m7f281dea.png]] = [[Image:Untitled%201_html_2091c33a.png]]

Kde [[Image:Untitled%201_html_7829c687.png]] je štvorcová submatica matice U o&nbsp;rozmeroch n-1. Dostávame dve rovnice [[Image:Untitled%201_html_m471c1329.png]](3.19) a [[Image:Untitled%201_html_2c7f31f8.png]]. Druhú rovnicu (3.20) možno riešiť ako [[Image:Untitled%201_html_376bc6c7.png]] a&nbsp;z&nbsp;prvej (3.19) dostávame [[Image:Untitled%201_html_m254a4557.png]]<nowiki>. Tento horný trojuholníkový systém riešime podobne ako v&nbsp;predchádzajúcom prípade dolný trojuholníkový systém prostredníctvom algoritmu s&nbsp;prístupom po stĺpcoch [1][2].