Kiwiki - Príspevky používateľa [sk]

Moderné metódy riešenia veľkých sústav lineárnych rovníc (Zadanie)

2010-08-03T12:06:41Z

Repto:

{{Zadanie_RP|Bc. Peter Poruban|Mechatronika|Moderné metódy riešenia veľkých sústav lineárnych rovníc|
Cieľom práce študenta je oboznámiť sa s metódami riešenia veľkých sústav lineárnych rovníc, opísať a porovnať niektoré existujúce metódy vhodné pre riešenie veľkých sústav lineárnych rovníc.
|# John K.Large Sparse Sets of Linear Equations. Academic Press Inc. 284 p. ISBN 0125861508.
# Timoty A. Davis: Direct Methods for Sparse Linear Systems: Fundamentals of Algorithms. Society for Industrial and Applied Mathematic . 217 p. ISBN 0898716136.
|Katedra informatiky, Fakulta mechatroniky, TnUAD
|Ing. Michal Štepanovský, PhD.
|Ing. Michal Štepanovský, PhD.
|7.10.2009
|Ing. Ján Žabka, CSc.|KI FM TnUAD
}}
[[Kategória:Zadanie RP]]

Moderné metódy riešenia veľkých sústav lineárnych rovníc (Zadanie)

2010-08-03T12:05:40Z

Repto:

{{Zadanie_RP|Bc. Peter Poruban|Mechatronika|Moderné metódy riešenia veľkých sústav lineárnych rovníc|
Cieľom práce študenta je oboznámiť sa s metódami riešenia veľkých sústav lineárnych rovníc, opísať a porovnať niektoré existujúce metódy vhodné pre riešenie veľkých sústav lineárnych rovníc.
|# John K.Large Sparse Sets of Linear Equations. Academic Press Inc. 284 p. ISBN 0125861508
# Timoty A. Davis: Direct Methods for Sparse Linear Systems: Fundamentals of Algorithms. Society for Industrial and Applied Mathematic . 217 p. ISBN 0898716136
|Katedra informatiky, Fakulta mechatroniky, TnUAD
|Ing. Michal Štepanovský, PhD.
|Ing. Michal Štepanovský, PhD.
|7.10.2009
|Ing. Ján Žabka, CSc.|KI FM TnUAD
}}
[[Kategória:Zadanie RP]]

Moderné metódy riešenia veľkých sústav rovníc

2010-07-30T15:12:16Z

Repto: /* Metóda konjugovaných gradientov (CG) */

[[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í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__
= =
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 :

<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 riešenie rovnice [[Image:Untitled%201_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:

[[Image:Untitled%201_html_m5e2a05ac.png]] potom [[Image:Untitled%201_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 [[Image:Untitled%201_html_m5857533e.png]]. Pre minimalizáciu dosadíme za α ,

[[Image:Untitled%201_html_m5fddc51d.png]]Budeme 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 [[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) ==

== Generalized Minimal Residual Method (GMRES) ==

== Multigridové metódy (MG) ==

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

2010-06-18T13:33:20Z

Repto: /* Algoritmy riešenia trojuholníkových systémov */

[[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 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 2.1.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 všetky tri matice sú štvorcové matice. Sú možné aj iné varianty ako zvoliť </nowiki> l11. V tomto prípade dostaneme dolnú trojuholníkovú maticu a š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 so základným argumentom (3.4) a induktívny predpoklad z rovnice (3.5) [3].</nowiki>[[Image:Untitled%201_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 [[Image:Untitled%201_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 [[Image:Untitled%201_html_m7ba66b87.png]]n, je permutačná matica ktorá vymieňa dva riadky A tak, že

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

a [[Image:Untitled%201_html_c0f008f.png]]. Ak rovnica (3.1) a 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 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 ú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 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 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'' je [[Image:Untitled%201_html_m1f50f11c.png]]symetrická 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 [[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 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 a hľadaná matica L sú blokové matice [[Image:Untitled%201_html_696253c7.png]] so štvorcovými diagonálnymi blokmi . Vyjadrením (i,j) v 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, 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 porovnaní s LU rozkladom o 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 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 : [[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 rozmeroch n-1. [[Image:Untitled%201_html_m1e0dd299.png]] sú stĺpcové vektory o dĺžke n-1. [[Image:Untitled%201_html_m6ac242f3.png]] sú skaláry. Toto vedie k 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 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 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'''

<source lang="pascal">

x=b;

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

xj= xj / Ljj ;

for i > j,Lij != 0 do

xj= xj – Lij * xj;

end for

end for
</source>

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

<source lang="pascal">

x=b;

for i=2,... n do
for j=2,... i-1 do
xj= xj - Lij * xj ;
end for
xi= xi / Lii;
end for
</source>

Pre riešenie Ux = b , kde U 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 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 z prvej (3.19) dostávame [[Image:Untitled%201_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].

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

2010-05-30T21:57:38Z

Repto: /* LU rozklad */

[[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 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 2.1.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 všetky tri matice sú štvorcové matice. Sú možné aj iné varianty ako zvoliť </nowiki> l11. V tomto prípade dostaneme dolnú trojuholníkovú maticu a š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 so základným argumentom (3.4) a induktívny predpoklad z rovnice (3.5) [3].</nowiki>[[Image:Untitled%201_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 [[Image:Untitled%201_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 [[Image:Untitled%201_html_m7ba66b87.png]]n, je permutačná matica ktorá vymieňa dva riadky A tak, že

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

a [[Image:Untitled%201_html_c0f008f.png]]. Ak rovnica (3.1) a 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 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 ú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 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 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'' je [[Image:Untitled%201_html_m1f50f11c.png]]symetrická 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 [[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 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 a hľadaná matica L sú blokové matice [[Image:Untitled%201_html_696253c7.png]] so štvorcovými diagonálnymi blokmi . Vyjadrením (i,j) v 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, 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 porovnaní s LU rozkladom o 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 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 : [[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 rozmeroch n-1. [[Image:Untitled%201_html_m1e0dd299.png]] sú stĺpcové vektory o dĺžke n-1. [[Image:Untitled%201_html_m6ac242f3.png]] sú skaláry. Toto vedie k 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 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 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<nowiki>= </nowiki> xj / ljj

'''for''' i > j, lij[[Image:Untitled%201_html_m6647c5ea.png]] '''do'''

xj<nowiki>= </nowiki>xj – lij xj<nowiki>;</nowiki>

'''end for'''

'''end for'''

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

x=b;

x1 <nowiki>= </nowiki>x1 / l11 <nowiki>;</nowiki>

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

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

xj<nowiki>= </nowiki> xj – lij xj<nowiki>;</nowiki>

'''end for'''

xi<nowiki>= x</nowiki>i / lii<nowiki>;</nowiki>

'''end for'''

Pre riešenie Ux = b , kde U 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 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 z prvej (3.19) dostávame [[Image:Untitled%201_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].

Moderné metódy riešenia veľkých sústav lineárnych rovníc

2010-05-30T21:54:59Z

Repto: /* Diagonálne matice */

[[Kategória:Študentské práce]]
[[Kategória:Ročníkové práce]]
[[Kategória:Matematika]]
{{Draft}}
{{Hlavička_FM
|{{PAGENAME}}|Bc. Peter Poruban|Ing. Michal Štepanovský, PhD
|2009/2010
|Ročníková práca
|Mechatronika
}}
{{Praca_uvod|1|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||||||||||}}
{{abstrakt
|Práca sa zaoberá metódami vhodnými pre riešenie veľkých sústav lineárnych rovníc. Prvá časť sa zaoberá klasickými metódami pre riešenie sústav lineárnych rovníc. V ďalšej časti sú opísané priame metódy riešenia veľkých sústav . Tretia časť sa venuje moderným iteračným metódam. V práci sa podrobne zaoberáme metódou konjugovaných gradientov a geometrickou multigridovou metódou. Pre tieto dve metódy sme vypracovali ukážkové príklady riešenia. Posledná časť sa zaoberá využitím týchto metód.
|
}}
__TOC__
'''Úvod'''

V technickej praxi je častou úlohou riešiť sústavu lineárnych rovníc Ax= b s maticou rádu n, kde n je veľké číslo. Rozmery týchto matíc môžu byť rádovo v státisícoch, ale aj väčšie. Pri takýchto sústavách lineárnych rovníc sú niektoré tradičné metódy nepoužiteľné alebo sú neefektívne a časovo náročné. Taktiež niektoré z nich môžu pri maticiach veľmi veľkých rozmerov alebo zle podmienených maticiach zlyhať.
Stretávame sa s dvomi typmi systémov lineárnych rovníc. Systém lineárnych rovníc sa nazýva plný, ak väčšina prvkov je nenulová. Naopak riedke systémy sú také, kde len relatívne málo prvkov je nenulových. Pre riešenie riedkych systémov možno využiť ich vlastnosti. Vďaka tomu možno riešiť prostredníctvom niektorých algoritmov tieto matice efektívnejšie. Veľké riedke systémy je v technickej praxi veľmi často potrebné riešiť, napr. pri riešení parciálnych diferenciálnych rovníc.
Metódy pre riešenie lineárnych rovníc delíme na priame metódy a iteračné metódy. Priame metódy vedú k riešeniu po konečnom počte krokov. Naopak iteračné metódy konvergujú k riešeniu a presnosť riešenia je závislá od počtu iterácií . Priame metódy sú všeobecne vhodnejšie pre plné matice, naopak pre riedke systémy sú vhodné iteračné metódy.
Známe sú klasické priame metódy ako Cramerovo pravidlo, použitie inverznej matice a Gaussova eliminačná metóda. Tieto však nie sú pre systémy veľkých rozmerov vhodné. Taktiež sú známe klasické iteračné algoritmy ako je Jacobiho metóda a Gauss Seidelova metóda. Tieto sú vhodné aj pre riedke matice veľkých rozmerov.
Pre priame riešenie veľkých sústav je známych niekoľko algoritmov. V tejto práci je opísaný LU rozklad a Choleského rozklad. Tieto rozklady sa v rôznych obmenených podobách používajú pre priame riešenie veľkých sústav lineárnych rovníc.
V posledných desaťročiach bolo vypracovaných niekoľko moderných iteračných algoritmov pre riešenie veľkých sústav lineárnych rovníc. V práci sa zaoberáme gradientnými metódami a multigridovými metódami. Metóda konjugovaných gradientov konverguje k riešeniu rýchlejšie ako klasické iteračné metódy a je výhodná hlavne pre symetrické kladne definitné matice. Naopak, metóda bikonjugovaných gradientov a metóda GMRES sú vhodné aj pre nesymetrické matice. Multigridové metódy patria medzi najrýchlejšie iteračné metódy. Zlepšujú konvergenciu tým, že sa daná úloha opísaná určitou sieťou vyrieši najprv pre redšiu sieť a potom sa toto riešenie použije pri hľadaní riešenia v hustejšej sieti.

=Sústavy lineárnych rovníc a matice=
V tejto časti sú opísané základné pojmy lineárnej algebry , ktoré súvisia s výpočtom
sústav lineárnych rovníc . Taktiež sú tu opísané rôzne tvary matíc, ktoré sa používajú pri riešení sústav lineárnych rovníc.
==Systémy lineárnych rovníc==
Riešenie sústav lineárnych rovníc patrí medzi najdôležitejšie časti matematiky. Množstvo praktických úloh nakoniec vedie k riešeniu takýchto sústav. Tieto sústavy môžu byť často veľmi rozsiahle. Vtedy je n veľké číslo.
Systém n - lineárnych rovníc:

<math>
\begin{matrix}
a_{11}x_1+a_{12}x_2+...+a_{1n}x_n\\
a_{21}x_1+a_{22}x_2+...+a_{2n}x_n\\
.\\
.\\
.\\
a_{n1}x_1+a_{n2}x_2+...+a_{nn}x_n
\end{matrix}
</math>(1.1)

s neznámymi x1,x2,...,xn.

Matica A(i,j) , kde i,j=1,..... n, sa nazýva maticou sústavy stĺpcový vektor b =(b1, ...., bn)^T vektor pravých strán .
Sústavu lineárnych rovníc môžeme zapísať v tvare

<math>Ax=b</math>

kde
<math>
A=
\begin{bmatrix}
a_{11} & \cdots & a_{1n} \\
\vdots & \ddots & \vdots \\
a_{n1} & \cdots & a_{nn}
\end{bmatrix},
x=
\begin{bmatrix}
x_{1}\\
\vdots\\
x_{n}
\end{bmatrix},
b=
\begin{bmatrix}
b_{1}\\
\vdots\\
b_{n}
\end{bmatrix}
</math>(1.2)

Rozlišujeme dva základné typy matíc sústav lineárnych rovníc:
;Plné:systémy, kde je väčšina prvkov nenulových
;Riedke:kde je naopak väčšina prvkov rovná nule. Túto ich vlastnosť možno využiť na riešenie prostredníctvom menšieho počtu krokov [4] [5].

==Matice==

Matica typu m[[Image:Untitled%201_html_4e44f889.png]]n je sústava mn čísiel, ktoré sú usporiadané v tvare obdĺžnikovej tabuľky. Všeobecná matica typu m[[Image:Untitled%201_html_4e44f889.png]]n je opísaná nasledovne:

A=[[Image:Untitled%201_html_m7af6f254.png]]

Prvok v i-tom riadku a j-tom stĺpci označujeme [[Image:Untitled%201_html_m49e52707.png]] (i=1, ..., m , j=1, ..., n)sú reálne prvky matice.

Matica A=[[Image:Untitled%201_html_m6a6585d2.png]]sa nazýva štvorcová ak m=n, teda ak má rovnaký počet riadkov a stĺpcov.

A=[[Image:Untitled%201_html_2dcaaa4e.png]]

Dôležitou štvorcovou je tzv. '''identická''' alebo '''jednotková matica'''. Jednotková matica má na diagonále jednotky a ostatné prvky u nulové. Označujeme ju písmenom I.

I=[[Image:Untitled%201_html_7d6b44a2.png]]

Pri násobení matíc má identická matica postavenie analogické číslu 1 pri násobení reálnych čísel. A*I=I*A=A

'''Transponovaná matica''' , je matica ktorá vznikne vymenením prvkov pôvodnej matice. Vymení sa súradnica riadku za súradnicu stĺpca. Potom transponovaná matica k matici A je :

AT<nowiki>=</nowiki>[[Image:Untitled%201_html_39d2bb89.png]]

'''Inverzná matica '''[[Image:Untitled%201_html_m7e0b28e3.png]] k štvorcovej [[Image:Untitled%201_html_696253c7.png]] matici A je taká , pre ktorú platí [[Image:Untitled%201_html_m5456b175.png]] , kde I je identická matica typu [[Image:Untitled%201_html_696253c7.png]]. K matici A existuje inverzná matica vtedy, keď je determinant matice A nenulový. Matica, ku ktorej existuje inverzná matica sa nazýva '''regulárna '''<nowiki>matica[5][6]. </nowiki>

=== Diagonálne matice ===
Diagonálna matica A je štvorcová matica typu n x n ktorá má nenulové prvky na hlavnej diagonále.

Existujú aj bidiagonálne a trojdiagonálne matice. Bidiagonálna matica je taká diagonálna matica, ktorá má ešte navyše nenulové horné (horná bidiagonálna matica) alebo dolné susedné prvky k diagonále (dolná bidiagonálna matica).

Horná bidiagonálna matica

[[Image:Untitled%201_html_6c55de17.png]]

Dolná bidiagonálna matica

[[Image:Untitled%201_html_m1022a49c.png]]

Ak sú nenulové horné aj dolné susedné prvky ku diagonálne, vtedy hovorí o trojdiagonálnej matici.

[[Image:Untitled%201_html_m7667af1.png]]

Na rozdiel od trojdiagonálnych systémov, ktoré majú nenulové prvky len na diagonále

plus a mínus jeden, '''skupinovo diagonálne systémy''' sú všeobecnejšie. Majú m1 ≥ 0 nenulových prvkov priamo vľavo(pod)od diagonály a m2<nowiki> ≥ 0 nenulových prvkov napravo(nad)od diagonály[6]. Diagonály nachádzajúce sa nad hlavnou diagonálou sa nazývajú superdiagonály. Subdiagonály sú naopak diagonály, ktoré sa nachádzajú pod hlavnou diagonálou. </nowiki>

=== Trojuholníkové matice ===
Trojuholníkové matice sú také matice, kde všetky prvky pod alebo nad diagonálou sú

nulové. Keď sú nulové prvky nad diagonálou hovoríme o dolnej trojuholníkovej matici, a naopak keď sú nulové prvky pod hlavnou diagonálou hovoríme o hornej trojuholníkovej matici .

Dolná trojuholníková matica Horná trojuholníková matica

[[Image:Untitled%201_html_mad4a9fb.png]] [[Image:Untitled%201_html_73ceb1e2.png]]

<nowiki>[5][6]</nowiki>

=== Blokové matice ===
Blokové matice sa používajú pre zjednodušenie počítania s maticami veľkých rozmerov.

Bloková matica je nejaká maticu A, ktorú rozdelíme na bloky [[Image:Untitled%201_html_1762b84b.png]].

Majme nasledovnú maticu A.

A = [[Image:Untitled%201_html_4ffcae58.png]]

Potom môžeme danú maticu zapísať nasledovne:

A=[[Image:Untitled%201_html_m21ac2751.png]]

kde je blok matice Aij tvorený prvkami matice A:

A11 = [[Image:Untitled%201_html_m3d3ac50a.png]] A12 = [[Image:Untitled%201_html_4a93fe51.png]]

A21 = [[Image:Untitled%201_html_m12099fb8.png]] A22 = [[Image:Untitled%201_html_757e3860.png]]

<nowiki>[3][6]</nowiki>

=== Ortogonálne matice ===
Ortogonálna matica (matica s ortonormálnymi stĺpcami) je matica so stĺpcami jednotkovej dĺžky, ktoré sú na seba kolmé. Matica typu [[Image:Untitled%201_html_696253c7.png]] je ortogonálna, ak [[Image:Untitled%201_html_12aad0e5.png]]. Podľa tejto rovnice má matica Q inverznú maticu a  platí [[Image:Untitled%201_html_m5665d8ff.png]] . Potom platí [[Image:Untitled%201_html_m34195d4f.png]]<nowiki>. Potom tieto tri vzťahy sú ekvivalentné a môžeme ich považovať za definíciu ortogonálnej matice [6].

Softvérové balíky pre riešenie veľkých lineárnych systémov

2010-05-30T21:49:53Z

Repto:

[[Kategória:Študentské práce]]
[[Kategória:Ročníkové práce]]
[[Kategória:Matematika]]
{{Praca_uvod|5|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__
= =

'''Softvérové balíky pre riešenie veľkých lineárnych systémov'''

Riešenie sústav lineárnych rovníc je základom riešenia mnohých problémov vo vedeckých výpočtoch. V mnohých prípadoch sú riešené sústavy veľmi veľké a matica sústavy je riedka. V mnohých aplikáciách je matica symetrická, ako je to napríklad pri použití metódy konečných prvkov. Za posledné desaťročia bolo navrhnutých množstvo nových algoritmov a taktiež programových balíkov pre riešenie symetrických riedkych matíc , ktoré implementujú tieto algoritmy. V tejto časti sú uvedené niektoré balíky obsahujúce priame riešiče riedkych lineárnych systémov.

Priame riešiče riedkych systémov pracujú v niekoľkých fázach. Presné rozdelenie do jednotlivých fáz závisí od použitého algoritmu a softvéru, všeobecné rozdelenie je nasledovné:

# Usporiadanie na základe štruktúry.
# Analýza štruktúry matice na základe, ktorej sa zavedú potrebné  dátové štruktúry pre efektívny rozklad matice
# Rozklad matice
# Fáza riešenia, kde sa vykoná eliminácia a potom následne spätná substitúcia.

Fáza rozkladu matice je obvykle časovo najnáročnejšia. Naopak fáza riešenia je všeobecne omnoho rýchlejšia.

'''Algoritmy rozkladu matíc'''

Rozklad môže vykonaný rôznymi spôsobmi, čo závisí od prístupu k jednotlivým prvkom systému. Existujú tri základné typy algoritmov : left-looking, right-looking a multifrontal.

Pri right-looking prístupe sa v každom kroku vypočítajú riadky a stĺpce a a tieto zmeny sa hneď aplikujú. Pri left-looking algoritme sa vypočítané zmeny neaplikujú hneď. Predtým ako je eliminovaný stĺpec ''k'' , všetky zmeny z predchádzajúcich stĺpcov ''k'' matice L sa použijú spolu so stĺpcom ''k'' matice A. Pri multifrontálnom algoritme sa zmeny akumulujú, a potom sa aplikujú prostredníctvom tzv. eliminačného stromu.

Niektoré knižnice pre priame riešenie riedkych systémov

'''PARDISO '''umožňuje paralelné a sériové riešenie nesymetrických a symetrických riedkych systémov na multiprocesorovom systéme so zdieľanou pamäťou .Využíva sa tu left-looking a right-looking verzia Choleského rozkladu.

'''SPOOLES''' je knižnica pre riešenie riedkych reálnych a komplexných sústav rovníc . Je dostupná v paralelnej aj sériovej verzii. Používa sa tu verzia Gaussovej eliminačnej metódy s Croutovou redukciou .

'''TAUCS''' je navrhnutá pre symetrické kladne definitné systémy . Používa sa tu left-looking a multifrontálne verzie LU rozkladu a Choleského rozkladu.

'''UMFPACK '''<nowiki>je knižnica pre riešenie nesymetrických systémov. Využíva nesymetrický multifrontálny LU rozklad [14]. </nowiki>

== Simulačný softvér ==
Existuje viacero softvérov, ktoré používajú metódu konečných prvkov. Pomocou tejto metódy sa transformuje systém parciálnych diferenciálnych rovníc, ktoré popisujú danú úlohu na systém lineárnych rovníc . Táto metóda sa používa v mnohých odvetviach : napr. pri návrhu strojov, rôznych súčiastok, atď.

Pri metóde konečných prvkov sa väčšinou dostávame k veľkému systému lineárnych rovníc . Pre jeho riešenie simulačné softvéry používajú niektoré z uvedených moderných metód . Je známych viacero softvérov ktoré pracujú s metódou konečných prvkov napr. ANSYS, COMSOL, FEMM, ELMER Multiphysics a mnoho ďalších. Pre riešenie vzniknutých veľkých sústav lineárnych rovníc používajú rôzne moderné metódy riešenia. V tab. 1 sú uvedené metódy používané v niektorých simulačných programoch.

'''Tab. č. 1 Metódy používané v simulačných softvéroch '''

{| style="border-spacing:0;"
| style="border-top:0.0361in double #000000;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:none;padding:0.0729in;"| <center>'''FEMM'''</center>
| style="border-top:0.0361in double #000000;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:none;padding:0.0729in;"| <center>'''ANSYS'''</center>
| style="border-top:0.0361in double #000000;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:none;padding:0.0729in;"| <center>'''COMSOL'''</center>
| style="border:0.0361in double #000000;padding:0.0729in;"| <center>'''Elmer Multiphysics'''</center>

|-
| style="border-top:none;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:none;padding:0.0729in;"| <center>CG</center>
| style="border-top:none;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:none;padding:0.0729in;"| <center>iteračné gradientné metódy </center>
| style="border-top:none;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:none;padding:0.0729in;"| <center>knižnica UMFPACK</center>
| style="border-top:none;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:0.0361in double #000000;padding:0.0729in;"| <center>knižnica UMFPACK</center>

|-
| style="border-top:none;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:none;padding:0.0729in;"| <center>BCG</center>
| style="border-top:none;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:none;padding:0.0729in;"| <center>AMG</center>
| style="border-top:none;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:none;padding:0.0729in;"| <center>GMRES</center>
| style="border-top:none;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:0.0361in double #000000;padding:0.0729in;"| <center>AMG a GMG</center>

|-
| style="border-top:none;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:none;padding:0.0729in;"| <center> </center>
| style="border-top:none;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:none;padding:0.0729in;"| <center> </center>
| style="border-top:none;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:none;padding:0.0729in;"| <center> </center>
| style="border-top:none;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:0.0361in double #000000;padding:0.0729in;"| <center>iteračné gradientné metódy </center>

|}
'''Ukážkový príklad analýzy vo FEMM'''

FEMM je softvérový balík pre riešenie nízkofrekvenčných elektromagnetických úloh v 2D. Pre <nowiki>riešenie vzniknutého systému lineárnych rovníc podľa typu riešeného problému používa buď metódu konjugovaných gradientov s prepodmienením alebo metódu bikonjugovaných gradientov [15].</nowiki>

Na (obr.4) je 2D model asynchrónneho motora, pre ktorý hľadáme rozloženie potenciálu.

Obr. 4 Model asynchrónneho motora vo FEMM

Daná úloha má [[Image:Untitled%201_html_49f63057.png]] stupňov voľnosti, teda sa rieši maticová rovnica s maticou systému o rozmeroch [[Image:Untitled%201_html_m3ca83b85.png]].

[[Image:Untitled%201_html_d245593.png]]Obr. 5 Rozloženie poľa asynchrónneho motora

Na (obr. 5) je vyriešené rozloženie potenciálu pre daný asynchrónny motor. Riešenie danej úlohy metódou bikonjugovaných gradientov prostredníctvom softvéru FEMM trvalo 3 minúty. Riešenie bolo realizované na počítači s procesorom AMD Turion X2 Dual-Core 2.20 GHz a s operačnou pamäťou 4 GB.

=Záver=
Cieľom mojej práce bolo oboznámiť sa s riešením sústav veľkých lineárnych rovníc a opísať a porovnať niektoré z existujúcich algoritmov. V práci som sa zameral na opis niektorých existujúcich algoritmov pre riešenie sústav lineárnych rovníc.
V práci sú opísané niektoré klasické algoritmy pre riešenie sústav lineárnych rovníc. Cramerovo pravidlo a riešenie pomocou inverznej matice sú vhodné len pre veľmi malé sústavy. Gaussova eliminačná metóda taktiež pre veľké matice nie je príliš vhodná, pretože je potrebné veľké množstvo operácií pre riešenie veľkých sústav. Takisto pri eliminácii môžu vzniknúť chyby. Preto sa skôr používajú jej modifikácie. Klasické iteračné metódy: Jacobiho a Gauss – Seidelova sú vhodné pre väčšie matice a riedke matice. Keďže množstvo nulových prvkov v riedkych maticiach znižuje počet potrebných operácií a výpočtovú náročnosť, sú tieto metódy vhodné aj pre veľké riedke sústavy lineárnych rovníc.
Ďalšia časť sa zaoberá priamymi metódami pre riešenie veľkých sústav. Sú tu opísané dva algoritmy rozkladu pre zjednodušenie veľkých matíc: LU rozklad a Choleského rozklad. Je viacero metód, ako možno rozložiť maticu do podoby niektorého z rozkladov. Na týchto rozkladoch sú založené niektoré moderné priame metódy. V tejto práci sú opísané len základné algoritmy, ako možno tieto rozklady uskutočniť.
Hlavná časť práce je venovaná moderným iteračným metódam riešenia veľkých sústav. Pozornosť sa tu venuje tzv. gradientným metódam a multigridovým metódam. Pri gradientných metódach sa zostrojí postupnosť vektorov , ktorá konverguje k riešeniu sústavy. Metóda konjugovaných gradientov je vhodná len pre symetrické kladne definitné matice, naopak metóda bikonjugovaných gradientov a GMRES sa používajú pre nesymetrické systémy. Je tu vypracovaný aj ukážkový príklad riešenia sústavy malých rozmerov prostredníctvom metódy konjugovaných gradientov. Ďalej sa táto časť zaoberá multigridovými metódami. Geometrické multigridové metódy vyžadujú informáciu o hierarchii daného systému, naopak algebraické multigridové metódy nepotrebujú túto hierarchiu poznať. Algebraické sú vhodnejšie pre úlohy s neregulárnou štruktúrou. Pre objasnenie metódy geometrického multigridu sme vypracovali ukážkový príklad riešenia jednoduchej úlohy.
Posledná časť práce sa zaoberá aplikáciou a použitím daných metód. Sú tu opísané niektoré knižnice ktoré v sebe implementujú niektoré z uvedených metód. Taktiež sú tu opísané simulačné programy, ktoré využívajú niektoré z týchto metód a knižníc.

=Použitá literatúra=
#Parallel Algorithms for Matrix Computations. Philadelphia : Society for Industrial and Applied Mathematics, 1990. 195 s. ISBN 0898712602
#TIMOTHY A. Davis: Direct Methods for Sparse Linear Systems : Fundamentals of Algorithms. Society for Industrial and Applied Mathematic, 2006. 217 s. ISBN 0898716136.
#GOLUB G. H. , Van Loan Ch. F., Matrix computations, The John Hopkins University Press, 1996. 694 s. ISBN 0801854148
#FAJMON, Bretislav , RUŽICKOVÁ, Irena. Matematika 3. Brno : Vysoké Učení Technické v Brne, 2005. 252 s. Dostupný z WWW: <http://www.umat.feec.vutbr.cz/~fajmon/inm/matematika3.pdf>.
#Skriptá, Bratislava: STU, Dostupný z WWW:<http://www-kmadg.svf.stuba.sk/skripta/index.html>.
#DOBÁK, Radoslav. Využitie blokových matíc pri riešení úloh lineárnej algebry . Bratislava, 2009. 51 s. Univerzita Komenského v Bratislave. Dostupné z WWW: <http://www.iam.fmph.uniba.sk/studium/efm/diplomovky/2009/dobak/diplomovka.pdf >
#Prednáška 4 : Numerické metódy matematiky I. Dostupný z WWW: <http://fyzikazeme.sk/mainpage/stud_mat/menm/prednaska4.pdf>
#Brezová Martina. Choleského metóda. 2006. Bratislava. Dostupný z WWW:< http://www.mtakac.com/aap/ref/brezova.pdf>
#Prednáška 5 : Numerické metódy matematiky I. Dostupný z WWW: <http://fyzikazeme.sk/mainpage/stud_mat/menm/prednaska5.pdf>
#Wikipedia [online]. 2007, 19.4.2010 [cit. 2010-05-2]. Conjugate gradient method. Dostupné z WWW: <http://en.wikipedia.org/wiki/Conjugate_gradient_method>.
#SAAD, Y. Iterative Methods for Sparse Linear Systems. Manchester , 2000. 447 s. Dostupné z WWW: <http://www.stanford.edu/class/cme324/saad.pdf>.
#KALTENBACHER, Manfred. Numerical Simulation of Mechatronic Sensors and Actuators. 2nd Edition. Berlin : Springer, 2007. 428 s. ISBN 978-3-540-71359-3.
#HULSEMANN, Frank. Parallel Geometric Multigrid ,2008. 44 s. Dostupné z WWW: <http://www10.informatik.unierlangen.de/Publications/Papers/2005/PGM_LNCSE51.pdf>.
#GOULD, N.; HU, Y.; SCOTT, J. A numerical evaluation of sparse direct solvers [online]. 2005 [cit. 2010-05-09]. Dostupné z WWW: <ftp://ftp.numerical.rl.ac.uk/pub/reports/ghsRAL200505.pdf>.
#MEEKER, David. Finite Element Method Magnetics User’s Manual [online]., 2007, 5.2.2009 [cit. 2010-05-09]. Dostupné z WWW: <http://www.femm.info/Archives/doc/manual42.pdf>.
#ŠTEPANOVSKÝ, Michal. Metóda konečných prvkov : Sprievodný materiál k semináru IT Power Knowledge
#BRIGGS, William. A Multigrid Tutorial.. 119 s. Dostupné z WWW: <http://www.cfm.brown.edu/people/gk/APMA2821F/mgtut_part1.pdf>.

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

2010-05-30T21:48:22Z

Repto: /* Algoritmy riešenia trojuholníkových systémov */

[[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 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:

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

kde l11<nowiki>=1 je skalár a všetky tri matice sú štvorcové matice. Sú možné aj iné varianty ako zvoliť l</nowiki>11. V tomto prípade dostaneme dolnú trojuholníkovú maticu a š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 so základným argumentom (3.4) a induktívny predpoklad z rovnice (3.5) [3].</nowiki>[[Image:Untitled%201_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 [[Image:Untitled%201_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 [[Image:Untitled%201_html_m7ba66b87.png]]n, je permutačná matica ktorá vymieňa dva riadky A tak, že

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

a [[Image:Untitled%201_html_c0f008f.png]]. Ak rovnica (3.1) a 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 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 ú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 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 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'' je [[Image:Untitled%201_html_m1f50f11c.png]]symetrická 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 [[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 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 a hľadaná matica L sú blokové matice [[Image:Untitled%201_html_696253c7.png]] so štvorcovými diagonálnymi blokmi . Vyjadrením (i,j) v 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, 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 porovnaní s LU rozkladom o 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 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 : [[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 rozmeroch n-1. [[Image:Untitled%201_html_m1e0dd299.png]] sú stĺpcové vektory o dĺžke n-1. [[Image:Untitled%201_html_m6ac242f3.png]] sú skaláry. Toto vedie k 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 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 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<nowiki>= </nowiki> xj / ljj

'''for''' i > j, lij[[Image:Untitled%201_html_m6647c5ea.png]] '''do'''

xj<nowiki>= </nowiki>xj – lij xj<nowiki>;</nowiki>

'''end for'''

'''end for'''

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

x=b;

x1 <nowiki>= </nowiki>x1 / l11 <nowiki>;</nowiki>

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

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

xj<nowiki>= </nowiki> xj – lij xj<nowiki>;</nowiki>

'''end for'''

xi<nowiki>= x</nowiki>i / lii<nowiki>;</nowiki>

'''end for'''

Pre riešenie Ux = b , kde U 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 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 z prvej (3.19) dostávame [[Image:Untitled%201_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].

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

2010-05-30T21:45:43Z

Repto: /* Algoritmy riešenia trojuholníkových systémov */

[[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 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:

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

kde l11<nowiki>=1 je skalár a všetky tri matice sú štvorcové matice. Sú možné aj iné varianty ako zvoliť l</nowiki>11. V tomto prípade dostaneme dolnú trojuholníkovú maticu a š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 so základným argumentom (3.4) a induktívny predpoklad z rovnice (3.5) [3].</nowiki>[[Image:Untitled%201_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 [[Image:Untitled%201_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 [[Image:Untitled%201_html_m7ba66b87.png]]n, je permutačná matica ktorá vymieňa dva riadky A tak, že

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

a [[Image:Untitled%201_html_c0f008f.png]]. Ak rovnica (3.1) a 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 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 ú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 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 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'' je [[Image:Untitled%201_html_m1f50f11c.png]]symetrická 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 [[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 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 a hľadaná matica L sú blokové matice [[Image:Untitled%201_html_696253c7.png]] so štvorcovými diagonálnymi blokmi . Vyjadrením (i,j) v 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, 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 porovnaní s LU rozkladom o 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 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 : [[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 rozmeroch n-1. [[Image:Untitled%201_html_m1e0dd299.png]] sú stĺpcové vektory o dĺžke n-1. [[Image:Untitled%201_html_m6ac242f3.png]] sú skaláry. Toto vedie k 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 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 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<nowiki>= </nowiki> xj / ljj

'''for''' i > j, lij[[Image:Untitled%201_html_m6647c5ea.png]] '''do'''

xj<nowiki>= </nowiki>xj – lij xj<nowiki>;</nowiki>

'''end for'''

'''end for'''

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

x=b;

x1 <nowiki>= </nowiki>x1 / l11 <nowiki>;</nowiki>

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

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

xj<nowiki>= </nowiki> xj – lij xj<nowiki>;</nowiki>

'''end for'''

xi<nowiki>= x</nowiki>i / lii<nowiki>;</nowiki>

'''end for'''

Pre riešenie Ux = b , kde U 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 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 z prvej (3.19) dostávame [[Image:Untitled%201_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].

Moderné metódy riešenia veľkých sústav lineárnych rovníc

2010-05-30T21:44:37Z

Repto: /* Matice */

[[Kategória:Študentské práce]]
[[Kategória:Ročníkové práce]]
[[Kategória:Matematika]]
{{Draft}}
{{Hlavička_FM
|{{PAGENAME}}|Bc. Peter Poruban|Ing. Michal Štepanovský, PhD
|2009/2010
|Ročníková práca
|Mechatronika
}}
{{Praca_uvod|1|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||||||||||}}
{{abstrakt
|Práca sa zaoberá metódami vhodnými pre riešenie veľkých sústav lineárnych rovníc. Prvá časť sa zaoberá klasickými metódami pre riešenie sústav lineárnych rovníc. V ďalšej časti sú opísané priame metódy riešenia veľkých sústav . Tretia časť sa venuje moderným iteračným metódam. V práci sa podrobne zaoberáme metódou konjugovaných gradientov a geometrickou multigridovou metódou. Pre tieto dve metódy sme vypracovali ukážkové príklady riešenia. Posledná časť sa zaoberá využitím týchto metód.
|
}}
__TOC__
'''Úvod'''

V technickej praxi je častou úlohou riešiť sústavu lineárnych rovníc Ax= b s maticou rádu n, kde n je veľké číslo. Rozmery týchto matíc môžu byť rádovo v státisícoch, ale aj väčšie. Pri takýchto sústavách lineárnych rovníc sú niektoré tradičné metódy nepoužiteľné alebo sú neefektívne a časovo náročné. Taktiež niektoré z nich môžu pri maticiach veľmi veľkých rozmerov alebo zle podmienených maticiach zlyhať.
Stretávame sa s dvomi typmi systémov lineárnych rovníc. Systém lineárnych rovníc sa nazýva plný, ak väčšina prvkov je nenulová. Naopak riedke systémy sú také, kde len relatívne málo prvkov je nenulových. Pre riešenie riedkych systémov možno využiť ich vlastnosti. Vďaka tomu možno riešiť prostredníctvom niektorých algoritmov tieto matice efektívnejšie. Veľké riedke systémy je v technickej praxi veľmi často potrebné riešiť, napr. pri riešení parciálnych diferenciálnych rovníc.
Metódy pre riešenie lineárnych rovníc delíme na priame metódy a iteračné metódy. Priame metódy vedú k riešeniu po konečnom počte krokov. Naopak iteračné metódy konvergujú k riešeniu a presnosť riešenia je závislá od počtu iterácií . Priame metódy sú všeobecne vhodnejšie pre plné matice, naopak pre riedke systémy sú vhodné iteračné metódy.
Známe sú klasické priame metódy ako Cramerovo pravidlo, použitie inverznej matice a Gaussova eliminačná metóda. Tieto však nie sú pre systémy veľkých rozmerov vhodné. Taktiež sú známe klasické iteračné algoritmy ako je Jacobiho metóda a Gauss Seidelova metóda. Tieto sú vhodné aj pre riedke matice veľkých rozmerov.
Pre priame riešenie veľkých sústav je známych niekoľko algoritmov. V tejto práci je opísaný LU rozklad a Choleského rozklad. Tieto rozklady sa v rôznych obmenených podobách používajú pre priame riešenie veľkých sústav lineárnych rovníc.
V posledných desaťročiach bolo vypracovaných niekoľko moderných iteračných algoritmov pre riešenie veľkých sústav lineárnych rovníc. V práci sa zaoberáme gradientnými metódami a multigridovými metódami. Metóda konjugovaných gradientov konverguje k riešeniu rýchlejšie ako klasické iteračné metódy a je výhodná hlavne pre symetrické kladne definitné matice. Naopak, metóda bikonjugovaných gradientov a metóda GMRES sú vhodné aj pre nesymetrické matice. Multigridové metódy patria medzi najrýchlejšie iteračné metódy. Zlepšujú konvergenciu tým, že sa daná úloha opísaná určitou sieťou vyrieši najprv pre redšiu sieť a potom sa toto riešenie použije pri hľadaní riešenia v hustejšej sieti.

=Sústavy lineárnych rovníc a matice=
V tejto časti sú opísané základné pojmy lineárnej algebry , ktoré súvisia s výpočtom
sústav lineárnych rovníc . Taktiež sú tu opísané rôzne tvary matíc, ktoré sa používajú pri riešení sústav lineárnych rovníc.
==Systémy lineárnych rovníc==
Riešenie sústav lineárnych rovníc patrí medzi najdôležitejšie časti matematiky. Množstvo praktických úloh nakoniec vedie k riešeniu takýchto sústav. Tieto sústavy môžu byť často veľmi rozsiahle. Vtedy je n veľké číslo.
Systém n - lineárnych rovníc:

<math>
\begin{matrix}
a_{11}x_1+a_{12}x_2+...+a_{1n}x_n\\
a_{21}x_1+a_{22}x_2+...+a_{2n}x_n\\
.\\
.\\
.\\
a_{n1}x_1+a_{n2}x_2+...+a_{nn}x_n
\end{matrix}
</math>(1.1)

s neznámymi x1,x2,...,xn.

Matica A(i,j) , kde i,j=1,..... n, sa nazýva maticou sústavy stĺpcový vektor b =(b1, ...., bn)^T vektor pravých strán .
Sústavu lineárnych rovníc môžeme zapísať v tvare

<math>Ax=b</math>

kde
<math>
A=
\begin{bmatrix}
a_{11} & \cdots & a_{1n} \\
\vdots & \ddots & \vdots \\
a_{n1} & \cdots & a_{nn}
\end{bmatrix},
x=
\begin{bmatrix}
x_{1}\\
\vdots\\
x_{n}
\end{bmatrix},
b=
\begin{bmatrix}
b_{1}\\
\vdots\\
b_{n}
\end{bmatrix}
</math>(1.2)

Rozlišujeme dva základné typy matíc sústav lineárnych rovníc:
;Plné:systémy, kde je väčšina prvkov nenulových
;Riedke:kde je naopak väčšina prvkov rovná nule. Túto ich vlastnosť možno využiť na riešenie prostredníctvom menšieho počtu krokov [4] [5].

==Matice==

Matica typu m[[Image:Untitled%201_html_4e44f889.png]]n je sústava mn čísiel, ktoré sú usporiadané v tvare obdĺžnikovej tabuľky. Všeobecná matica typu m[[Image:Untitled%201_html_4e44f889.png]]n je opísaná nasledovne:

A=[[Image:Untitled%201_html_m7af6f254.png]]

Prvok v i-tom riadku a j-tom stĺpci označujeme [[Image:Untitled%201_html_m49e52707.png]] (i=1, ..., m , j=1, ..., n)sú reálne prvky matice.

Matica A=[[Image:Untitled%201_html_m6a6585d2.png]]sa nazýva štvorcová ak m=n, teda ak má rovnaký počet riadkov a stĺpcov.

A=[[Image:Untitled%201_html_2dcaaa4e.png]]

Dôležitou štvorcovou je tzv. '''identická''' alebo '''jednotková matica'''. Jednotková matica má na diagonále jednotky a ostatné prvky u nulové. Označujeme ju písmenom I.

I=[[Image:Untitled%201_html_7d6b44a2.png]]

Pri násobení matíc má identická matica postavenie analogické číslu 1 pri násobení reálnych čísel. A*I=I*A=A

'''Transponovaná matica''' , je matica ktorá vznikne vymenením prvkov pôvodnej matice. Vymení sa súradnica riadku za súradnicu stĺpca. Potom transponovaná matica k matici A je :

AT<nowiki>=</nowiki>[[Image:Untitled%201_html_39d2bb89.png]]

'''Inverzná matica '''[[Image:Untitled%201_html_m7e0b28e3.png]] k štvorcovej [[Image:Untitled%201_html_696253c7.png]] matici A je taká , pre ktorú platí [[Image:Untitled%201_html_m5456b175.png]] , kde I je identická matica typu [[Image:Untitled%201_html_696253c7.png]]. K matici A existuje inverzná matica vtedy, keď je determinant matice A nenulový. Matica, ku ktorej existuje inverzná matica sa nazýva '''regulárna '''<nowiki>matica[5][6]. </nowiki>

=== Diagonálne matice ===
Diagonálna matica A je štvorcová matica typu n x n ktorá má nenulové prvky na hlavnej diagonále.

Existujú aj bidiagonálne a trojdiagonálne matice. Bidiagonálna matica je taká diagonálna matica, ktorá má ešte navyše nenulové horné (horná bidiagonálna matica) alebo dolné susedné prvky k diagonále (dolná bidiagonálna matica).

Horná bidiagonálna matica Dolná bidiagonálna matica

[[Image:Untitled%201_html_6c55de17.png]] [[Image:Untitled%201_html_m1022a49c.png]]

Ak sú nenulové horné aj dolné susedné prvky ku diagonálne, vtedy hovorí o trojdiagonálnej matici.

[[Image:Untitled%201_html_m7667af1.png]]

Na rozdiel od trojdiagonálnych systémov, ktoré majú nenulové prvky len na diagonále

plus a mínus jeden, '''skupinovo diagonálne systémy''' sú všeobecnejšie. Majú m1 ≥ 0 nenulových prvkov priamo vľavo(pod)od diagonály a m2<nowiki> ≥ 0 nenulových prvkov napravo(nad)od diagonály[6]. Diagonály nachádzajúce sa nad hlavnou diagonálou sa nazývajú superdiagonály. Subdiagonály sú naopak diagonály, ktoré sa nachádzajú pod hlavnou diagonálou. </nowiki>

=== Trojuholníkové matice ===
Trojuholníkové matice sú také matice, kde všetky prvky pod alebo nad diagonálou sú

nulové. Keď sú nulové prvky nad diagonálou hovoríme o dolnej trojuholníkovej matici, a naopak keď sú nulové prvky pod hlavnou diagonálou hovoríme o hornej trojuholníkovej matici .

Dolná trojuholníková matica Horná trojuholníková matica

[[Image:Untitled%201_html_mad4a9fb.png]] [[Image:Untitled%201_html_73ceb1e2.png]]

<nowiki>[5][6]</nowiki>

=== Blokové matice ===
Blokové matice sa používajú pre zjednodušenie počítania s maticami veľkých rozmerov.

Bloková matica je nejaká maticu A, ktorú rozdelíme na bloky [[Image:Untitled%201_html_1762b84b.png]].

Majme nasledovnú maticu A.

A = [[Image:Untitled%201_html_4ffcae58.png]]

Potom môžeme danú maticu zapísať nasledovne:

A=[[Image:Untitled%201_html_m21ac2751.png]]

kde je blok matice Aij tvorený prvkami matice A:

A11 = [[Image:Untitled%201_html_m3d3ac50a.png]] A12 = [[Image:Untitled%201_html_4a93fe51.png]]

A21 = [[Image:Untitled%201_html_m12099fb8.png]] A22 = [[Image:Untitled%201_html_757e3860.png]]

<nowiki>[3][6]</nowiki>

=== Ortogonálne matice ===
Ortogonálna matica (matica s ortonormálnymi stĺpcami) je matica so stĺpcami jednotkovej dĺžky, ktoré sú na seba kolmé. Matica typu [[Image:Untitled%201_html_696253c7.png]] je ortogonálna, ak [[Image:Untitled%201_html_12aad0e5.png]]. Podľa tejto rovnice má matica Q inverznú maticu a  platí [[Image:Untitled%201_html_m5665d8ff.png]] . Potom platí [[Image:Untitled%201_html_m34195d4f.png]]<nowiki>. Potom tieto tri vzťahy sú ekvivalentné a môžeme ich považovať za definíciu ortogonálnej matice [6].

Klasické metódy riešenia sústav lineárnych rovníc

2010-05-30T21:43:08Z

Repto:

[[Kategória:Študentské práce]]
[[Kategória:Ročníkové práce]]
[[Kategória:Matematika]]
{{Praca_uvod|2|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__
= =
Existuje viacero metód riešenia lineárnych sústav rovníc. Poznáme dva základné typy metód: priame a iteračné metódy. Pre husté systémy, je vo väčšine prípadoch vhodnejšie použiť priame metódy naopak pri väčších riedkych maticiach sú vo väčšine prípadov vhodnejšie iteračné metódy
==Priame metódy==

Metódu riešenia sústavy, ktorá vedie k riešeniu po konečnom počte krokov, nazývame '''priama metóda'''. Základným princípom priamych metód je eliminácia.

=== Cramerovo pravidlo ===
Majme sústavu (1.1) . Ak je matica sústavy regulárna, teda determinant sústavy je nenulový, potom riešenie sústavy možno určiť nasledovne:

[[Image:Untitled%201_html_51683075.png]] , [[Image:Untitled%201_html_m3491dee3.png]] kde D je determinant matice sústavy A a [[Image:Untitled%201_html_18d6a5a7.png]] pre k=1, ... ,n sú determinanty matíc, ktoré vzniknú z matice A nahradením k-teho stĺpca tejto matice vektorom pravých strán b. Cramerovo pravidlo je vhodné len pre veľmi malé sústavy lineárnych rovníc. Pre väčšie sústavy by bolo potrebné počítať mnoho determinantov vysokého rádu, čo je dosť náročné. Preto sa táto metóda pre riešenie veľkých sústav nepoužíva.

=== Riešenie pomocou inverznej matice ===
Uvažujme sústavu (1.1) . Keďže je matica sústavy regulárna, existuje k nej inverzná matica

A-1 pre ktorú platí: [[Image:Untitled%201_html_5e10b471.png]] .

Potom platí [[Image:Untitled%201_html_m18a5a089.png]].

Potom z jednoznačnosti riešenia dostávame, že [[Image:Untitled%201_html_2884beac.png]]. Toto vyjadrenie riešenia sme dostali, tak že sme obe strany rovnosti [[Image:Untitled%201_html_3640367f.png]]zľava vynásobili maticou [[Image:Untitled%201_html_m7e0b28e3.png]]<nowiki> . Táto metóda tiež nie je vhodná pre matice väčších rozmerov [5].</nowiki>

=== Gaussova eliminačná metóda (GEM) ===
Základom tejto metódy je úprava sústavy na trojuholníkový tvar pomocou elementárnych riadkových úprav. Majme sústavu (1.1).

Teraz sa pomocou pričítania vhodných násobkov prvej rovnice z ostatných rovníc pokúsime eliminovať x1. Ak je prvok a11 rovný nule, vtedy vymeníme prvú rovnicu s prvou takou rovnicou, ktorej prvý prvok je nenulový. Keď budeme postupne odčítavať prvú rovnicu, vynásobenú číslom [[Image:Untitled%201_html_45c9b1ff.png]] , od i-tej rovnice , pre i=2,3, .... n , dostaneme

a11 x1 + a12 x2 + ··· + a1n xn = b1

a22 x2 + ··· + a2n xn = b2

an2 x2 + ··· + ann xn = b

Nové koeficienty vypočítame ako[[Image:Untitled%201_html_m66602679.png]] Teraz budeme pomocou vhodných násobkov druhej rovnice eliminovať x2 v tretej, štvrtej a n-tej rovnici. Opäť ak je a22<nowiki>=0, vymeníme druhú rovnicu s prvou z ďalších rovníc, v ktorej x</nowiki>2 je nenulová. Touto úpravou dostávame:

a11 x1 + a12 x2 + a13 x3 ··· + a1n xn = b1

a22 x2 + a23 x3 + ··· + a2n xn = b2

a33 x3 + ··· + a3n xn = b3

an3 x3+ ··· + ann xn = bn

kde [[Image:Untitled%201_html_m64a5d78.png]]

Ak pokračujeme ďalej rovnakým spôsobom , dostaneme po n-1 krokoch sústavu v trojuholníkovom  tvare

a11 x1 + a12 x2 + a13 x3 ··· + a1n xn = b1

a22 x2 + a23 x3 + ··· + a2n xn = b2

a33 x3 + ··· + a3n xn = b3

ann xn = bn

Z tejto sústavy potom ľahko určíme hľadané riešenie :

[[Image:Untitled%201_html_m16d60ed1.png]]

[[Image:Untitled%201_html_7d21c7ec.png]]

[[Image:Untitled%201_html_376a8cc5.png]]

Toto sa nazýva spätná substitúcia. Číslo [[Image:Untitled%201_html_62fe2ece.png]] sa nazýva hlavný prvok alebo pivot. Pre odstránenie zaokrúhľovacích chýb sa používa modifikácia GEM, takzvaná '''eliminácia s čiastočným výberom hlavného prvku. '''

V prvom kroku eliminácie nájdeme rovnicu, ktorá má pri neznámej x1 v absolútnej hodnote najväčší koeficient. Vymeníme ju s prvou rovnicou. Potom pomocou jej násobkou eliminujeme x1 s ostatných rovníc. Potom nájdeme medzi všetkými rovnicami okrem prvej rovnice takú, kde je najväčší koeficient pri neznámej x2. Vymeníme ju z druhou rovnicou a pomocou jej násobkov eliminujeme x2 z ďalších rovníc. Podobne pokračujeme ďalej. Všeobecne v k -tom kroku eliminácie nájdeme medzi poslednými n-k+1 rovnicami tú, ktorá má najväčší koeficient pri xk. Vymeníme ju s k –tou rovnicou a pomocou nej eliminujeme xk z nasledujúcej rovnice.

Gaussova eliminačná metóda je pre veľké matice veľmi časovo náročná. Vyžaduje n3 operácií . Preto je táto metóda vhodná len pre riešenie nie príliš rozsiahlych sústav lineárnych rovníc. Jej modifikácie <nowiki>sa používajú pri niektorých iných metódach [4][5].

</nowiki>

== Iteračné metódy ==
Druhou skupinou metód pre riešenie sústav lineárnych rovníc sú '''iteračné metódy'''. Iteračné metódy na rozdiel od priamych metód nevedú k presnému riešeniu po konečnom počte krokov. U iteračných metód sa zvolí počiatočná aproximácia riešenia a určitým postupom ju v každom kroku metódy zlepšujeme. K riešeniu sa približujeme postupne a väčšinou ho dosiahneme až v limite. Avšak výpočet nemožno prevádzať do nekonečna, preto ho po istom čase ukončíme. Výsledkom bude približné riešenie sústavy. Štandardné eliminačné metódy nie sú vhodné na riešenie väčších riedkych sústav lineárnych rovníc. Pretože v priebehu eliminácie postupne dochádza k zaplňovaniu pôvodne nenulových pozícií v matici sústavy - matica prestáva byť riedkou. Naopak iteračné metódy sú vhodné aj pre riešenie veľkých riedkych systémov, pretože nulové prvky v riedkych systémoch zjednodušujú iterácie. Vďaka tomu sa zjednodušuje výpočtová náročnosť.

=== Jacobiho metóda ===
Maticu A rozložíme na súčet [[Image:Untitled%201_html_m62e15c23.png]] , kde D je diagonálna matica, ktorá má rovnakú diagonálu ako A. L je dolná trojuholníková časť matice A a U je horná trojuholníková časť matice A

[[Image:Untitled%201_html_m50986641.png]] [[Image:Untitled%201_html_m6517c304.png]]

Jacobiho iteračnú metódu definujeme na základe rozkladu  [[Image:Untitled%201_html_2d246193.png]] , kde [[Image:Untitled%201_html_61ae277a.png]] a [[Image:Untitled%201_html_m428e7dc2.png]] a zapisujeme ju v tvare [[Image:Untitled%201_html_4b590df3.png]].

Sústava s diagonálnou maticou sa rieši ľahko. Ak ju zapíšeme po zložkách dostaneme

[[Image:Untitled%201_html_m1dd89cf1.png]]Analýzou vlastností iteračnej matice [[Image:Untitled%201_html_m500824df.png]] možno ukázať , že Jacobiho metóda konverguje , keď A je rýdzo diagonálne dominantná.

'''Definícia:''' Hovoríme, že matica[[Image:Untitled%201_html_m1fd48037.png]] je '''rýdzo diagonálne dominantná''', ak

<nowiki>Teda inými slovami, v každom riadku je absolútna hodnota diagonálneho prvku väčšia ako súčet absolútnych hodnôt ostatných prvkov tohto riadku [7] .</nowiki>

=== Gauss-Seidelova metóda ===
Je podobná ako Jacobiho metóda. Líši sa v tom že pri výpočte ďalšej aproximácie sa vždy použijú najnovšie približné hodnoty x1,x2,...,xn, ktoré sú k dispozícii.

V maticovom tvare : [[Image:Untitled%201_html_m136f2e51.png]]

Analýzou vlastností iteračnej matice [[Image:Untitled%201_html_m3f9eccb1.png]] možno ukázať , že Gauss – Seidelova metóda konverguje , keď A je rýdzo diagonálne dominantná alebo kladne definitná.

'''Definícia:''' Hovoríme, že matica A je pozitívne definitná, ak pre ľubovoľný nenulový vektor

X platí: [[Image:Untitled%201_html_m40da36b.png]] .

<nowiki>Gauss-seidelova metóda konverguje rýchlejšie, a vyžaduje približne polovicu iterácií oproti Jacobiho metóde [7].

Moderné metódy riešenia veľkých sústav lineárnych rovníc

2010-05-30T21:33:01Z

Repto:

[[Kategória:Študentské práce]]
[[Kategória:Ročníkové práce]]
[[Kategória:Matematika]]
{{Draft}}
{{Hlavička_FM
|{{PAGENAME}}|Bc. Peter Poruban|Ing. Michal Štepanovský, PhD
|2009/2010
|Ročníková práca
|Mechatronika
}}
{{Praca_uvod|1|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||||||||||}}
{{abstrakt
|Práca sa zaoberá metódami vhodnými pre riešenie veľkých sústav lineárnych rovníc. Prvá časť sa zaoberá klasickými metódami pre riešenie sústav lineárnych rovníc. V ďalšej časti sú opísané priame metódy riešenia veľkých sústav . Tretia časť sa venuje moderným iteračným metódam. V práci sa podrobne zaoberáme metódou konjugovaných gradientov a geometrickou multigridovou metódou. Pre tieto dve metódy sme vypracovali ukážkové príklady riešenia. Posledná časť sa zaoberá využitím týchto metód.
|
}}
__TOC__
'''Úvod'''

V technickej praxi je častou úlohou riešiť sústavu lineárnych rovníc Ax= b s maticou rádu n, kde n je veľké číslo. Rozmery týchto matíc môžu byť rádovo v státisícoch, ale aj väčšie. Pri takýchto sústavách lineárnych rovníc sú niektoré tradičné metódy nepoužiteľné alebo sú neefektívne a časovo náročné. Taktiež niektoré z nich môžu pri maticiach veľmi veľkých rozmerov alebo zle podmienených maticiach zlyhať.
Stretávame sa s dvomi typmi systémov lineárnych rovníc. Systém lineárnych rovníc sa nazýva plný, ak väčšina prvkov je nenulová. Naopak riedke systémy sú také, kde len relatívne málo prvkov je nenulových. Pre riešenie riedkych systémov možno využiť ich vlastnosti. Vďaka tomu možno riešiť prostredníctvom niektorých algoritmov tieto matice efektívnejšie. Veľké riedke systémy je v technickej praxi veľmi často potrebné riešiť, napr. pri riešení parciálnych diferenciálnych rovníc.
Metódy pre riešenie lineárnych rovníc delíme na priame metódy a iteračné metódy. Priame metódy vedú k riešeniu po konečnom počte krokov. Naopak iteračné metódy konvergujú k riešeniu a presnosť riešenia je závislá od počtu iterácií . Priame metódy sú všeobecne vhodnejšie pre plné matice, naopak pre riedke systémy sú vhodné iteračné metódy.
Známe sú klasické priame metódy ako Cramerovo pravidlo, použitie inverznej matice a Gaussova eliminačná metóda. Tieto však nie sú pre systémy veľkých rozmerov vhodné. Taktiež sú známe klasické iteračné algoritmy ako je Jacobiho metóda a Gauss Seidelova metóda. Tieto sú vhodné aj pre riedke matice veľkých rozmerov.
Pre priame riešenie veľkých sústav je známych niekoľko algoritmov. V tejto práci je opísaný LU rozklad a Choleského rozklad. Tieto rozklady sa v rôznych obmenených podobách používajú pre priame riešenie veľkých sústav lineárnych rovníc.
V posledných desaťročiach bolo vypracovaných niekoľko moderných iteračných algoritmov pre riešenie veľkých sústav lineárnych rovníc. V práci sa zaoberáme gradientnými metódami a multigridovými metódami. Metóda konjugovaných gradientov konverguje k riešeniu rýchlejšie ako klasické iteračné metódy a je výhodná hlavne pre symetrické kladne definitné matice. Naopak, metóda bikonjugovaných gradientov a metóda GMRES sú vhodné aj pre nesymetrické matice. Multigridové metódy patria medzi najrýchlejšie iteračné metódy. Zlepšujú konvergenciu tým, že sa daná úloha opísaná určitou sieťou vyrieši najprv pre redšiu sieť a potom sa toto riešenie použije pri hľadaní riešenia v hustejšej sieti.

=Sústavy lineárnych rovníc a matice=
V tejto časti sú opísané základné pojmy lineárnej algebry , ktoré súvisia s výpočtom
sústav lineárnych rovníc . Taktiež sú tu opísané rôzne tvary matíc, ktoré sa používajú pri riešení sústav lineárnych rovníc.
==Systémy lineárnych rovníc==
Riešenie sústav lineárnych rovníc patrí medzi najdôležitejšie časti matematiky. Množstvo praktických úloh nakoniec vedie k riešeniu takýchto sústav. Tieto sústavy môžu byť často veľmi rozsiahle. Vtedy je n veľké číslo.
Systém n - lineárnych rovníc:

<math>
\begin{matrix}
a_{11}x_1+a_{12}x_2+...+a_{1n}x_n\\
a_{21}x_1+a_{22}x_2+...+a_{2n}x_n\\
.\\
.\\
.\\
a_{n1}x_1+a_{n2}x_2+...+a_{nn}x_n
\end{matrix}
</math>(1.1)

s neznámymi x1,x2,...,xn.

Matica A(i,j) , kde i,j=1,..... n, sa nazýva maticou sústavy stĺpcový vektor b =(b1, ...., bn)^T vektor pravých strán .
Sústavu lineárnych rovníc môžeme zapísať v tvare

<math>Ax=b</math>

kde
<math>
A=
\begin{bmatrix}
a_{11} & \cdots & a_{1n} \\
\vdots & \ddots & \vdots \\
a_{n1} & \cdots & a_{nn}
\end{bmatrix},
x=
\begin{bmatrix}
x_{1}\\
\vdots\\
x_{n}
\end{bmatrix},
b=
\begin{bmatrix}
b_{1}\\
\vdots\\
b_{n}
\end{bmatrix}
</math>(1.2)

Rozlišujeme dva základné typy matíc sústav lineárnych rovníc:
;Plné:systémy, kde je väčšina prvkov nenulových
;Riedke:kde je naopak väčšina prvkov rovná nule. Túto ich vlastnosť možno využiť na riešenie prostredníctvom menšieho počtu krokov [4] [5].

==Matice==

Matica typu m[[Image:Untitled%201_html_4e44f889.png]]n je sústava mn čísiel, ktoré sú usporiadané v tvare obdĺžnikovej tabuľky. Všeobecná matica typu m[[Image:Untitled%201_html_4e44f889.png]]n je opísaná nasledovne:

A=[[Image:Untitled%201_html_m7af6f254.png]]

Prvok v i-tom riadku a j-tom stĺpci označujeme [[Image:Untitled%201_html_m49e52707.png]] (i=1, ..., m , j=1, ..., n)sú reálne prvky matice.

Matica A=[[Image:Untitled%201_html_m6a6585d2.png]]sa nazýva štvorcová ak m=n, teda ak má rovnaký počet riadkov a stĺpcov.

A=[[Image:Untitled%201_html_2dcaaa4e.png]]

Dôležitou štvorcovou je tzv. '''identická''' alebo '''jednotková matica'''. Jednotková matica má na diagonále jednotky a ostatné prvky u nulové. Označujeme ju písmenom I.

I=[[Image:Untitled%201_html_7d6b44a2.png]]

Pri násobení matíc má identická matica postavenie analogické číslu 1 pri násobení reálnych čísel. A*I=I*A=A

'''Transponovaná matica''' , je matica ktorá vznikne vymenením prvkov pôvodnej matice. Vymení sa súradnica riadku za súradnicu stĺpca. Potom transponovaná matica k matici A je :

AT<nowiki>=</nowiki>[[Image:Untitled%201_html_39d2bb89.png]]

'''Inverzná matica '''[[Image:Untitled%201_html_m7e0b28e3.png]] k štvorcovej [[Image:Untitled%201_html_696253c7.png]] matici A je taká , pre ktorú platí [[Image:Untitled%201_html_m5456b175.png]] , kde I je identická matica typu [[Image:Untitled%201_html_696253c7.png]]. K matici A existuje inverzná matica vtedy, keď je determinant matice A nenulový. Matica, ku ktorej existuje inverzná matica sa nazýva '''regulárna '''<nowiki>matica[5][6]. </nowiki>

=== Diagonálne matice ===
Diagonálna matica A je štvorcová matica typu n x n ktorá má nenulové prvky na hlavnej diagonále.

Existujú aj bidiagonálne a trojdiagonálne matice. Bidiagonálna matica je taká diagonálna matica, ktorá má ešte navyše nenulové horné (horná bidiagonálna matica) alebo dolné susedné prvky k diagonále (dolná bidiagonálna matica).

Horná bidiagonálna matica Dolná bidiagonálna matica

[[Image:Untitled%201_html_6c55de17.png]] [[Image:Untitled%201_html_m1022a49c.png]]

Ak sú nenulové horné aj dolné susedné prvky ku diagonálne, vtedy hovorí o trojdiagonálnej matici.

[[Image:Untitled%201_html_m7667af1.png]]

Na rozdiel od trojdiagonálnych systémov, ktoré majú nenulové prvky len na diagonále

plus a mínus jeden, '''skupinovo diagonálne systémy''' sú všeobecnejšie. Majú m1 ≥ 0 nenulových prvkov priamo vľavo(pod)od diagonály a m2<nowiki> ≥ 0 nenulových prvkov napravo(nad)od diagonály[6]. Diagonály nachádzajúce sa nad hlavnou diagonálou sa nazývajú superdiagonály. Subdiagonály sú naopak diagonály, ktoré sa nachádzajú pod hlavnou diagonálou. </nowiki>

=== Trojuholníkové matice ===
Trojuholníkové matice sú také matice, kde všetky prvky pod alebo nad diagonálou sú

nulové. Keď sú nulové prvky nad diagonálou hovoríme o dolnej trojuholníkovej matici, a naopak keď sú nulové prvky pod hlavnou diagonálou hovoríme o hornej trojuholníkovej matici .

Dolná trojuholníková matica Horná trojuholníková matica

[[Image:Untitled%201_html_mad4a9fb.png]] [[Image:Untitled%201_html_73ceb1e2.png]]

<nowiki>[5][6]</nowiki>

=== Blokové matice ===
Blokové matice sa používajú pre zjednodušenie počítania s maticami veľkých rozmerov.

Bloková matica je nejaká maticu A, ktorú rozdelíme na bloky [[Image:Untitled%201_html_1762b84b.png]].

Majme nasledovnú maticu A.

A = [[Image:Untitled%201_html_4ffcae58.png]]

Potom môžeme danú maticu zapísať nasledovne:

A=[[Image:Untitled%201_html_m21ac2751.png]]

kde je blok matice Aij tvorený prvkami matice A:

A11 = [[Image:Untitled%201_html_m3d3ac50a.png]] A12 = [[Image:Untitled%201_html_4a93fe51.png]]

A21 = [[Image:Untitled%201_html_m12099fb8.png]] A22 = [[Image:Untitled%201_html_757e3860.png]]

<nowiki>[3][6]</nowiki>

=== Ortogonálne matice ===
Ortogonálna matica (matica s ortonormálnymi stĺpcami) je matica so stĺpcami jednotkovej dĺžky, ktoré sú na seba kolmé. Matica typu [[Image:Untitled%201_html_696253c7.png]] je ortogonálna, ak [[Image:Untitled%201_html_12aad0e5.png]]. Podľa tejto rovnice má matica Q inverznú maticu a  platí [[Image:Untitled%201_html_m5665d8ff.png]] . Potom platí [[Image:Untitled%201_html_m34195d4f.png]]<nowiki>. Potom tieto tri vzťahy sú ekvivalentné a môžeme ich považovať za definíciu ortogonálnej matice [6].

Moderné metódy riešenia veľkých sústav lineárnych rovníc

2010-05-30T21:31:00Z

Repto:

[[Kategória:Študentské práce]]
[[Kategória:Ročníkové práce]]
[[Kategória:Matematika]]
{{Draft}}
{{Hlavička_FM
|{{PAGENAME}}|Bc. Peter Poruban|Ing. Michal Štepanovský, PhD
|2009/2010
|Ročníková práca
|Mechatronika
}}
{{Praca_uvod|1|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||||||||||}}
{{abstrakt
|Práca sa zaoberá metódami vhodnými pre riešenie veľkých sústav lineárnych rovníc. Prvá časť sa zaoberá klasickými metódami pre riešenie sústav lineárnych rovníc. V ďalšej časti sú opísané priame metódy riešenia veľkých sústav . Tretia časť sa venuje moderným iteračným metódam. V práci sa podrobne zaoberáme metódou konjugovaných gradientov a geometrickou multigridovou metódou. Pre tieto dve metódy sme vypracovali ukážkové príklady riešenia. Posledná časť sa zaoberá využitím týchto metód.
|
}}
__TOC__
'''Úvod'''

V technickej praxi je častou úlohou riešiť sústavu lineárnych rovníc Ax= b s maticou rádu n, kde n je veľké číslo. Rozmery týchto matíc môžu byť rádovo v státisícoch, ale aj väčšie. Pri takýchto sústavách lineárnych rovníc sú niektoré tradičné metódy nepoužiteľné alebo sú neefektívne a časovo náročné. Taktiež niektoré z nich môžu pri maticiach veľmi veľkých rozmerov alebo zle podmienených maticiach zlyhať.
Stretávame sa s dvomi typmi systémov lineárnych rovníc. Systém lineárnych rovníc sa nazýva plný, ak väčšina prvkov je nenulová. Naopak riedke systémy sú také, kde len relatívne málo prvkov je nenulových. Pre riešenie riedkych systémov možno využiť ich vlastnosti. Vďaka tomu možno riešiť prostredníctvom niektorých algoritmov tieto matice efektívnejšie. Veľké riedke systémy je v technickej praxi veľmi často potrebné riešiť, napr. pri riešení parciálnych diferenciálnych rovníc.
Metódy pre riešenie lineárnych rovníc delíme na priame metódy a iteračné metódy. Priame metódy vedú k riešeniu po konečnom počte krokov. Naopak iteračné metódy konvergujú k riešeniu a presnosť riešenia je závislá od počtu iterácií . Priame metódy sú všeobecne vhodnejšie pre plné matice, naopak pre riedke systémy sú vhodné iteračné metódy.
Známe sú klasické priame metódy ako Cramerovo pravidlo, použitie inverznej matice a Gaussova eliminačná metóda. Tieto však nie sú pre systémy veľkých rozmerov vhodné. Taktiež sú známe klasické iteračné algoritmy ako je Jacobiho metóda a Gauss Seidelova metóda. Tieto sú vhodné aj pre riedke matice veľkých rozmerov.
Pre priame riešenie veľkých sústav je známych niekoľko algoritmov. V tejto práci je opísaný LU rozklad a Choleského rozklad. Tieto rozklady sa v rôznych obmenených podobách používajú pre priame riešenie veľkých sústav lineárnych rovníc.
V posledných desaťročiach bolo vypracovaných niekoľko moderných iteračných algoritmov pre riešenie veľkých sústav lineárnych rovníc. V práci sa zaoberáme gradientnými metódami a multigridovými metódami. Metóda konjugovaných gradientov konverguje k riešeniu rýchlejšie ako klasické iteračné metódy a je výhodná hlavne pre symetrické kladne definitné matice. Naopak, metóda bikonjugovaných gradientov a metóda GMRES sú vhodné aj pre nesymetrické matice. Multigridové metódy patria medzi najrýchlejšie iteračné metódy. Zlepšujú konvergenciu tým, že sa daná úloha opísaná určitou sieťou vyrieši najprv pre redšiu sieť a potom sa toto riešenie použije pri hľadaní riešenia v hustejšej sieti.

=Sústavy lineárnych rovníc a matice=
V tejto časti sú opísané základné pojmy lineárnej algebry , ktoré súvisia s výpočtom
sústav lineárnych rovníc . Taktiež sú tu opísané rôzne tvary matíc, ktoré sa používajú pri riešení sústav lineárnych rovníc.
==Systémy lineárnych rovníc==
Riešenie sústav lineárnych rovníc patrí medzi najdôležitejšie časti matematiky. Množstvo praktických úloh nakoniec vedie k riešeniu takýchto sústav. Tieto sústavy môžu byť často veľmi rozsiahle. Vtedy je n veľké číslo.
Systém n - lineárnych rovníc:

<math>
\begin{matrix}
a_{11}x_1+a_{12}x_2+...+a_{1n}x_n\\
a_{21}x_1+a_{22}x_2+...+a_{2n}x_n\\
.\\
.\\
.\\
a_{n1}x_1+a_{n2}x_2+...+a_{nn}x_n
\end{matrix}
</math>(1.1)

s neznámymi x1,x2,...,xn.

Matica A(i,j) , kde i,j=1,..... n, sa nazýva maticou sústavy stĺpcový vektor b =(b1, ...., bn)^T vektor pravých strán .
Sústavu lineárnych rovníc môžeme zapísať v tvare

<math>Ax=b</math>

kde
<math>
A=
\begin{bmatrix}
a_{11} & \cdots & a_{1n} \\
\vdots & \ddots & \vdots \\
a_{n1} & \cdots & a_{nn}
\end{bmatrix},
x=
\begin{bmatrix}
x_{1}\\
\vdots\\
x_{n}
\end{bmatrix},
b=
\begin{bmatrix}
b_{1}\\
\vdots\\
b_{n}
\end{bmatrix}
</math>(1.2)

Rozlišujeme dva základné typy matíc sústav lineárnych rovníc:
;Plné:systémy, kde je väčšina prvkov nenulových
;Riedke:kde je naopak väčšina prvkov rovná nule. Túto ich vlastnosť možno využiť na riešenie prostredníctvom menšieho počtu krokov [4] [5].

==Matice==

Matica typu m[[Image:Untitled%201_html_4e44f889.png]]n je sústava mn čísiel, ktoré sú usporiadané v tvare obdĺžnikovej tabuľky. Všeobecná matica typu m[[Image:Untitled%201_html_4e44f889.png]]n je opísaná nasledovne:

A=[[Image:Untitled%201_html_m7af6f254.png]]

Prvok v i-tom riadku a j-tom stĺpci označujeme [[Image:Untitled%201_html_m49e52707.png]] (i=1, ..., m , j=1, ..., n)sú reálne prvky matice.

Matica A=[[Image:Untitled%201_html_m6a6585d2.png]]sa nazýva štvorcová ak m=n, teda ak má rovnaký počet riadkov a stĺpcov.

A=[[Image:Untitled%201_html_2dcaaa4e.png]]

Dôležitou štvorcovou je tzv. '''identická''' alebo '''jednotková matica'''. Jednotková matica má na diagonále jednotky a ostatné prvky u nulové. Označujeme ju písmenom I.

I=[[Image:Untitled%201_html_7d6b44a2.png]]

Pri násobení matíc má identická matica postavenie analogické číslu 1 pri násobení reálnych čísel. A*I=I*A=A

'''Transponovaná matica''' , je matica ktorá vznikne vymenením prvkov pôvodnej matice. Vymení sa súradnica riadku za súradnicu stĺpca. Potom transponovaná matica k matici A je :

AT<nowiki>=</nowiki>[[Image:Untitled%201_html_39d2bb89.png]]

'''Inverzná matica '''[[Image:Untitled%201_html_m7e0b28e3.png]] k štvorcovej [[Image:Untitled%201_html_696253c7.png]] matici A je taká , pre ktorú platí [[Image:Untitled%201_html_m5456b175.png]] , kde I je identická matica typu [[Image:Untitled%201_html_696253c7.png]]. K matici A existuje inverzná matica vtedy, keď je determinant matice A nenulový. Matica, ku ktorej existuje inverzná matica sa nazýva '''regulárna '''<nowiki>matica[5][6]. </nowiki>

=== Diagonálne matice ===
Diagonálna matica A je štvorcová matica typu n x n ktorá má nenulové prvky na hlavnej diagonále.

Existujú aj bidiagonálne a trojdiagonálne matice. Bidiagonálna matica je taká diagonálna matica, ktorá má ešte navyše nenulové horné (horná bidiagonálna matica) alebo dolné susedné prvky k diagonále (dolná bidiagonálna matica).

Horná bidiagonálna matica Dolná bidiagonálna matica

[[Image:Untitled%201_html_6c55de17.png]] [[Image:Untitled%201_html_m1022a49c.png]]

Ak sú nenulové horné aj dolné susedné prvky ku diagonálne, vtedy hovorí o trojdiagonálnej matici.

[[Image:Untitled%201_html_m7667af1.png]]

Na rozdiel od trojdiagonálnych systémov, ktoré majú nenulové prvky len na diagonále

plus a mínus jeden, '''skupinovo diagonálne systémy''' sú všeobecnejšie. Majú m1 ≥ 0 nenulových prvkov priamo vľavo(pod)od diagonály a m2<nowiki> ≥ 0 nenulových prvkov napravo(nad)od diagonály[6]. Diagonály nachádzajúce sa nad hlavnou diagonálou sa nazývajú superdiagonály. Subdiagonály sú naopak diagonály, ktoré sa nachádzajú pod hlavnou diagonálou. </nowiki>

=== Trojuholníkové matice ===
Trojuholníkové matice sú také matice, kde všetky prvky pod alebo nad diagonálou sú

nulové. Keď sú nulové prvky nad diagonálou hovoríme o dolnej trojuholníkovej matici, a naopak keď sú nulové prvky pod hlavnou diagonálou hovoríme o hornej trojuholníkovej matici .

Dolná trojuholníková matica Horná trojuholníková matica

[[Image:Untitled%201_html_mad4a9fb.png]] [[Image:Untitled%201_html_73ceb1e2.png]]

<nowiki>[5][6]</nowiki>

=== Blokové matice ===
Blokové matice sa používajú pre zjednodušenie počítania s maticami veľkých rozmerov.

Bloková matica je nejaká maticu A, ktorú rozdelíme na bloky [[Image:Untitled%201_html_1762b84b.png]].

Majme nasledovnú maticu A.

<center>A = [[Image:Untitled%201_html_4ffcae58.png]]</center>

Potom môžeme danú maticu zapísať nasledovne:

<center>A=[[Image:Untitled%201_html_m21ac2751.png]]</center>

kde je blok matice Aij tvorený prvkami matice A:

<center>A11 = [[Image:Untitled%201_html_m3d3ac50a.png]] A12 = [[Image:Untitled%201_html_4a93fe51.png]]</center>

A21 = [[Image:Untitled%201_html_m12099fb8.png]] A22 = [[Image:Untitled%201_html_757e3860.png]]

<nowiki>[3][6]</nowiki>

=== Ortogonálne matice ===
Ortogonálna matica (matica s ortonormálnymi stĺpcami) je matica so stĺpcami jednotkovej dĺžky, ktoré sú na seba kolmé. Matica typu [[Image:Untitled%201_html_696253c7.png]] je ortogonálna, ak [[Image:Untitled%201_html_12aad0e5.png]]. Podľa tejto rovnice má matica Q inverznú maticu a  platí [[Image:Untitled%201_html_m5665d8ff.png]] . Potom platí [[Image:Untitled%201_html_m34195d4f.png]]<nowiki>. Potom tieto tri vzťahy sú ekvivalentné a môžeme ich považovať za definíciu ortogonálnej matice [6].

Ročníkové práce

2010-05-30T21:29:11Z

Repto:

{{Ako_pisat_wikiPracu|XvovaX}}

<div id="mainpage_topbox">
<div id="mainpage_pagetitle">Ročníkové práce 2009/2010</div>
{| class="wikitable sortable" border=1 cellpadding=5 cellspacing=0 style="width:100%"
|+ Mechatronika
|-
!Autor
!Názov práce
!style="width:150px"|Stav práce
!style="width:90px"|Zadanie
|-
|Martin Starosta, Bc.
|[[Open Project Management ako Java Enterprise aplikácia]]
|{{stav_prace|50}}
|[[Open Project Management ako Java Enterprise aplikácia (Zadanie)|Zadanie RP]]
|-
|Ivana Zuzinová, Bc.
|[[Framework "Ruby on Rails" a web 2.0]]
|{{stav_prace|50}}
|[[Framework "Ruby on Rails" a web 2.0 (Zadanie)|Zadanie RP]]
|-
|Martin Vaško, Bc.
|[[Platforma JavaFX pre moderné webové aplikácie]]
|{{stav_prace|70}}
|[[Platforma JavaFX pre moderné webové aplikácie (Zadanie)|Zadanie RP]]
|-
|Ján Danko, Bc.
|[[Návrh a realizácia robota na báze lego mindstorm s využitím vyšších programovacích jazykov]]
|{{stav_prace|100}}
|[[Návrh a realizácia robota na báze lego mindstorm s využitím vyšších programovacích jazykov (Zadanie)|Zadanie RP]]
|-
|Ján Kosterec, Bc.
|[[Zabezpečovacie zariadenie automobilu na CAN zbernici]]
|{{stav_prace|0}}
|[[Zabezpečovacie zariadenie automobilu na CAN zbernici (Zadanie)|Zadanie RP]]
|-
|Peter Celler, Bc.
|
|
|-
|Peter Poruban, Bc.
|[[Moderné metódy riešenia veľkých sústav lineárnych rovníc]]
|{{stav_prace|90}}
|[[Moderné metódy riešenia veľkých sústav lineárnych rovníc (Zadanie)|Zadanie RP]]
|-
|Pavel Hromada, Bc.
|[[Analyzátor nameraných dát z meracích prístrojov v priemysle]]
|{{stav_prace|50}}
|[[Analyzátor nameraných dát z meracích prístrojov v priemysle (Zadanie)|Zadanie RP]]
|}
</div>

[[Kategória:Študentské práce]]

Moderné metódy riešenia veľkých sústav rovníc

2010-05-30T21:27:33Z

Repto: 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…“

Softvérové balíky pre riešenie veľkých lineárnych systémov

2010-05-30T21:16:40Z

Repto:

[[Kategória:Študentské práce]]
[[Kategória:Ročníkové práce]]
[[Kategória:Matematika]]
{{Praca_uvod|5|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__
= =

'''Softvérové balíky pre riešenie veľkých lineárnych systémov'''

Riešenie sústav lineárnych rovníc je základom riešenia mnohých problémov vo vedeckých výpočtoch. V mnohých prípadoch sú riešené sústavy veľmi veľké a matica sústavy je riedka. V mnohých aplikáciách je matica symetrická, ako je to napríklad pri použití metódy konečných prvkov. Za posledné desaťročia bolo navrhnutých množstvo nových algoritmov a taktiež programových balíkov pre riešenie symetrických riedkych matíc , ktoré implementujú tieto algoritmy. V tejto časti sú uvedené niektoré balíky obsahujúce priame riešiče riedkych lineárnych systémov.

Priame riešiče riedkych systémov pracujú v niekoľkých fázach. Presné rozdelenie do jednotlivých fáz závisí od použitého algoritmu a softvéru, všeobecné rozdelenie je nasledovné:

# Usporiadanie na základe štruktúry.
# Analýza štruktúry matice na základe, ktorej sa zavedú potrebné  dátové štruktúry pre efektívny rozklad matice
# Rozklad matice
# Fáza riešenia, kde sa vykoná eliminácia a potom následne spätná substitúcia.

Fáza rozkladu matice je obvykle časovo najnáročnejšia. Naopak fáza riešenia je všeobecne omnoho rýchlejšia.

Algoritmy rozkladu matíc

Rozklad môže vykonaný rôznymi spôsobmi, čo závisí od prístupu k jednotlivým prvkom systému. Existujú tri základné typy algoritmov : left-looking, right-looking a multifrontal.

Pri right-looking prístupe sa v každom kroku vypočítajú riadky a stĺpce a a tieto zmeny sa hneď aplikujú. Pri left-looking algoritme sa vypočítané zmeny neaplikujú hneď. Predtým ako je eliminovaný stĺpec ''k'' , všetky zmeny z predchádzajúcich stĺpcov ''k'' matice L sa použijú spolu so stĺpcom ''k'' matice A. Pri multifrontálnom algoritme sa zmeny akumulujú, a potom sa aplikujú prostredníctvom tzv. eliminačného stromu.

Niektoré knižnice pre priame riešenie riedkych systémov

'''PARDISO '''umožňuje paralelné a sériové riešenie nesymetrických a symetrických riedkych systémov na multiprocesorovom systéme so zdieľanou pamäťou .Využíva sa tu left-looking a right-looking verzia Choleského rozkladu.

'''SPOOLES''' je knižnica pre riešenie riedkych reálnych a komplexných sústav rovníc . Je dostupná v paralelnej aj sériovej verzii. Používa sa tu verzia Gaussovej eliminačnej metódy s Croutovou redukciou .

'''TAUCS''' je navrhnutá pre symetrické kladne definitné systémy . Používa sa tu left-looking a multifrontálne verzie LU rozkladu a Choleského rozkladu.

'''UMFPACK '''<nowiki>je knižnica pre riešenie nesymetrických systémov. Využíva nesymetrický multifrontálny LU rozklad [14]. </nowiki>

== Simulačný softvér ==
Existuje viacero softvérov, ktoré používajú metódu konečných prvkov. Pomocou tejto metódy sa transformuje systém parciálnych diferenciálnych rovníc, ktoré popisujú danú úlohu na systém lineárnych rovníc . Táto metóda sa používa v mnohých odvetviach : napr. pri návrhu strojov, rôznych súčiastok, atď.

Pri metóde konečných prvkov sa väčšinou dostávame k veľkému systému lineárnych rovníc . Pre jeho riešenie simulačné softvéry používajú niektoré z uvedených moderných metód . Je známych viacero softvérov ktoré pracujú s metódou konečných prvkov napr. ANSYS, COMSOL, FEMM, ELMER Multiphysics a mnoho ďalších. Pre riešenie vzniknutých veľkých sústav lineárnych rovníc používajú rôzne moderné metódy riešenia. V tab. 1 sú uvedené metódy používané v niektorých simulačných programoch.

'''Tab. č. 1 Metódy používané v simulačných softvéroch '''

{| style="border-spacing:0;"
| style="border-top:0.0361in double #000000;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:none;padding:0.0729in;"| <center>'''FEMM'''</center>
| style="border-top:0.0361in double #000000;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:none;padding:0.0729in;"| <center>'''ANSYS'''</center>
| style="border-top:0.0361in double #000000;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:none;padding:0.0729in;"| <center>'''COMSOL'''</center>
| style="border:0.0361in double #000000;padding:0.0729in;"| <center>'''Elmer Multiphysics'''</center>

|-
| style="border-top:none;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:none;padding:0.0729in;"| <center>CG</center>
| style="border-top:none;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:none;padding:0.0729in;"| <center>iteračné gradientné metódy </center>
| style="border-top:none;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:none;padding:0.0729in;"| <center>knižnica UMFPACK</center>
| style="border-top:none;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:0.0361in double #000000;padding:0.0729in;"| <center>knižnica UMFPACK</center>

|-
| style="border-top:none;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:none;padding:0.0729in;"| <center>BCG</center>
| style="border-top:none;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:none;padding:0.0729in;"| <center>AMG</center>
| style="border-top:none;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:none;padding:0.0729in;"| <center>GMRES</center>
| style="border-top:none;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:0.0361in double #000000;padding:0.0729in;"| <center>AMG a GMG</center>

|-
| style="border-top:none;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:none;padding:0.0729in;"| <center> </center>
| style="border-top:none;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:none;padding:0.0729in;"| <center> </center>
| style="border-top:none;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:none;padding:0.0729in;"| <center> </center>
| style="border-top:none;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:0.0361in double #000000;padding:0.0729in;"| <center>iteračné gradientné metódy </center>

|}
'''Ukážkový príklad analýzy vo FEMM'''

FEMM je softvérový balík pre riešenie nízkofrekvenčných elektromagnetických úloh v 2D. Pre <nowiki>riešenie vzniknutého systému lineárnych rovníc podľa typu riešeného problému používa buď metódu konjugovaných gradientov s prepodmienením alebo metódu bikonjugovaných gradientov [15].</nowiki>

Na (obr.4) je 2D model asynchrónneho motora, pre ktorý hľadáme rozloženie potenciálu.

Obr. 4 Model asynchrónneho motora vo FEMM

Daná úloha má [[Image:Untitled%201_html_49f63057.png]] stupňov voľnosti, teda sa rieši maticová rovnica s maticou systému o rozmeroch [[Image:Untitled%201_html_m3ca83b85.png]].

[[Image:Untitled%201_html_d245593.png]]Obr. 5 Rozloženie poľa asynchrónneho motora

Na (obr. 5) je vyriešené rozloženie potenciálu pre daný asynchrónny motor. Riešenie danej úlohy metódou bikonjugovaných gradientov prostredníctvom softvéru FEMM trvalo 3 minúty. Riešenie bolo realizované na počítači s procesorom AMD Turion X2 Dual-Core 2.20 GHz a s operačnou pamäťou 4 GB.

=Záver=
Cieľom mojej práce bolo oboznámiť sa s riešením sústav veľkých lineárnych rovníc a opísať a porovnať niektoré z existujúcich algoritmov. V práci som sa zameral na opis niektorých existujúcich algoritmov pre riešenie sústav lineárnych rovníc.
V práci sú opísané niektoré klasické algoritmy pre riešenie sústav lineárnych rovníc. Cramerovo pravidlo a riešenie pomocou inverznej matice sú vhodné len pre veľmi malé sústavy. Gaussova eliminačná metóda taktiež pre veľké matice nie je príliš vhodná, pretože je potrebné veľké množstvo operácií pre riešenie veľkých sústav. Takisto pri eliminácii môžu vzniknúť chyby. Preto sa skôr používajú jej modifikácie. Klasické iteračné metódy: Jacobiho a Gauss – Seidelova sú vhodné pre väčšie matice a riedke matice. Keďže množstvo nulových prvkov v riedkych maticiach znižuje počet potrebných operácií a výpočtovú náročnosť, sú tieto metódy vhodné aj pre veľké riedke sústavy lineárnych rovníc.
Ďalšia časť sa zaoberá priamymi metódami pre riešenie veľkých sústav. Sú tu opísané dva algoritmy rozkladu pre zjednodušenie veľkých matíc: LU rozklad a Choleského rozklad. Je viacero metód, ako možno rozložiť maticu do podoby niektorého z rozkladov. Na týchto rozkladoch sú založené niektoré moderné priame metódy. V tejto práci sú opísané len základné algoritmy, ako možno tieto rozklady uskutočniť.
Hlavná časť práce je venovaná moderným iteračným metódam riešenia veľkých sústav. Pozornosť sa tu venuje tzv. gradientným metódam a multigridovým metódam. Pri gradientných metódach sa zostrojí postupnosť vektorov , ktorá konverguje k riešeniu sústavy. Metóda konjugovaných gradientov je vhodná len pre symetrické kladne definitné matice, naopak metóda bikonjugovaných gradientov a GMRES sa používajú pre nesymetrické systémy. Je tu vypracovaný aj ukážkový príklad riešenia sústavy malých rozmerov prostredníctvom metódy konjugovaných gradientov. Ďalej sa táto časť zaoberá multigridovými metódami. Geometrické multigridové metódy vyžadujú informáciu o hierarchii daného systému, naopak algebraické multigridové metódy nepotrebujú túto hierarchiu poznať. Algebraické sú vhodnejšie pre úlohy s neregulárnou štruktúrou. Pre objasnenie metódy geometrického multigridu sme vypracovali ukážkový príklad riešenia jednoduchej úlohy.
Posledná časť práce sa zaoberá aplikáciou a použitím daných metód. Sú tu opísané niektoré knižnice ktoré v sebe implementujú niektoré z uvedených metód. Taktiež sú tu opísané simulačné programy, ktoré využívajú niektoré z týchto metód a knižníc.

=Použitá literatúra=
#Parallel Algorithms for Matrix Computations. Philadelphia : Society for Industrial and Applied Mathematics, 1990. 195 s. ISBN 0898712602
#TIMOTHY A. Davis: Direct Methods for Sparse Linear Systems : Fundamentals of Algorithms. Society for Industrial and Applied Mathematic, 2006. 217 s. ISBN 0898716136.
#GOLUB G. H. , Van Loan Ch. F., Matrix computations, The John Hopkins University Press, 1996. 694 s. ISBN 0801854148
#FAJMON, Bretislav , RUŽICKOVÁ, Irena. Matematika 3. Brno : Vysoké Učení Technické v Brne, 2005. 252 s. Dostupný z WWW: <http://www.umat.feec.vutbr.cz/~fajmon/inm/matematika3.pdf>.
#Skriptá, Bratislava: STU, Dostupný z WWW:<http://www-kmadg.svf.stuba.sk/skripta/index.html>.
#DOBÁK, Radoslav. Využitie blokových matíc pri riešení úloh lineárnej algebry . Bratislava, 2009. 51 s. Univerzita Komenského v Bratislave. Dostupné z WWW: <http://www.iam.fmph.uniba.sk/studium/efm/diplomovky/2009/dobak/diplomovka.pdf >
#Prednáška 4 : Numerické metódy matematiky I. Dostupný z WWW: <http://fyzikazeme.sk/mainpage/stud_mat/menm/prednaska4.pdf>
#Brezová Martina. Choleského metóda. 2006. Bratislava. Dostupný z WWW:< http://www.mtakac.com/aap/ref/brezova.pdf>
#Prednáška 5 : Numerické metódy matematiky I. Dostupný z WWW: <http://fyzikazeme.sk/mainpage/stud_mat/menm/prednaska5.pdf>
#Wikipedia [online]. 2007, 19.4.2010 [cit. 2010-05-2]. Conjugate gradient method. Dostupné z WWW: <http://en.wikipedia.org/wiki/Conjugate_gradient_method>.
#SAAD, Y. Iterative Methods for Sparse Linear Systems. Manchester , 2000. 447 s. Dostupné z WWW: <http://www.stanford.edu/class/cme324/saad.pdf>.
#KALTENBACHER, Manfred. Numerical Simulation of Mechatronic Sensors and Actuators. 2nd Edition. Berlin : Springer, 2007. 428 s. ISBN 978-3-540-71359-3.
#HULSEMANN, Frank. Parallel Geometric Multigrid ,2008. 44 s. Dostupné z WWW: <http://www10.informatik.unierlangen.de/Publications/Papers/2005/PGM_LNCSE51.pdf>.
#GOULD, N.; HU, Y.; SCOTT, J. A numerical evaluation of sparse direct solvers [online]. 2005 [cit. 2010-05-09]. Dostupné z WWW: <ftp://ftp.numerical.rl.ac.uk/pub/reports/ghsRAL200505.pdf>.
#MEEKER, David. Finite Element Method Magnetics User’s Manual [online]., 2007, 5.2.2009 [cit. 2010-05-09]. Dostupné z WWW: <http://www.femm.info/Archives/doc/manual42.pdf>.
#ŠTEPANOVSKÝ, Michal. Metóda konečných prvkov : Sprievodný materiál k semináru IT Power Knowledge
#BRIGGS, William. A Multigrid Tutorial.. 119 s. Dostupné z WWW: <http://www.cfm.brown.edu/people/gk/APMA2821F/mgtut_part1.pdf>.

Softvérové balíky pre riešenie veľkých lineárnych systémov

2010-05-30T21:13:54Z

Repto: Vytvorená stránka „ '''Softvérové balíky pre riešenie veľkých lineárnych systémov''' Riešenie sústav lineárnych rovníc je základom riešenia mnohých problémov vo vedecký…“

'''Softvérové balíky pre riešenie veľkých lineárnych systémov'''

Riešenie sústav lineárnych rovníc je základom riešenia mnohých problémov vo vedeckých výpočtoch. V mnohých prípadoch sú riešené sústavy veľmi veľké a matica sústavy je riedka. V mnohých aplikáciách je matica symetrická, ako je to napríklad pri použití metódy konečných prvkov. Za posledné desaťročia bolo navrhnutých množstvo nových algoritmov a taktiež programových balíkov pre riešenie symetrických riedkych matíc , ktoré implementujú tieto algoritmy. V tejto časti sú uvedené niektoré balíky obsahujúce priame riešiče riedkych lineárnych systémov.

Priame riešiče riedkych systémov pracujú v niekoľkých fázach. Presné rozdelenie do jednotlivých fáz závisí od použitého algoritmu a softvéru, všeobecné rozdelenie je nasledovné:

# Usporiadanie na základe štruktúry.
# Analýza štruktúry matice na základe, ktorej sa zavedú potrebné  dátové štruktúry pre efektívny rozklad matice
# Rozklad matice
# Fáza riešenia, kde sa vykoná eliminácia a potom následne spätná substitúcia.

Fáza rozkladu matice je obvykle časovo najnáročnejšia. Naopak fáza riešenia je všeobecne omnoho rýchlejšia.

Algoritmy rozkladu matíc

Rozklad môže vykonaný rôznymi spôsobmi, čo závisí od prístupu k jednotlivým prvkom systému. Existujú tri základné typy algoritmov : left-looking, right-looking a multifrontal.

Pri right-looking prístupe sa v každom kroku vypočítajú riadky a stĺpce a a tieto zmeny sa hneď aplikujú. Pri left-looking algoritme sa vypočítané zmeny neaplikujú hneď. Predtým ako je eliminovaný stĺpec ''k'' , všetky zmeny z predchádzajúcich stĺpcov ''k'' matice L sa použijú spolu so stĺpcom ''k'' matice A. Pri multifrontálnom algoritme sa zmeny akumulujú, a potom sa aplikujú prostredníctvom tzv. eliminačného stromu.

Niektoré knižnice pre priame riešenie riedkych systémov

'''PARDISO '''umožňuje paralelné a sériové riešenie nesymetrických a symetrických riedkych systémov na multiprocesorovom systéme so zdieľanou pamäťou .Využíva sa tu left-looking a right-looking verzia Choleského rozkladu.

'''SPOOLES''' je knižnica pre riešenie riedkych reálnych a komplexných sústav rovníc . Je dostupná v paralelnej aj sériovej verzii. Používa sa tu verzia Gaussovej eliminačnej metódy s Croutovou redukciou .

'''TAUCS''' je navrhnutá pre symetrické kladne definitné systémy . Používa sa tu left-looking a multifrontálne verzie LU rozkladu a Choleského rozkladu.

'''UMFPACK '''<nowiki>je knižnica pre riešenie nesymetrických systémov. Využíva nesymetrický multifrontálny LU rozklad [14]. </nowiki>

== Simulačný softvér ==
Existuje viacero softvérov, ktoré používajú metódu konečných prvkov. Pomocou tejto metódy sa transformuje systém parciálnych diferenciálnych rovníc, ktoré popisujú danú úlohu na systém lineárnych rovníc . Táto metóda sa používa v mnohých odvetviach : napr. pri návrhu strojov, rôznych súčiastok, atď.

Pri metóde konečných prvkov sa väčšinou dostávame k veľkému systému lineárnych rovníc . Pre jeho riešenie simulačné softvéry používajú niektoré z uvedených moderných metód . Je známych viacero softvérov ktoré pracujú s metódou konečných prvkov napr. ANSYS, COMSOL, FEMM, ELMER Multiphysics a mnoho ďalších. Pre riešenie vzniknutých veľkých sústav lineárnych rovníc používajú rôzne moderné metódy riešenia. V tab. 1 sú uvedené metódy používané v niektorých simulačných programoch.

'''Tab. č. 1 Metódy používané v simulačných softvéroch '''

{| style="border-spacing:0;"
| style="border-top:0.0361in double #000000;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:none;padding:0.0729in;"| <center>'''FEMM'''</center>
| style="border-top:0.0361in double #000000;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:none;padding:0.0729in;"| <center>'''ANSYS'''</center>
| style="border-top:0.0361in double #000000;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:none;padding:0.0729in;"| <center>'''COMSOL'''</center>
| style="border:0.0361in double #000000;padding:0.0729in;"| <center>'''Elmer Multiphysics'''</center>

|-
| style="border-top:none;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:none;padding:0.0729in;"| <center>CG</center>
| style="border-top:none;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:none;padding:0.0729in;"| <center>iteračné gradientné metódy </center>
| style="border-top:none;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:none;padding:0.0729in;"| <center>knižnica UMFPACK</center>
| style="border-top:none;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:0.0361in double #000000;padding:0.0729in;"| <center>knižnica UMFPACK</center>

|-
| style="border-top:none;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:none;padding:0.0729in;"| <center>BCG</center>
| style="border-top:none;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:none;padding:0.0729in;"| <center>AMG</center>
| style="border-top:none;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:none;padding:0.0729in;"| <center>GMRES</center>
| style="border-top:none;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:0.0361in double #000000;padding:0.0729in;"| <center>AMG a GMG</center>

|-
| style="border-top:none;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:none;padding:0.0729in;"| <center> </center>
| style="border-top:none;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:none;padding:0.0729in;"| <center> </center>
| style="border-top:none;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:none;padding:0.0729in;"| <center> </center>
| style="border-top:none;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:0.0361in double #000000;padding:0.0729in;"| <center>iteračné gradientné metódy </center>

|}
'''Ukážkový príklad analýzy vo FEMM'''

FEMM je softvérový balík pre riešenie nízkofrekvenčných elektromagnetických úloh v 2D. Pre <nowiki>riešenie vzniknutého systému lineárnych rovníc podľa typu riešeného problému používa buď metódu konjugovaných gradientov s prepodmienením alebo metódu bikonjugovaných gradientov [15].</nowiki>

Na (obr.4) je 2D model asynchrónneho motora, pre ktorý hľadáme rozloženie potenciálu.

Obr. 4 Model asynchrónneho motora vo FEMM

Daná úloha má [[Image:Untitled%201_html_49f63057.png]] stupňov voľnosti, teda sa rieši maticová rovnica s maticou systému o rozmeroch [[Image:Untitled%201_html_m3ca83b85.png]].

[[Image:Untitled%201_html_d245593.png]]Obr. 5 Rozloženie poľa asynchrónneho motora

Na (obr. 5) je vyriešené rozloženie potenciálu pre daný asynchrónny motor. Riešenie danej úlohy metódou bikonjugovaných gradientov prostredníctvom softvéru FEMM trvalo 3 minúty. Riešenie bolo realizované na počítači s procesorom AMD Turion X2 Dual-Core 2.20 GHz a s operačnou pamäťou 4 GB.

Súbor:Untitled 1 html d245593.png

2010-05-30T21:13:37Z

Repto:

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

2010-05-30T21:10:05Z

Repto:

[[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 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:

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

kde l11<nowiki>=1 je skalár a všetky tri matice sú štvorcové matice. Sú možné aj iné varianty ako zvoliť l</nowiki>11. V tomto prípade dostaneme dolnú trojuholníkovú maticu a š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 so základným argumentom (3.4) a induktívny predpoklad z rovnice (3.5) [3].</nowiki>[[Image:Untitled%201_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 [[Image:Untitled%201_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 [[Image:Untitled%201_html_m7ba66b87.png]]n, je permutačná matica ktorá vymieňa dva riadky A tak, že

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

a [[Image:Untitled%201_html_c0f008f.png]]. Ak rovnica (3.1) a 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 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 ú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 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 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'' je [[Image:Untitled%201_html_m1f50f11c.png]]symetrická 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 [[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 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 a hľadaná matica L sú blokové matice [[Image:Untitled%201_html_696253c7.png]] so štvorcovými diagonálnymi blokmi . Vyjadrením (i,j) v 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, 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 porovnaní s LU rozkladom o 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 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 : [[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 rozmeroch n-1. [[Image:Untitled%201_html_m1e0dd299.png]] sú stĺpcové vektory o dĺžke n-1. [[Image:Untitled%201_html_m6ac242f3.png]] sú skaláry. Toto vedie k 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 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 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<nowiki>= </nowiki> xj / ljj

'''for''' i > j, lij[[Image:Untitled%201_html_m6647c5ea.png]] '''do'''

xj<nowiki>= </nowiki>xj – lij xj<nowiki>;</nowiki>

'''end for'''

'''end for'''

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

x=b;

x1 <nowiki>= </nowiki>x1 / l11 <nowiki>;</nowiki>

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

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

>xj<nowiki>= </nowiki> xj – lij xj<nowiki>;</nowiki>

'''end for'''

xi<nowiki>= x</nowiki>i / lii<nowiki>;</nowiki>

'''end for'''

Pre riešenie Ux = b , kde U 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 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 z prvej (3.19) dostávame [[Image:Untitled%201_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].

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

2010-05-30T21:05:34Z

Repto:

[[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 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:

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

kde l11<nowiki>=1 je skalár a všetky tri matice sú štvorcové matice. Sú možné aj iné varianty ako zvoliť l</nowiki>11. V tomto prípade dostaneme dolnú trojuholníkovú maticu a š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 so základným argumentom (3.4) a induktívny predpoklad z rovnice (3.5) [3].</nowiki>[[Image:Untitled%201_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 [[Image:Untitled%201_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 [[Image:Untitled%201_html_m7ba66b87.png]]n, je permutačná matica ktorá vymieňa dva riadky A tak, že

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

a [[Image:Untitled%201_html_c0f008f.png]]. Ak rovnica (3.1) a 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 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 ú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 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 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'' je [[Image:Untitled%201_html_m1f50f11c.png]]symetrická 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 [[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 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 a hľadaná matica L sú blokové matice [[Image:Untitled%201_html_696253c7.png]] so štvorcovými diagonálnymi blokmi . Vyjadrením (i,j) v 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, 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 porovnaní s LU rozkladom o 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 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 : [[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 rozmeroch n-1. [[Image:Untitled%201_html_m1e0dd299.png]] sú stĺpcové vektory o dĺžke n-1. [[Image:Untitled%201_html_m6ac242f3.png]] sú skaláry. Toto vedie k 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 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 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<nowiki>= </nowiki> xj / ljj

'''for''' i > j, lij[[Image:Untitled%201_html_m6647c5ea.png]] '''do'''

xj<nowiki>= </nowiki>xj – lij xj<nowiki>;</nowiki>

'''end for'''

'''end for'''

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

x=b;

x1 <nowiki>= </nowiki>x1 / l11 <nowiki>;</nowiki>

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

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

xj<nowiki>= </nowiki> xj – lij xj<nowiki>;</nowiki>

'''end for'''

xi<nowiki>= x</nowiki>i / lii<nowiki>;</nowiki>

'''end for'''

Pre riešenie Ux = b , kde U 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 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 z prvej (3.19) dostávame [[Image:Untitled%201_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].

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

2010-05-30T20:53:28Z

Repto:

[[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 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:

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

kde l11<nowiki>=1 je skalár a všetky tri matice sú štvorcové matice. Sú možné aj iné varianty ako zvoliť l</nowiki>11. V tomto prípade dostaneme dolnú trojuholníkovú maticu a š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 so základným argumentom (3.4) a induktívny predpoklad z rovnice (3.5) [3].</nowiki>[[Image:Untitled%201_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 [[Image:Untitled%201_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 [[Image:Untitled%201_html_m7ba66b87.png]]n, je permutačná matica ktorá vymieňa dva riadky A tak, že

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

a [[Image:Untitled%201_html_c0f008f.png]]. Ak rovnica (3.1) a 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 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 ú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 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 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'' je [[Image:Untitled%201_html_m1f50f11c.png]]symetrická 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 [[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 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 a hľadaná matica L sú blokové matice [[Image:Untitled%201_html_696253c7.png]] so štvorcovými diagonálnymi blokmi . Vyjadrením (i,j) v 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, 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 porovnaní s LU rozkladom o 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 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 : [[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 rozmeroch n-1. [[Image:Untitled%201_html_m1e0dd299.png]] sú stĺpcové vektory o dĺžke n-1. [[Image:Untitled%201_html_m6ac242f3.png]] sú skaláry. Toto vedie k 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 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 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<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 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 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 z prvej (3.19) dostávame [[Image:Untitled%201_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].

Súbor:Untitled 1 html bc4ade2.png

2010-05-30T20:36:04Z

Repto:

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

2010-05-30T20:33:42Z

Repto:

[[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__
= =
</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:

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

kde l11<nowiki>=1 je skalár a všetky tri matice sú štvorcové matice. Sú možné aj iné varianty ako zvoliť l</nowiki>11. V tomto prípade dostaneme dolnú trojuholníkovú maticu a š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 so základným argumentom (3.4) a induktívny predpoklad z rovnice (3.5) [3].</nowiki>[[Image:Untitled%201_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 [[Image:Untitled%201_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 [[Image:Untitled%201_html_m7ba66b87.png]]n, je permutačná matica ktorá vymieňa dva riadky A tak, že

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

a [[Image:Untitled%201_html_c0f008f.png]]. Ak rovnica (3.1) a 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 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 ú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 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 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'' je [[Image:Untitled%201_html_m1f50f11c.png]]symetrická 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 [[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 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 a hľadaná matica L sú blokové matice [[Image:Untitled%201_html_696253c7.png]] so štvorcovými diagonálnymi blokmi . Vyjadrením (i,j) v 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, 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 porovnaní s LU rozkladom o 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 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 : [[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 rozmeroch n-1. [[Image:Untitled%201_html_m1e0dd299.png]] sú stĺpcové vektory o dĺžke n-1. [[Image:Untitled%201_html_m6ac242f3.png]] sú skaláry. Toto vedie k 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 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 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<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 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 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 z prvej (3.19) dostávame [[Image:Untitled%201_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].

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

2010-05-30T20:27:33Z

Repto:

[[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__
= =
</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:

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

kde l11<nowiki>=1 je skalár a všetky tri matice sú štvorcové matice. Sú možné aj iné varianty ako zvoliť l</nowiki>11. V tomto prípade dostaneme dolnú trojuholníkovú maticu a š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 so základným argumentom (3.4) a induktívny predpoklad z rovnice (3.5) [3].</nowiki>[[Image:Untitled%201_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 [[Image:Untitled%201_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 [[Image:Untitled%201_html_m7ba66b87.png]]n, je permutačná matica ktorá vymieňa dva riadky A tak, že

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

a [[Image:Untitled%201_html_c0f008f.png]]. Ak rovnica (3.1) a 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 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 ú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 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 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'' je [[Image:Untitled%201_html_m1f50f11c.png]]symetrická 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 [[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 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 a hľadaná matica L sú blokové matice [[Image:Untitled%201_html_696253c7.png]] so štvorcovými diagonálnymi blokmi . Vyjadrením (i,j) v 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, 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 porovnaní s LU rozkladom o 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 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 : [[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 rozmeroch n-1. [[Image:Untitled%201_html_m1e0dd299.png]] sú stĺpcové vektory o dĺžke n-1. [[Image:Untitled%201_html_m6ac242f3.png]] sú skaláry. Toto vedie k 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 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 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<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 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 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 z prvej (3.19) dostávame [[Image:Untitled%201_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].

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

2010-05-30T20:25:16Z

Repto: 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…“

Klasické metódy riešenia sústav lineárnych rovníc

2010-05-30T20:24:23Z

Repto:

[[Kategória:Študentské práce]]
[[Kategória:Ročníkové práce]]
[[Kategória:Matematika]]
{{Praca_uvod|2|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__
= =
Existuje viacero metód riešenia lineárnych sústav rovníc. Poznáme dva základné typy metód: priame a iteračné metódy. Pre husté systémy, je vo väčšine prípadoch vhodnejšie použiť priame metódy naopak pri väčších riedkych maticiach sú vo väčšine prípadov vhodnejšie iteračné metódy
==Priame metódy==

Metódu riešenia sústavy, ktorá vedie k riešeniu po konečnom počte krokov, nazývame '''priama metóda'''. Základným princípom priamych metód je eliminácia.

=== Cramerovo pravidlo ===
Majme sústavu (1.1) . Ak je matica sústavy regulárna, teda determinant sústavy je nenulový, potom riešenie sústavy možno určiť nasledovne:

[[Image:Untitled%201_html_51683075.png]] , [[Image:Untitled%201_html_m3491dee3.png]] kde D je determinant matice sústavy A a [[Image:Untitled%201_html_18d6a5a7.png]] pre k=1, ... ,n sú determinanty matíc, ktoré vzniknú z matice A nahradením k-teho stĺpca tejto matice vektorom pravých strán b. Cramerovo pravidlo je vhodné len pre veľmi malé sústavy lineárnych rovníc. Pre väčšie sústavy by bolo potrebné počítať mnoho determinantov vysokého rádu, čo je dosť náročné. Preto sa táto metóda pre riešenie veľkých sústav nepoužíva.

=== Riešenie pomocou inverznej matice ===
Uvažujme sústavu (1.1) . Keďže je matica sústavy regulárna, existuje k nej inverzná matica

A-1 pre ktorú platí: [[Image:Untitled%201_html_5e10b471.png]] .

Potom platí [[Image:Untitled%201_html_m18a5a089.png]].

Potom z jednoznačnosti riešenia dostávame, že [[Image:Untitled%201_html_2884beac.png]]. Toto vyjadrenie riešenia sme dostali, tak že sme obe strany rovnosti [[Image:Untitled%201_html_3640367f.png]]zľava vynásobili maticou [[Image:Untitled%201_html_m7e0b28e3.png]]<nowiki> . Táto metóda tiež nie je vhodná pre matice väčších rozmerov [5].</nowiki>

=== Gaussova eliminačná metóda (GEM) ===
Základom tejto metódy je úprava sústavy na trojuholníkový tvar pomocou elementárnych riadkových úprav. Majme sústavu (1.1).

Teraz sa pomocou pričítania vhodných násobkov prvej rovnice z ostatných rovníc pokúsime eliminovať x1. Ak je prvok a11 rovný nule, vtedy vymeníme prvú rovnicu s prvou takou rovnicou, ktorej prvý prvok je nenulový. Keď budeme postupne odčítavať prvú rovnicu, vynásobenú číslom [[Image:Untitled%201_html_45c9b1ff.png]] , od i-tej rovnice , pre i=2,3, .... n , dostaneme

<center>a11 x1 + a12 x2 + ··· + a1n xn = b1 </center>

<center>a22 x2 + ··· + a2n xn = b2 </center>

an2 x2 + ··· + ann xn <nowiki>= b</nowiki>n

Horný index naznačuje, že sme ukončili prvý krok eliminácie.

Nové koeficienty vypočítame ako[[Image:Untitled%201_html_m66602679.png]] Teraz budeme pomocou vhodných násobkov druhej rovnice eliminovať x2 v tretej, štvrtej a n-tej rovnici. Opäť ak je a22<nowiki>=0, vymeníme druhú rovnicu s prvou z ďalších rovníc, v ktorej x</nowiki>2 je nenulová. Touto úpravou dostávame:

<center>a11 x1 + a12 x2 + a13 x3 ··· + a1n xn = b1 </center>

<center>a22 x2 + a23 x3 + ··· + a2n xn = b2 </center>

<center>a33 x3 + ··· + a3n xn = b3 </center>

an3 x3+ ··· + ann xn <nowiki>= b</nowiki>n

kde [[Image:Untitled%201_html_m64a5d78.png]]

Ak pokračujeme ďalej rovnakým spôsobom , dostaneme po n-1 krokoch sústavu v trojuholníkovom  tvare

a11 x1 + a12 x2 + a13 x3 ··· + a1n xn = b1

<center>a22 x2 + a23 x3 + ··· + a2n xn = b2 </center>

<center>a33 x3 + ··· + a3n xn = b3 </center>

<center>ann xn = bn</center>

Z tejto sústavy potom ľahko určíme hľadané riešenie :

[[Image:Untitled%201_html_m16d60ed1.png]]

[[Image:Untitled%201_html_7d21c7ec.png]]

[[Image:Untitled%201_html_376a8cc5.png]]

Toto sa nazýva spätná substitúcia. Číslo [[Image:Untitled%201_html_62fe2ece.png]] sa nazýva hlavný prvok alebo pivot. Pre odstránenie zaokrúhľovacích chýb sa používa modifikácia GEM, takzvaná '''eliminácia s čiastočným výberom hlavného prvku. '''

V prvom kroku eliminácie nájdeme rovnicu, ktorá má pri neznámej x1 v absolútnej hodnote najväčší koeficient. Vymeníme ju s prvou rovnicou. Potom pomocou jej násobkou eliminujeme x1 s ostatných rovníc. Potom nájdeme medzi všetkými rovnicami okrem prvej rovnice takú, kde je najväčší koeficient pri neznámej x2. Vymeníme ju z druhou rovnicou a pomocou jej násobkov eliminujeme x2 z ďalších rovníc. Podobne pokračujeme ďalej. Všeobecne v k -tom kroku eliminácie nájdeme medzi poslednými n-k+1 rovnicami tú, ktorá má najväčší koeficient pri xk. Vymeníme ju s k –tou rovnicou a pomocou nej eliminujeme xk z nasledujúcej rovnice.

Gaussova eliminačná metóda je pre veľké matice veľmi časovo náročná. Vyžaduje n3 operácií . Preto je táto metóda vhodná len pre riešenie nie príliš rozsiahlych sústav lineárnych rovníc. Jej modifikácie <nowiki>sa používajú pri niektorých iných metódach [4][5].

</nowiki>

== Iteračné metódy ==
Druhou skupinou metód pre riešenie sústav lineárnych rovníc sú '''iteračné metódy'''. Iteračné metódy na rozdiel od priamych metód nevedú k presnému riešeniu po konečnom počte krokov. U iteračných metód sa zvolí počiatočná aproximácia riešenia a určitým postupom ju v každom kroku metódy zlepšujeme. K riešeniu sa približujeme postupne a väčšinou ho dosiahneme až v limite. Avšak výpočet nemožno prevádzať do nekonečna, preto ho po istom čase ukončíme. Výsledkom bude približné riešenie sústavy. Štandardné eliminačné metódy nie sú vhodné na riešenie väčších riedkych sústav lineárnych rovníc. Pretože v priebehu eliminácie postupne dochádza k zaplňovaniu pôvodne nenulových pozícií v matici sústavy - matica prestáva byť riedkou. Naopak iteračné metódy sú vhodné aj pre riešenie veľkých riedkych systémov, pretože nulové prvky v riedkych systémoch zjednodušujú iterácie. Vďaka tomu sa zjednodušuje výpočtová náročnosť.

=== Jacobiho metóda ===
Maticu A rozložíme na súčet [[Image:Untitled%201_html_m62e15c23.png]] , kde D je diagonálna matica, ktorá má rovnakú diagonálu ako A. L je dolná trojuholníková časť matice A a U je horná trojuholníková časť matice A

[[Image:Untitled%201_html_m50986641.png]] [[Image:Untitled%201_html_m6517c304.png]]

Jacobiho iteračnú metódu definujeme na základe rozkladu  [[Image:Untitled%201_html_2d246193.png]] , kde [[Image:Untitled%201_html_61ae277a.png]] a [[Image:Untitled%201_html_m428e7dc2.png]] a zapisujeme ju v tvare [[Image:Untitled%201_html_4b590df3.png]].

Sústava s diagonálnou maticou sa rieši ľahko. Ak ju zapíšeme po zložkách dostaneme

[[Image:Untitled%201_html_m1dd89cf1.png]]Analýzou vlastností iteračnej matice [[Image:Untitled%201_html_m500824df.png]] možno ukázať , že Jacobiho metóda konverguje , keď A je rýdzo diagonálne dominantná.

'''Definícia:''' Hovoríme, že matica[[Image:Untitled%201_html_m1fd48037.png]] je '''rýdzo diagonálne dominantná''', ak

<nowiki>Teda inými slovami, v každom riadku je absolútna hodnota diagonálneho prvku väčšia ako súčet absolútnych hodnôt ostatných prvkov tohto riadku [7] .</nowiki>

=== Gauss-Seidelova metóda ===
Je podobná ako Jacobiho metóda. Líši sa v tom že pri výpočte ďalšej aproximácie sa vždy použijú najnovšie približné hodnoty x1,x2,...,xn, ktoré sú k dispozícii.

V maticovom tvare : [[Image:Untitled%201_html_m136f2e51.png]]

Analýzou vlastností iteračnej matice [[Image:Untitled%201_html_m3f9eccb1.png]] možno ukázať , že Gauss – Seidelova metóda konverguje , keď A je rýdzo diagonálne dominantná alebo kladne definitná.

'''Definícia:''' Hovoríme, že matica A je pozitívne definitná, ak pre ľubovoľný nenulový vektor

X platí: [[Image:Untitled%201_html_m40da36b.png]] .

<nowiki>Gauss-seidelova metóda konverguje rýchlejšie, a vyžaduje približne polovicu iterácií oproti Jacobiho metóde [7].

Moderné metódy riešenia veľkých sústav lineárnych rovníc

2010-05-30T18:55:00Z

Repto:

[[Kategória:Študentské práce]]
[[Kategória:Ročníkové práce]]
[[Kategória:Matematika]]
{{Draft}}
{{Hlavička_FM
|{{PAGENAME}}|Bc. Peter Poruban|Ing. Michal Štepanovský, PhD
|2009/2010
|Ročníková práca
|Mechatronika
}}
{{Praca_uvod|1|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||||||||||}}
{{abstrakt
|Práca sa zaoberá metódami vhodnými pre riešenie veľkých sústav lineárnych rovníc. Prvá časť sa zaoberá klasickými metódami pre riešenie sústav lineárnych rovníc. V ďalšej časti sú opísané priame metódy riešenia veľkých sústav . Tretia časť sa venuje moderným iteračným metódam. V práci sa podrobne zaoberáme metódou konjugovaných gradientov a geometrickou multigridovou metódou. Pre tieto dve metódy sme vypracovali ukážkové príklady riešenia. Posledná časť sa zaoberá využitím týchto metód.
|
}}
__TOC__
'''Úvod'''

V technickej praxi je častou úlohou riešiť sústavu lineárnych rovníc Ax= b s maticou rádu n, kde n je veľké číslo. Rozmery týchto matíc môžu byť rádovo v státisícoch, ale aj väčšie. Pri takýchto sústavách lineárnych rovníc sú niektoré tradičné metódy nepoužiteľné alebo sú neefektívne a časovo náročné. Taktiež niektoré z nich môžu pri maticiach veľmi veľkých rozmerov alebo zle podmienených maticiach zlyhať.
Stretávame sa s dvomi typmi systémov lineárnych rovníc. Systém lineárnych rovníc sa nazýva plný, ak väčšina prvkov je nenulová. Naopak riedke systémy sú také, kde len relatívne málo prvkov je nenulových. Pre riešenie riedkych systémov možno využiť ich vlastnosti. Vďaka tomu možno riešiť prostredníctvom niektorých algoritmov tieto matice efektívnejšie. Veľké riedke systémy je v technickej praxi veľmi často potrebné riešiť, napr. pri riešení parciálnych diferenciálnych rovníc.
Metódy pre riešenie lineárnych rovníc delíme na priame metódy a iteračné metódy. Priame metódy vedú k riešeniu po konečnom počte krokov. Naopak iteračné metódy konvergujú k riešeniu a presnosť riešenia je závislá od počtu iterácií . Priame metódy sú všeobecne vhodnejšie pre plné matice, naopak pre riedke systémy sú vhodné iteračné metódy.
Známe sú klasické priame metódy ako Cramerovo pravidlo, použitie inverznej matice a Gaussova eliminačná metóda. Tieto však nie sú pre systémy veľkých rozmerov vhodné. Taktiež sú známe klasické iteračné algoritmy ako je Jacobiho metóda a Gauss Seidelova metóda. Tieto sú vhodné aj pre riedke matice veľkých rozmerov.
Pre priame riešenie veľkých sústav je známych niekoľko algoritmov. V tejto práci je opísaný LU rozklad a Choleského rozklad. Tieto rozklady sa v rôznych obmenených podobách používajú pre priame riešenie veľkých sústav lineárnych rovníc.
V posledných desaťročiach bolo vypracovaných niekoľko moderných iteračných algoritmov pre riešenie veľkých sústav lineárnych rovníc. V práci sa zaoberáme gradientnými metódami a multigridovými metódami. Metóda konjugovaných gradientov konverguje k riešeniu rýchlejšie ako klasické iteračné metódy a je výhodná hlavne pre symetrické kladne definitné matice. Naopak, metóda bikonjugovaných gradientov a metóda GMRES sú vhodné aj pre nesymetrické matice. Multigridové metódy patria medzi najrýchlejšie iteračné metódy. Zlepšujú konvergenciu tým, že sa daná úloha opísaná určitou sieťou vyrieši najprv pre redšiu sieť a potom sa toto riešenie použije pri hľadaní riešenia v hustejšej sieti.

=Sústavy lineárnych rovníc a matice=
V tejto časti sú opísané základné pojmy lineárnej algebry , ktoré súvisia s výpočtom
sústav lineárnych rovníc . Taktiež sú tu opísané rôzne tvary matíc, ktoré sa používajú pri riešení sústav lineárnych rovníc.
==Systémy lineárnych rovníc==
Riešenie sústav lineárnych rovníc patrí medzi najdôležitejšie časti matematiky. Množstvo praktických úloh nakoniec vedie k riešeniu takýchto sústav. Tieto sústavy môžu byť často veľmi rozsiahle. Vtedy je n veľké číslo.
Systém n - lineárnych rovníc:

<math>
\begin{matrix}
a_{11}x_1+a_{12}x_2+...+a_{1n}x_n\\
a_{21}x_1+a_{22}x_2+...+a_{2n}x_n\\
.\\
.\\
.\\
a_{n1}x_1+a_{n2}x_2+...+a_{nn}x_n
\end{matrix}
</math>(1.1)

s neznámymi x_1,x_2,...,x_n.

Matica A(i,j) , kde i,j=1,..... n, sa nazýva maticou sústavy stĺpcový vektor b =(b1, ...., bn)^T vektor pravých strán .
Sústavu lineárnych rovníc môžeme zapísať v tvare

<math>Ax=b</math>

kde
<math>
A=
\begin{bmatrix}
a_{11} & \cdots & a_{1n} \\
\vdots & \ddots & \vdots \\
a_{n1} & \cdots & a_{nn}
\end{bmatrix},
x=
\begin{bmatrix}
x_{1}\\
\vdots\\
x_{n}
\end{bmatrix},
b=
\begin{bmatrix}
b_{1}\\
\vdots\\
b_{n}
\end{bmatrix}
</math>(1.2)

Rozlišujeme dva základné typy matíc sústav lineárnych rovníc:
;Plné:systémy, kde je väčšina prvkov nenulových
;Riedke:kde je naopak väčšina prvkov rovná nule. Túto ich vlastnosť možno využiť na riešenie prostredníctvom menšieho počtu krokov [4] [5].

==Matice==

Matica typu m[[Image:Untitled%201_html_4e44f889.png]]n je sústava mn čísiel, ktoré sú usporiadané v tvare obdĺžnikovej tabuľky. Všeobecná matica typu m[[Image:Untitled%201_html_4e44f889.png]]n je opísaná nasledovne:

A=[[Image:Untitled%201_html_m7af6f254.png]]

Prvok v i-tom riadku a j-tom stĺpci označujeme [[Image:Untitled%201_html_m49e52707.png]] (i=1, ..., m , j=1, ..., n)sú reálne prvky matice.

Matica A=[[Image:Untitled%201_html_m6a6585d2.png]]sa nazýva štvorcová ak m=n, teda ak má rovnaký počet riadkov a stĺpcov.

A=[[Image:Untitled%201_html_2dcaaa4e.png]]

Dôležitou štvorcovou je tzv. '''identická''' alebo '''jednotková matica'''. Jednotková matica má na diagonále jednotky a ostatné prvky u nulové. Označujeme ju písmenom I.

I=[[Image:Untitled%201_html_7d6b44a2.png]]

Pri násobení matíc má identická matica postavenie analogické číslu 1 pri násobení reálnych čísel. A*I=I*A=A

'''Transponovaná matica''' , je matica ktorá vznikne vymenením prvkov pôvodnej matice. Vymení sa súradnica riadku za súradnicu stĺpca. Potom transponovaná matica k matici A je :

AT<nowiki>=</nowiki>[[Image:Untitled%201_html_39d2bb89.png]]

'''Inverzná matica '''[[Image:Untitled%201_html_m7e0b28e3.png]] k štvorcovej [[Image:Untitled%201_html_696253c7.png]] matici A je taká , pre ktorú platí [[Image:Untitled%201_html_m5456b175.png]] , kde I je identická matica typu [[Image:Untitled%201_html_696253c7.png]]. K matici A existuje inverzná matica vtedy, keď je determinant matice A nenulový. Matica, ku ktorej existuje inverzná matica sa nazýva '''regulárna '''<nowiki>matica[5][6]. </nowiki>

=== Diagonálne matice ===
Diagonálna matica A je štvorcová matica typu n x n ktorá má nenulové prvky na hlavnej diagonále.

Existujú aj bidiagonálne a trojdiagonálne matice. Bidiagonálna matica je taká diagonálna matica, ktorá má ešte navyše nenulové horné (horná bidiagonálna matica) alebo dolné susedné prvky k diagonále (dolná bidiagonálna matica).

Horná bidiagonálna matica Dolná bidiagonálna matica

[[Image:Untitled%201_html_6c55de17.png]] [[Image:Untitled%201_html_m1022a49c.png]]

Ak sú nenulové horné aj dolné susedné prvky ku diagonálne, vtedy hovorí o trojdiagonálnej matici.

[[Image:Untitled%201_html_m7667af1.png]]

Na rozdiel od trojdiagonálnych systémov, ktoré majú nenulové prvky len na diagonále

plus a mínus jeden, '''skupinovo diagonálne systémy''' sú všeobecnejšie. Majú m1 ≥ 0 nenulových prvkov priamo vľavo(pod)od diagonály a m2<nowiki> ≥ 0 nenulových prvkov napravo(nad)od diagonály[6]. Diagonály nachádzajúce sa nad hlavnou diagonálou sa nazývajú superdiagonály. Subdiagonály sú naopak diagonály, ktoré sa nachádzajú pod hlavnou diagonálou. </nowiki>

=== Trojuholníkové matice ===
Trojuholníkové matice sú také matice, kde všetky prvky pod alebo nad diagonálou sú

nulové. Keď sú nulové prvky nad diagonálou hovoríme o dolnej trojuholníkovej matici, a naopak keď sú nulové prvky pod hlavnou diagonálou hovoríme o hornej trojuholníkovej matici .

Dolná trojuholníková matica Horná trojuholníková matica

[[Image:Untitled%201_html_mad4a9fb.png]] [[Image:Untitled%201_html_73ceb1e2.png]]

<nowiki>[5][6]</nowiki>

=== Blokové matice ===
Blokové matice sa používajú pre zjednodušenie počítania s maticami veľkých rozmerov.

Bloková matica je nejaká maticu A, ktorú rozdelíme na bloky [[Image:Untitled%201_html_1762b84b.png]].

Majme nasledovnú maticu A.

<center>A = [[Image:Untitled%201_html_4ffcae58.png]]</center>

Potom môžeme danú maticu zapísať nasledovne:

<center>A=[[Image:Untitled%201_html_m21ac2751.png]]</center>

kde je blok matice Aij tvorený prvkami matice A:

<center>A11 = [[Image:Untitled%201_html_m3d3ac50a.png]] A12 = [[Image:Untitled%201_html_4a93fe51.png]]</center>

A21 = [[Image:Untitled%201_html_m12099fb8.png]] A22 = [[Image:Untitled%201_html_757e3860.png]]

<nowiki>[3][6]</nowiki>

=== Ortogonálne matice ===
Ortogonálna matica (matica s ortonormálnymi stĺpcami) je matica so stĺpcami jednotkovej dĺžky, ktoré sú na seba kolmé. Matica typu [[Image:Untitled%201_html_696253c7.png]] je ortogonálna, ak [[Image:Untitled%201_html_12aad0e5.png]]. Podľa tejto rovnice má matica Q inverznú maticu a  platí [[Image:Untitled%201_html_m5665d8ff.png]] . Potom platí [[Image:Untitled%201_html_m34195d4f.png]]<nowiki>. Potom tieto tri vzťahy sú ekvivalentné a môžeme ich považovať za definíciu ortogonálnej matice [6].

Moderné metódy riešenia veľkých sústav lineárnych rovníc

2010-05-30T18:54:04Z

Repto:

[[Kategória:Študentské práce]]
[[Kategória:Ročníkové práce]]
[[Kategória:Matematika]]
{{Draft}}
{{Hlavička_FM
|{{PAGENAME}}|Bc. Peter Poruban|Ing. Michal Štepanovský, PhD
|2009/2010
|Ročníková práca
|Mechatronika
}}
{{Praca_uvod|1|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 lineárnych rovníc|Softvérové balíky pre riešenie veľkých lineárnych systémov||||||||||}}
{{abstrakt
|Práca sa zaoberá metódami vhodnými pre riešenie veľkých sústav lineárnych rovníc. Prvá časť sa zaoberá klasickými metódami pre riešenie sústav lineárnych rovníc. V ďalšej časti sú opísané priame metódy riešenia veľkých sústav . Tretia časť sa venuje moderným iteračným metódam. V práci sa podrobne zaoberáme metódou konjugovaných gradientov a geometrickou multigridovou metódou. Pre tieto dve metódy sme vypracovali ukážkové príklady riešenia. Posledná časť sa zaoberá využitím týchto metód.
|
}}
__TOC__
'''Úvod'''

V technickej praxi je častou úlohou riešiť sústavu lineárnych rovníc Ax= b s maticou rádu n, kde n je veľké číslo. Rozmery týchto matíc môžu byť rádovo v státisícoch, ale aj väčšie. Pri takýchto sústavách lineárnych rovníc sú niektoré tradičné metódy nepoužiteľné alebo sú neefektívne a časovo náročné. Taktiež niektoré z nich môžu pri maticiach veľmi veľkých rozmerov alebo zle podmienených maticiach zlyhať.
Stretávame sa s dvomi typmi systémov lineárnych rovníc. Systém lineárnych rovníc sa nazýva plný, ak väčšina prvkov je nenulová. Naopak riedke systémy sú také, kde len relatívne málo prvkov je nenulových. Pre riešenie riedkych systémov možno využiť ich vlastnosti. Vďaka tomu možno riešiť prostredníctvom niektorých algoritmov tieto matice efektívnejšie. Veľké riedke systémy je v technickej praxi veľmi často potrebné riešiť, napr. pri riešení parciálnych diferenciálnych rovníc.
Metódy pre riešenie lineárnych rovníc delíme na priame metódy a iteračné metódy. Priame metódy vedú k riešeniu po konečnom počte krokov. Naopak iteračné metódy konvergujú k riešeniu a presnosť riešenia je závislá od počtu iterácií . Priame metódy sú všeobecne vhodnejšie pre plné matice, naopak pre riedke systémy sú vhodné iteračné metódy.
Známe sú klasické priame metódy ako Cramerovo pravidlo, použitie inverznej matice a Gaussova eliminačná metóda. Tieto však nie sú pre systémy veľkých rozmerov vhodné. Taktiež sú známe klasické iteračné algoritmy ako je Jacobiho metóda a Gauss Seidelova metóda. Tieto sú vhodné aj pre riedke matice veľkých rozmerov.
Pre priame riešenie veľkých sústav je známych niekoľko algoritmov. V tejto práci je opísaný LU rozklad a Choleského rozklad. Tieto rozklady sa v rôznych obmenených podobách používajú pre priame riešenie veľkých sústav lineárnych rovníc.
V posledných desaťročiach bolo vypracovaných niekoľko moderných iteračných algoritmov pre riešenie veľkých sústav lineárnych rovníc. V práci sa zaoberáme gradientnými metódami a multigridovými metódami. Metóda konjugovaných gradientov konverguje k riešeniu rýchlejšie ako klasické iteračné metódy a je výhodná hlavne pre symetrické kladne definitné matice. Naopak, metóda bikonjugovaných gradientov a metóda GMRES sú vhodné aj pre nesymetrické matice. Multigridové metódy patria medzi najrýchlejšie iteračné metódy. Zlepšujú konvergenciu tým, že sa daná úloha opísaná určitou sieťou vyrieši najprv pre redšiu sieť a potom sa toto riešenie použije pri hľadaní riešenia v hustejšej sieti.

=Sústavy lineárnych rovníc a matice=
V tejto časti sú opísané základné pojmy lineárnej algebry , ktoré súvisia s výpočtom
sústav lineárnych rovníc . Taktiež sú tu opísané rôzne tvary matíc, ktoré sa používajú pri riešení sústav lineárnych rovníc.
==Systémy lineárnych rovníc==
Riešenie sústav lineárnych rovníc patrí medzi najdôležitejšie časti matematiky. Množstvo praktických úloh nakoniec vedie k riešeniu takýchto sústav. Tieto sústavy môžu byť často veľmi rozsiahle. Vtedy je n veľké číslo.
Systém n - lineárnych rovníc:

<math>
\begin{matrix}
a_{11}x_1+a_{12}x_2+...+a_{1n}x_n\\
a_{21}x_1+a_{22}x_2+...+a_{2n}x_n\\
.\\
.\\
.\\
a_{n1}x_1+a_{n2}x_2+...+a_{nn}x_n
\end{matrix}
</math>(1.1)

s neznámymi x_1,x_2,...,x_n.

Matica A(i,j) , kde i,j=1,..... n, sa nazýva maticou sústavy stĺpcový vektor b =(b1, ...., bn)^T vektor pravých strán .
Sústavu lineárnych rovníc môžeme zapísať v tvare

<math>Ax=b</math>

kde
<math>
A=
\begin{bmatrix}
a_{11} & \cdots & a_{1n} \\
\vdots & \ddots & \vdots \\
a_{n1} & \cdots & a_{nn}
\end{bmatrix},
x=
\begin{bmatrix}
x_{1}\\
\vdots\\
x_{n}
\end{bmatrix},
b=
\begin{bmatrix}
b_{1}\\
\vdots\\
b_{n}
\end{bmatrix}
</math>(1.2)

Rozlišujeme dva základné typy matíc sústav lineárnych rovníc:
;Plné:systémy, kde je väčšina prvkov nenulových
;Riedke:kde je naopak väčšina prvkov rovná nule. Túto ich vlastnosť možno využiť na riešenie prostredníctvom menšieho počtu krokov [4] [5].

==Matice==

Matica typu m[[Image:Untitled%201_html_4e44f889.png]]n je sústava mn čísiel, ktoré sú usporiadané v tvare obdĺžnikovej tabuľky. Všeobecná matica typu m[[Image:Untitled%201_html_4e44f889.png]]n je opísaná nasledovne:

A=[[Image:Untitled%201_html_m7af6f254.png]]

Prvok v i-tom riadku a j-tom stĺpci označujeme [[Image:Untitled%201_html_m49e52707.png]] (i=1, ..., m , j=1, ..., n)sú reálne prvky matice.

Matica A=[[Image:Untitled%201_html_m6a6585d2.png]]sa nazýva štvorcová ak m=n, teda ak má rovnaký počet riadkov a stĺpcov.

A=[[Image:Untitled%201_html_2dcaaa4e.png]]

Dôležitou štvorcovou je tzv. '''identická''' alebo '''jednotková matica'''. Jednotková matica má na diagonále jednotky a ostatné prvky u nulové. Označujeme ju písmenom I.

I=[[Image:Untitled%201_html_7d6b44a2.png]]

Pri násobení matíc má identická matica postavenie analogické číslu 1 pri násobení reálnych čísel. A*I=I*A=A

'''Transponovaná matica''' , je matica ktorá vznikne vymenením prvkov pôvodnej matice. Vymení sa súradnica riadku za súradnicu stĺpca. Potom transponovaná matica k matici A je :

AT<nowiki>=</nowiki>[[Image:Untitled%201_html_39d2bb89.png]]

'''Inverzná matica '''[[Image:Untitled%201_html_m7e0b28e3.png]] k štvorcovej [[Image:Untitled%201_html_696253c7.png]] matici A je taká , pre ktorú platí [[Image:Untitled%201_html_m5456b175.png]] , kde I je identická matica typu [[Image:Untitled%201_html_696253c7.png]]. K matici A existuje inverzná matica vtedy, keď je determinant matice A nenulový. Matica, ku ktorej existuje inverzná matica sa nazýva '''regulárna '''<nowiki>matica[5][6]. </nowiki>

=== Diagonálne matice ===
Diagonálna matica A je štvorcová matica typu n x n ktorá má nenulové prvky na hlavnej diagonále.

Existujú aj bidiagonálne a trojdiagonálne matice. Bidiagonálna matica je taká diagonálna matica, ktorá má ešte navyše nenulové horné (horná bidiagonálna matica) alebo dolné susedné prvky k diagonále (dolná bidiagonálna matica).

Horná bidiagonálna matica Dolná bidiagonálna matica

[[Image:Untitled%201_html_6c55de17.png]] [[Image:Untitled%201_html_m1022a49c.png]]

Ak sú nenulové horné aj dolné susedné prvky ku diagonálne, vtedy hovorí o trojdiagonálnej matici.

[[Image:Untitled%201_html_m7667af1.png]]

Na rozdiel od trojdiagonálnych systémov, ktoré majú nenulové prvky len na diagonále

plus a mínus jeden, '''skupinovo diagonálne systémy''' sú všeobecnejšie. Majú m1 ≥ 0 nenulových prvkov priamo vľavo(pod)od diagonály a m2<nowiki> ≥ 0 nenulových prvkov napravo(nad)od diagonály[6]. Diagonály nachádzajúce sa nad hlavnou diagonálou sa nazývajú superdiagonály. Subdiagonály sú naopak diagonály, ktoré sa nachádzajú pod hlavnou diagonálou. </nowiki>

=== Trojuholníkové matice ===
Trojuholníkové matice sú také matice, kde všetky prvky pod alebo nad diagonálou sú

nulové. Keď sú nulové prvky nad diagonálou hovoríme o dolnej trojuholníkovej matici, a naopak keď sú nulové prvky pod hlavnou diagonálou hovoríme o hornej trojuholníkovej matici .

Dolná trojuholníková matica Horná trojuholníková matica

[[Image:Untitled%201_html_mad4a9fb.png]] [[Image:Untitled%201_html_73ceb1e2.png]]

<nowiki>[5][6]</nowiki>

=== Blokové matice ===
Blokové matice sa používajú pre zjednodušenie počítania s maticami veľkých rozmerov.

Bloková matica je nejaká maticu A, ktorú rozdelíme na bloky [[Image:Untitled%201_html_1762b84b.png]].

Majme nasledovnú maticu A.

<center>A = [[Image:Untitled%201_html_4ffcae58.png]]</center>

Potom môžeme danú maticu zapísať nasledovne:

<center>A=[[Image:Untitled%201_html_m21ac2751.png]]</center>

kde je blok matice Aij tvorený prvkami matice A:

<center>A11 = [[Image:Untitled%201_html_m3d3ac50a.png]] A12 = [[Image:Untitled%201_html_4a93fe51.png]]</center>

A21 = [[Image:Untitled%201_html_m12099fb8.png]] A22 = [[Image:Untitled%201_html_757e3860.png]]

<nowiki>[3][6]</nowiki>

=== Ortogonálne matice ===
Ortogonálna matica (matica s ortonormálnymi stĺpcami) je matica so stĺpcami jednotkovej dĺžky, ktoré sú na seba kolmé. Matica typu [[Image:Untitled%201_html_696253c7.png]] je ortogonálna, ak [[Image:Untitled%201_html_12aad0e5.png]]. Podľa tejto rovnice má matica Q inverznú maticu a  platí [[Image:Untitled%201_html_m5665d8ff.png]] . Potom platí [[Image:Untitled%201_html_m34195d4f.png]]<nowiki>. Potom tieto tri vzťahy sú ekvivalentné a môžeme ich považovať za definíciu ortogonálnej matice [6].

Klasické metódy riešenia sústav lineárnych rovníc

2010-05-30T18:33:33Z

Repto:

[[Kategória:Študentské práce]]
[[Kategória:Ročníkové práce]]
[[Kategória:Matematika]]
{{Praca_uvod|2|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|Metódy riešenia veľkých sústav lineárnych rovníc|||||||||}}
__TOC__
= =
Existuje viacero metód riešenia lineárnych sústav rovníc. Poznáme dva základné typy metód: priame a iteračné metódy. Pre husté systémy, je vo väčšine prípadoch vhodnejšie použiť priame metódy naopak pri väčších riedkych maticiach sú vo väčšine prípadov vhodnejšie iteračné metódy
==Priame metódy==

Metódu riešenia sústavy, ktorá vedie k riešeniu po konečnom počte krokov, nazývame '''priama metóda'''. Základným princípom priamych metód je eliminácia.

=== Cramerovo pravidlo ===
Majme sústavu (1.1) . Ak je matica sústavy regulárna, teda determinant sústavy je nenulový, potom riešenie sústavy možno určiť nasledovne:

[[Image:Untitled%201_html_51683075.png]] , [[Image:Untitled%201_html_m3491dee3.png]] kde D je determinant matice sústavy A a [[Image:Untitled%201_html_18d6a5a7.png]] pre k=1, ... ,n sú determinanty matíc, ktoré vzniknú z matice A nahradením k-teho stĺpca tejto matice vektorom pravých strán b. Cramerovo pravidlo je vhodné len pre veľmi malé sústavy lineárnych rovníc. Pre väčšie sústavy by bolo potrebné počítať mnoho determinantov vysokého rádu, čo je dosť náročné. Preto sa táto metóda pre riešenie veľkých sústav nepoužíva.

=== Riešenie pomocou inverznej matice ===
Uvažujme sústavu (1.1) . Keďže je matica sústavy regulárna, existuje k nej inverzná matica

A-1 pre ktorú platí: [[Image:Untitled%201_html_5e10b471.png]] .

Potom platí [[Image:Untitled%201_html_m18a5a089.png]].

Potom z jednoznačnosti riešenia dostávame, že [[Image:Untitled%201_html_2884beac.png]]. Toto vyjadrenie riešenia sme dostali, tak že sme obe strany rovnosti [[Image:Untitled%201_html_3640367f.png]]zľava vynásobili maticou [[Image:Untitled%201_html_m7e0b28e3.png]]<nowiki> . Táto metóda tiež nie je vhodná pre matice väčších rozmerov [5].</nowiki>

=== Gaussova eliminačná metóda (GEM) ===
Základom tejto metódy je úprava sústavy na trojuholníkový tvar pomocou elementárnych riadkových úprav. Majme sústavu (1.1).

Teraz sa pomocou pričítania vhodných násobkov prvej rovnice z ostatných rovníc pokúsime eliminovať x1. Ak je prvok a11 rovný nule, vtedy vymeníme prvú rovnicu s prvou takou rovnicou, ktorej prvý prvok je nenulový. Keď budeme postupne odčítavať prvú rovnicu, vynásobenú číslom [[Image:Untitled%201_html_45c9b1ff.png]] , od i-tej rovnice , pre i=2,3, .... n , dostaneme

<center>a11 x1 + a12 x2 + ··· + a1n xn = b1 </center>

<center>a22 x2 + ··· + a2n xn = b2 </center>

an2 x2 + ··· + ann xn <nowiki>= b</nowiki>n

Horný index naznačuje, že sme ukončili prvý krok eliminácie.

Nové koeficienty vypočítame ako[[Image:Untitled%201_html_m66602679.png]] Teraz budeme pomocou vhodných násobkov druhej rovnice eliminovať x2 v tretej, štvrtej a n-tej rovnici. Opäť ak je a22<nowiki>=0, vymeníme druhú rovnicu s prvou z ďalších rovníc, v ktorej x</nowiki>2 je nenulová. Touto úpravou dostávame:

<center>a11 x1 + a12 x2 + a13 x3 ··· + a1n xn = b1 </center>

<center>a22 x2 + a23 x3 + ··· + a2n xn = b2 </center>

<center>a33 x3 + ··· + a3n xn = b3 </center>

an3 x3+ ··· + ann xn <nowiki>= b</nowiki>n

kde [[Image:Untitled%201_html_m64a5d78.png]]

Ak pokračujeme ďalej rovnakým spôsobom , dostaneme po n-1 krokoch sústavu v trojuholníkovom  tvare

a11 x1 + a12 x2 + a13 x3 ··· + a1n xn = b1

<center>a22 x2 + a23 x3 + ··· + a2n xn = b2 </center>

<center>a33 x3 + ··· + a3n xn = b3 </center>

<center>ann xn = bn</center>

Z tejto sústavy potom ľahko určíme hľadané riešenie :

[[Image:Untitled%201_html_m16d60ed1.png]]

[[Image:Untitled%201_html_7d21c7ec.png]]

[[Image:Untitled%201_html_376a8cc5.png]]

Toto sa nazýva spätná substitúcia. Číslo [[Image:Untitled%201_html_62fe2ece.png]] sa nazýva hlavný prvok alebo pivot. Pre odstránenie zaokrúhľovacích chýb sa používa modifikácia GEM, takzvaná '''eliminácia s čiastočným výberom hlavného prvku. '''

V prvom kroku eliminácie nájdeme rovnicu, ktorá má pri neznámej x1 v absolútnej hodnote najväčší koeficient. Vymeníme ju s prvou rovnicou. Potom pomocou jej násobkou eliminujeme x1 s ostatných rovníc. Potom nájdeme medzi všetkými rovnicami okrem prvej rovnice takú, kde je najväčší koeficient pri neznámej x2. Vymeníme ju z druhou rovnicou a pomocou jej násobkov eliminujeme x2 z ďalších rovníc. Podobne pokračujeme ďalej. Všeobecne v k -tom kroku eliminácie nájdeme medzi poslednými n-k+1 rovnicami tú, ktorá má najväčší koeficient pri xk. Vymeníme ju s k –tou rovnicou a pomocou nej eliminujeme xk z nasledujúcej rovnice.

Gaussova eliminačná metóda je pre veľké matice veľmi časovo náročná. Vyžaduje n3 operácií . Preto je táto metóda vhodná len pre riešenie nie príliš rozsiahlych sústav lineárnych rovníc. Jej modifikácie <nowiki>sa používajú pri niektorých iných metódach [4][5].

</nowiki>

== Iteračné metódy ==
Druhou skupinou metód pre riešenie sústav lineárnych rovníc sú '''iteračné metódy'''. Iteračné metódy na rozdiel od priamych metód nevedú k presnému riešeniu po konečnom počte krokov. U iteračných metód sa zvolí počiatočná aproximácia riešenia a určitým postupom ju v každom kroku metódy zlepšujeme. K riešeniu sa približujeme postupne a väčšinou ho dosiahneme až v limite. Avšak výpočet nemožno prevádzať do nekonečna, preto ho po istom čase ukončíme. Výsledkom bude približné riešenie sústavy. Štandardné eliminačné metódy nie sú vhodné na riešenie väčších riedkych sústav lineárnych rovníc. Pretože v priebehu eliminácie postupne dochádza k zaplňovaniu pôvodne nenulových pozícií v matici sústavy - matica prestáva byť riedkou. Naopak iteračné metódy sú vhodné aj pre riešenie veľkých riedkych systémov, pretože nulové prvky v riedkych systémoch zjednodušujú iterácie. Vďaka tomu sa zjednodušuje výpočtová náročnosť.

=== Jacobiho metóda ===
Maticu A rozložíme na súčet [[Image:Untitled%201_html_m62e15c23.png]] , kde D je diagonálna matica, ktorá má rovnakú diagonálu ako A. L je dolná trojuholníková časť matice A a U je horná trojuholníková časť matice A

[[Image:Untitled%201_html_m50986641.png]] [[Image:Untitled%201_html_m6517c304.png]]

Jacobiho iteračnú metódu definujeme na základe rozkladu  [[Image:Untitled%201_html_2d246193.png]] , kde [[Image:Untitled%201_html_61ae277a.png]] a [[Image:Untitled%201_html_m428e7dc2.png]] a zapisujeme ju v tvare [[Image:Untitled%201_html_4b590df3.png]].

Sústava s diagonálnou maticou sa rieši ľahko. Ak ju zapíšeme po zložkách dostaneme

[[Image:Untitled%201_html_m1dd89cf1.png]]Analýzou vlastností iteračnej matice [[Image:Untitled%201_html_m500824df.png]] možno ukázať , že Jacobiho metóda konverguje , keď A je rýdzo diagonálne dominantná.

'''Definícia:''' Hovoríme, že matica[[Image:Untitled%201_html_m1fd48037.png]] je '''rýdzo diagonálne dominantná''', ak

<nowiki>Teda inými slovami, v každom riadku je absolútna hodnota diagonálneho prvku väčšia ako súčet absolútnych hodnôt ostatných prvkov tohto riadku [7] .</nowiki>

=== Gauss-Seidelova metóda ===
Je podobná ako Jacobiho metóda. Líši sa v tom že pri výpočte ďalšej aproximácie sa vždy použijú najnovšie približné hodnoty x1,x2,...,xn, ktoré sú k dispozícii.

V maticovom tvare : [[Image:Untitled%201_html_m136f2e51.png]]

Analýzou vlastností iteračnej matice [[Image:Untitled%201_html_m3f9eccb1.png]] možno ukázať , že Gauss – Seidelova metóda konverguje , keď A je rýdzo diagonálne dominantná alebo kladne definitná.

'''Definícia:''' Hovoríme, že matica A je pozitívne definitná, ak pre ľubovoľný nenulový vektor

X platí: [[Image:Untitled%201_html_m40da36b.png]] .

<nowiki>Gauss-seidelova metóda konverguje rýchlejšie, a vyžaduje približne polovicu iterácií oproti Jacobiho metóde [7].

Klasické metódy riešenia sústav lineárnych rovníc

2010-05-30T18:23:47Z

Repto:

Moderné metódy riešenia veľkých sústav lineárnych rovníc

2010-05-30T18:05:18Z

Repto:

[[Kategória:Študentské práce]]
[[Kategória:Ročníkové práce]]
[[Kategória:Matematika]]
{{Draft}}
{{Hlavička_FM
|{{PAGENAME}}|Bc. Peter Poruban|Ing. Michal Štepanovský, PhD
|2009/2010
|Ročníková práca
|Mechatronika
}}
{{Praca_uvod|1|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|Metódy riešenia veľkých sústav lineárnych rovníc|||||||||}}
{{abstrakt
|Práca sa zaoberá metódami vhodnými pre riešenie veľkých sústav lineárnych rovníc. Prvá časť sa zaoberá klasickými metódami pre riešenie sústav lineárnych rovníc. V ďalšej časti sú opísané priame metódy riešenia veľkých sústav . Tretia časť sa venuje moderným iteračným metódam. V práci sa podrobne zaoberáme metódou konjugovaných gradientov a geometrickou multigridovou metódou. Pre tieto dve metódy sme vypracovali ukážkové príklady riešenia. Posledná časť sa zaoberá využitím týchto metód.
|
}}
__TOC__
'''Úvod'''

V technickej praxi je častou úlohou riešiť sústavu lineárnych rovníc Ax= b s maticou rádu n, kde n je veľké číslo. Rozmery týchto matíc môžu byť rádovo v státisícoch, ale aj väčšie. Pri takýchto sústavách lineárnych rovníc sú niektoré tradičné metódy nepoužiteľné alebo sú neefektívne a časovo náročné. Taktiež niektoré z nich môžu pri maticiach veľmi veľkých rozmerov alebo zle podmienených maticiach zlyhať.
Stretávame sa s dvomi typmi systémov lineárnych rovníc. Systém lineárnych rovníc sa nazýva plný, ak väčšina prvkov je nenulová. Naopak riedke systémy sú také, kde len relatívne málo prvkov je nenulových. Pre riešenie riedkych systémov možno využiť ich vlastnosti. Vďaka tomu možno riešiť prostredníctvom niektorých algoritmov tieto matice efektívnejšie. Veľké riedke systémy je v technickej praxi veľmi často potrebné riešiť, napr. pri riešení parciálnych diferenciálnych rovníc.
Metódy pre riešenie lineárnych rovníc delíme na priame metódy a iteračné metódy. Priame metódy vedú k riešeniu po konečnom počte krokov. Naopak iteračné metódy konvergujú k riešeniu a presnosť riešenia je závislá od počtu iterácií . Priame metódy sú všeobecne vhodnejšie pre plné matice, naopak pre riedke systémy sú vhodné iteračné metódy.
Známe sú klasické priame metódy ako Cramerovo pravidlo, použitie inverznej matice a Gaussova eliminačná metóda. Tieto však nie sú pre systémy veľkých rozmerov vhodné. Taktiež sú známe klasické iteračné algoritmy ako je Jacobiho metóda a Gauss Seidelova metóda. Tieto sú vhodné aj pre riedke matice veľkých rozmerov.
Pre priame riešenie veľkých sústav je známych niekoľko algoritmov. V tejto práci je opísaný LU rozklad a Choleského rozklad. Tieto rozklady sa v rôznych obmenených podobách používajú pre priame riešenie veľkých sústav lineárnych rovníc.
V posledných desaťročiach bolo vypracovaných niekoľko moderných iteračných algoritmov pre riešenie veľkých sústav lineárnych rovníc. V práci sa zaoberáme gradientnými metódami a multigridovými metódami. Metóda konjugovaných gradientov konverguje k riešeniu rýchlejšie ako klasické iteračné metódy a je výhodná hlavne pre symetrické kladne definitné matice. Naopak, metóda bikonjugovaných gradientov a metóda GMRES sú vhodné aj pre nesymetrické matice. Multigridové metódy patria medzi najrýchlejšie iteračné metódy. Zlepšujú konvergenciu tým, že sa daná úloha opísaná určitou sieťou vyrieši najprv pre redšiu sieť a potom sa toto riešenie použije pri hľadaní riešenia v hustejšej sieti.

=Sústavy lineárnych rovníc a matice=
V tejto časti sú opísané základné pojmy lineárnej algebry , ktoré súvisia s výpočtom
sústav lineárnych rovníc . Taktiež sú tu opísané rôzne tvary matíc, ktoré sa používajú pri riešení sústav lineárnych rovníc.
==Systémy lineárnych rovníc==
Riešenie sústav lineárnych rovníc patrí medzi najdôležitejšie časti matematiky. Množstvo praktických úloh nakoniec vedie k riešeniu takýchto sústav. Tieto sústavy môžu byť často veľmi rozsiahle. Vtedy je n veľké číslo.
Systém n - lineárnych rovníc:

<math>
\begin{matrix}
a_{11}x_1+a_{12}x_2+...+a_{1n}x_n\\
a_{21}x_1+a_{22}x_2+...+a_{2n}x_n\\
.\\
.\\
.\\
a_{n1}x_1+a_{n2}x_2+...+a_{nn}x_n
\end{matrix}
</math>(1.1)

s neznámymi x_1,x_2,...,x_n.

Matica A(i,j) , kde i,j=1,..... n, sa nazýva maticou sústavy stĺpcový vektor b =(b1, ...., bn)^T vektor pravých strán .
Sústavu lineárnych rovníc môžeme zapísať v tvare

<math>Ax=b</math>

kde
<math>
A=
\begin{bmatrix}
a_{11} & \cdots & a_{1n} \\
\vdots & \ddots & \vdots \\
a_{n1} & \cdots & a_{nn}
\end{bmatrix},
x=
\begin{bmatrix}
x_{1}\\
\vdots\\
x_{n}
\end{bmatrix},
b=
\begin{bmatrix}
b_{1}\\
\vdots\\
b_{n}
\end{bmatrix}
</math>(1.2)

Rozlišujeme dva základné typy matíc sústav lineárnych rovníc:
;Plné:systémy, kde je väčšina prvkov nenulových
;Riedke:kde je naopak väčšina prvkov rovná nule. Túto ich vlastnosť možno využiť na riešenie prostredníctvom menšieho počtu krokov [4] [5].

==Matice==

Matica typu m[[Image:Untitled%201_html_4e44f889.png]]n je sústava mn čísiel, ktoré sú usporiadané v tvare obdĺžnikovej tabuľky. Všeobecná matica typu m[[Image:Untitled%201_html_4e44f889.png]]n je opísaná nasledovne:

A=[[Image:Untitled%201_html_m7af6f254.png]]

Prvok v i-tom riadku a j-tom stĺpci označujeme [[Image:Untitled%201_html_m49e52707.png]] (i=1, ..., m , j=1, ..., n)sú reálne prvky matice.

Matica A=[[Image:Untitled%201_html_m6a6585d2.png]]sa nazýva štvorcová ak m=n, teda ak má rovnaký počet riadkov a stĺpcov.

A=[[Image:Untitled%201_html_2dcaaa4e.png]]

Dôležitou štvorcovou je tzv. '''identická''' alebo '''jednotková matica'''. Jednotková matica má na diagonále jednotky a ostatné prvky u nulové. Označujeme ju písmenom I.

I=[[Image:Untitled%201_html_7d6b44a2.png]]

Pri násobení matíc má identická matica postavenie analogické číslu 1 pri násobení reálnych čísel. A*I=I*A=A

'''Transponovaná matica''' , je matica ktorá vznikne vymenením prvkov pôvodnej matice. Vymení sa súradnica riadku za súradnicu stĺpca. Potom transponovaná matica k matici A je :

AT<nowiki>=</nowiki>[[Image:Untitled%201_html_39d2bb89.png]]

'''Inverzná matica '''[[Image:Untitled%201_html_m7e0b28e3.png]] k štvorcovej [[Image:Untitled%201_html_696253c7.png]] matici A je taká , pre ktorú platí [[Image:Untitled%201_html_m5456b175.png]] , kde I je identická matica typu [[Image:Untitled%201_html_696253c7.png]]. K matici A existuje inverzná matica vtedy, keď je determinant matice A nenulový. Matica, ku ktorej existuje inverzná matica sa nazýva '''regulárna '''<nowiki>matica[5][6]. </nowiki>

=== Diagonálne matice ===
Diagonálna matica A je štvorcová matica typu n x n ktorá má nenulové prvky na hlavnej diagonále.

Existujú aj bidiagonálne a trojdiagonálne matice. Bidiagonálna matica je taká diagonálna matica, ktorá má ešte navyše nenulové horné (horná bidiagonálna matica) alebo dolné susedné prvky k diagonále (dolná bidiagonálna matica).

Horná bidiagonálna matica Dolná bidiagonálna matica

[[Image:Untitled%201_html_6c55de17.png]] [[Image:Untitled%201_html_m1022a49c.png]]

Ak sú nenulové horné aj dolné susedné prvky ku diagonálne, vtedy hovorí o trojdiagonálnej matici.

[[Image:Untitled%201_html_m7667af1.png]]

Na rozdiel od trojdiagonálnych systémov, ktoré majú nenulové prvky len na diagonále

plus a mínus jeden, '''skupinovo diagonálne systémy''' sú všeobecnejšie. Majú m1 ≥ 0 nenulových prvkov priamo vľavo(pod)od diagonály a m2<nowiki> ≥ 0 nenulových prvkov napravo(nad)od diagonály[6]. Diagonály nachádzajúce sa nad hlavnou diagonálou sa nazývajú superdiagonály. Subdiagonály sú naopak diagonály, ktoré sa nachádzajú pod hlavnou diagonálou. </nowiki>

=== Trojuholníkové matice ===
Trojuholníkové matice sú také matice, kde všetky prvky pod alebo nad diagonálou sú

nulové. Keď sú nulové prvky nad diagonálou hovoríme o dolnej trojuholníkovej matici, a naopak keď sú nulové prvky pod hlavnou diagonálou hovoríme o hornej trojuholníkovej matici .

Dolná trojuholníková matica Horná trojuholníková matica

[[Image:Untitled%201_html_mad4a9fb.png]] [[Image:Untitled%201_html_73ceb1e2.png]]

<nowiki>[5][6]</nowiki>

=== Blokové matice ===
Blokové matice sa používajú pre zjednodušenie počítania s maticami veľkých rozmerov.

Bloková matica je nejaká maticu A, ktorú rozdelíme na bloky [[Image:Untitled%201_html_1762b84b.png]].

Majme nasledovnú maticu A.

<center>A = [[Image:Untitled%201_html_4ffcae58.png]]</center>

Potom môžeme danú maticu zapísať nasledovne:

<center>A=[[Image:Untitled%201_html_m21ac2751.png]]</center>

kde je blok matice Aij tvorený prvkami matice A:

<center>A11 = [[Image:Untitled%201_html_m3d3ac50a.png]] A12 = [[Image:Untitled%201_html_4a93fe51.png]]</center>

A21 = [[Image:Untitled%201_html_m12099fb8.png]] A22 = [[Image:Untitled%201_html_757e3860.png]]

<nowiki>[3][6]</nowiki>

=== Ortogonálne matice ===
Ortogonálna matica (matica s ortonormálnymi stĺpcami) je matica so stĺpcami jednotkovej dĺžky, ktoré sú na seba kolmé. Matica typu [[Image:Untitled%201_html_696253c7.png]] je ortogonálna, ak [[Image:Untitled%201_html_12aad0e5.png]]. Podľa tejto rovnice má matica Q inverznú maticu a  platí [[Image:Untitled%201_html_m5665d8ff.png]] . Potom platí [[Image:Untitled%201_html_m34195d4f.png]]<nowiki>. Potom tieto tri vzťahy sú ekvivalentné a môžeme ich považovať za definíciu ortogonálnej matice [6].

Súbor:Untitled 1 html 4e44f889.png

2010-05-30T17:39:14Z

Repto:

Metódy riešenia veľkých sústav lineárnych rovníc

2010-05-30T11:25:13Z

Repto: /* Použitá literatúra */

Metódy riešenia veľkých sústav lineárnych rovníc

2010-05-30T11:20:20Z

Repto:

Moderné metódy riešenia veľkých sústav lineárnych rovníc

2010-05-30T11:18:54Z

Repto: