Moderné metódy riešenia 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|4|Moderné metódy riešenia veľkých sústav lineárnych rovn…“)
 
Riadok 9: Riadok 9:
 
== Metóda konjugovaných gradientov (CG) ==
 
== Metóda konjugovaných gradientov (CG) ==
 
Väčšina iteračných metód je závislá na parametroch, avšak niekedy je veľmi náročné zvoliť správne parametre. Toto nie je potrebné pri metóde konjugovaných gradientov (Conjugate Gradient Method). Táto metóda sa používa pre riešenie pre veľkých riedkych systémov, pretože sa v nej často využíva len násobenie matice sústavy vektorom. Metóda konjugovaných gradientov je vhodná pre symetrické a kladne definitné systémy[3].
 
Väčšina iteračných metód je závislá na parametroch, avšak niekedy je veľmi náročné zvoliť správne parametre. Toto nie je potrebné pri metóde konjugovaných gradientov (Conjugate Gradient Method). Táto metóda sa používa pre riešenie pre veľkých riedkych systémov, pretože sa v nej často využíva len násobenie matice sústavy vektorom. Metóda konjugovaných gradientov je vhodná pre symetrické a kladne definitné systémy[3].
 +
</nowiki>
  
 +
Majme systém rovníc Ax=b, kde A&nbsp;je štvorcová symetrická kladne definitná matica.
  
 +
Využíva sa tu fakt, že riešenie takejto sústavy je jediným minimom nasledovnej formy :
  
 +
 +
<nowiki>[3][9]</nowiki>
 +
 +
Minimum funkcie [[Image:Untitled%201_html_62c069ec.png]] je [[Image:Untitled%201_html_34cf7694.png]] , čo sme dostali dosadením za x , [[Image:Untitled%201_html_m60aae07e.png]] .
 +
 +
Potom teda minimalizácia funkcie [[Image:Untitled%201_html_62c069ec.png]] a&nbsp;riešenie rovnice [[Image:Untitled%201_html_m7a021ec3.png]] , sú ekvivalentné problémy ak je matica A&nbsp;symetrická kladne definitná.
 +
 +
Jedným z&nbsp;najjednoduchších spôsobov pre minimalizáciu je tzv. metóda najväčšieho spádu. V&nbsp;nejakom bode xc funkcia ϕ klesá najviac v&nbsp;smere záporného gradientu:
 +
 +
[[Image:Untitled%201_html_m5e2a05ac.png]] potom [[Image:Untitled%201_html_m5edc5fcf.png]] . Hovoríme že, ''rc'' je reziduálny vektor v&nbsp;bode xc. Ak je reziduálny vektor nenulový , potom existuje kladné α , také že [[Image:Untitled%201_html_m5857533e.png]]. Pre minimalizáciu dosadíme za α ,
 +
 +
 +
[[Image:Untitled%201_html_m5fddc51d.png]]Budeme uvažovať o&nbsp;minimalizácii pozdĺž smerov {p1,p2,....} . V tejto metóde sa volia vektory pk tak, že vzniknú A-ortogonalizáciou vektora rezíduí . A-ortogonalizácia umožňuje z postupnosti lineárne nezávislých vektorov u1 , ... , un zostrojiť inú postupnosť lineárne nezávislých vektorov v1 , ... , vn tak , že bude platiť nasledovný vzťah [[Image:Untitled%201_html_m34c7e8ad.png]]
 +
 +
Možno dokázať, že minimum funkcie [[Image:Untitled%201_html_m50af89e3.png]] dostaneme pre
 +
 +
[[Image:Untitled%201_html_m1f81f06b.png]].
 +
 +
Dostávame [[Image:Untitled%201_html_4b706326.png]] , kde [[Image:Untitled%201_html_30d16477.png]]je spádový smer a [[Image:Untitled%201_html_50944cad.png]]<nowiki> je optimálny krok[3]. </nowiki>
 +
 +
Ak [[Image:Untitled%201_html_41a11afb.png]]potom existuje[[Image:Untitled%201_html_1b50c9e0.png]] také, že [[Image:Untitled%201_html_m73d51500.png]]. Keď je [[Image:Untitled%201_html_17e99a2f.png]] potom [[Image:Untitled%201_html_m5a74b315.png]]. Pre k > 1 potom platí : [[Image:Untitled%201_html_m37501b51.png]] .
 +
 +
Keď [[Image:Untitled%201_html_2c4cd40f.png]] potom dostávame vzťah : [[Image:Untitled%201_html_m19c0fef7.png]]
 +
 +
Reziduálny vektor[[Image:Untitled%201_html_3a67fd29.png]] môžeme vyjadriť ako [[Image:Untitled%201_html_103ca811.png]] .
 +
 +
Potom použitím nasledovných substitúcií [[Image:Untitled%201_html_m3a97303b.png]]
 +
 +
 +
vo vzťahu pre [[Image:Untitled%201_html_7103b18.png]] dostávame výsledný algoritmus .
  
 
== Metóda bikonjugovaných gradientov (BCG) ==
 
== Metóda bikonjugovaných gradientov (BCG) ==

Verzia zo dňa a času 17:12, 30. júl 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

V tejto časti sú opísané niektoré z moderných iteračných metód, ktoré sú vhodné pre riešenie veľmi veľkých a riedkych matíc. Sú tu opísané gradientné metódy a taktiež multigridové metódy. Tieto metódy využívajú mnohé zo simulačných softvérov, kde je potrebné riešiť veľké riedke sústavy lineárnych rovníc.

Metóda konjugovaných gradientov (CG)

Väčšina iteračných metód je závislá na parametroch, avšak niekedy je veľmi náročné zvoliť správne parametre. Toto nie je potrebné pri metóde konjugovaných gradientov (Conjugate Gradient Method). Táto metóda sa používa pre riešenie pre veľkých riedkych systémov, pretože sa v nej často využíva len násobenie matice sústavy vektorom. Metóda konjugovaných gradientov je vhodná pre symetrické a kladne definitné systémy[3]. </nowiki>

Majme systém rovníc Ax=b, kde A je štvorcová symetrická kladne definitná matica.

Využíva sa tu fakt, že riešenie takejto sústavy je jediným minimom nasledovnej formy :


[3][9]

Minimum funkcie Súbor:Untitled 1 html 62c069ec.png je Súbor:Untitled 1 html 34cf7694.png , čo sme dostali dosadením za x , Súbor:Untitled 1 html m60aae07e.png .

Potom teda minimalizácia funkcie Súbor:Untitled 1 html 62c069ec.png a riešenie rovnice Súbor:Untitled 1 html m7a021ec3.png , sú ekvivalentné problémy ak je matica A symetrická kladne definitná.

Jedným z najjednoduchších spôsobov pre minimalizáciu je tzv. metóda najväčšieho spádu. V nejakom bode xc funkcia ϕ klesá najviac v smere záporného gradientu:

Súbor:Untitled 1 html m5e2a05ac.png potom Súbor:Untitled 1 html m5edc5fcf.png . Hovoríme že, rc je reziduálny vektor v bode xc. Ak je reziduálny vektor nenulový , potom existuje kladné α , také že Súbor:Untitled 1 html m5857533e.png. Pre minimalizáciu dosadíme za α ,


Súbor:Untitled 1 html m5fddc51d.pngBudeme uvažovať o minimalizácii pozdĺž smerov {p1,p2,....} . V tejto metóde sa volia vektory pk tak, že vzniknú A-ortogonalizáciou vektora rezíduí . A-ortogonalizácia umožňuje z postupnosti lineárne nezávislých vektorov u1 , ... , un zostrojiť inú postupnosť lineárne nezávislých vektorov v1 , ... , vn tak , že bude platiť nasledovný vzťah Súbor:Untitled 1 html m34c7e8ad.png

Možno dokázať, že minimum funkcie Súbor:Untitled 1 html m50af89e3.png dostaneme pre

Súbor:Untitled 1 html m1f81f06b.png.

Dostávame Súbor:Untitled 1 html 4b706326.png , kde Súbor:Untitled 1 html 30d16477.pngje spádový smer a Súbor:Untitled 1 html 50944cad.png je optimálny krok[3].

Ak Súbor:Untitled 1 html 41a11afb.pngpotom existujeSúbor:Untitled 1 html 1b50c9e0.png také, že Súbor:Untitled 1 html m73d51500.png. Keď je Súbor:Untitled 1 html 17e99a2f.png potom Súbor:Untitled 1 html m5a74b315.png. Pre k > 1 potom platí : Súbor:Untitled 1 html m37501b51.png .

Keď Súbor:Untitled 1 html 2c4cd40f.png potom dostávame vzťah : Súbor:Untitled 1 html m19c0fef7.png

Reziduálny vektorSúbor:Untitled 1 html 3a67fd29.png môžeme vyjadriť ako Súbor:Untitled 1 html 103ca811.png .

Potom použitím nasledovných substitúcií Súbor:Untitled 1 html m3a97303b.png


vo vzťahu pre Súbor:Untitled 1 html 7103b18.png dostávame výsledný algoritmus .

Metóda bikonjugovaných gradientov (BCG)

Generalized Minimal Residual Method (GMRES)

Multigridové metódy (MG)

Zdroj: „http://www.kiwiki.info/index.php?title=Moderné_metódy_riešenia_veľkých_sústav_rovníc&oldid=6404“