Priame metódy pre riešenie veľkých sústav rovníc: Rozdiel medzi revíziami

Z Kiwiki
Skočit na navigaci Skočit na vyhledávání
(Vytvorená stránka „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…“)
 
Riadok 5: Riadok 5:
 
__TOC__
 
__TOC__
 
= =
 
= =
 +
</nowiki>
 +
 +
'''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 x1 :
 +
 +
 +
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 x2. Tento algoritmus využíva iteráciu cez stĺpce matice L. Môžeme si všimnúť, že b1 a&nbsp;b2 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'''
 +
 +
xj<nowiki>= x</nowiki>j / ljj
 +
 +
'''for''' i > j, lij[[Image:Untitled%201_html_m6647c5ea.png]] '''do'''
 +
 +
xj<nowiki>= x</nowiki>j – lij xj<nowiki>;</nowiki>
 +
 +
'''end for'''
 +
 +
'''end for'''
 +
 +
 +
'''Algoritmus prístupom po riadkoch'''
 +
 +
x=b;
 +
 +
x1<nowiki>= x</nowiki>1 / l11 <nowiki>;</nowiki>
 +
 +
'''for''' i=2,... n '''do'''
 +
 +
'''for '''j=1 ...i-1 '''do'''
 +
 +
xj<nowiki>= x</nowiki>j – lij xj<nowiki>;</nowiki>
 +
 +
'''end for'''
 +
 +
xi<nowiki>= x</nowiki>i / lii<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].

Verzia zo dňa a času 21:27, 30. máj 2010

Obsah práce
1. Sústavy lineárnych rovníc a matice
2. Klasické metódy riešenia sústav lineárnych rovníc
3. Priame metódy pre riešenie veľkých sústav rovníc
4. Moderné metódy riešenia veľkých sústav rovníc
5. Softvérové balíky pre riešenie veľkých lineárnych systémov

</nowiki>

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 Untitled 1 html bc4ade2.png 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

Súbor:Untitled 1 html m4f626776.png (3.7)

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

Zdroj: „http://www.kiwiki.info/index.php?title=Priame_metódy_pre_riešenie_veľkých_sústav_rovníc&oldid=4755“