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

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