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

	Trenčianska Univerzita Alexandra Dubčeka v Trenčíne Fakulta Mechatroniky
	Moderné metódy riešenia veľkých sústav lineárnych rovníc zadanie práce Ročníková práca

Autor:	Bc. Peter Poruban
Pedagogický vedúci:	Ing. Michal Štepanovský, PhD
Študijný odbor:	Mechatronika
Akademický rok	2009/2010

Obsah práce

1.	Sústavy lineárnych rovníc a matice
2.	Klasické metódy riešenia sústav lineárnych rovníc
3.	Metódy riešenia veľkých sústav lineárnych rovníc

Abstrakt slovenksy.

Abstract anglicky

Ú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. Výpočet takýchto sústav sa v súčasnosti realizuje samozrejme na počítači. 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. 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ú priame metódy ako Cramerovo pravidlo, použitie inverznej matice a Gaussova eliminačná metóda. Cramerovo pravidlo a použitie inverznej matice sú vhodne len pre matice malých rozmerov. Gaussovu eliminačnú metódu možno použiť pre riešenie plných systémov. Pri riedkych systémoch veľkých rozmerov použitím Gaussovej eliminačnej metódy môže dôjsť k zaplneniu pôvodne nulových prvkov nenulovými prvkami a algoritmus môže zlyhať. Pre riešenie veľkých matíc sa kvôli jej náročnosti častejšie používajú jej modifikácie. 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. V posledných desaťročiach bolo vypracovaných niekoľko úspešných algoritmov pre riešenie veľkých sústav lineárnych rovníc. V tejto práci sa venujeme riešeniu rovníc so všeobecnými maticami veľkých rozmerov, ale taktiež riešeniu diagonálnych a skupinovo diagonálnych systémov, kde sú nenulové prvky len na diagonále a v okolí nej. Pre riešenie lineárnych systémov sú opísané niektoré rozklady, ktoré rozdelia danú maticu sústavy na zväčša dve jednoduchšie sústavy. Tieto zjednodušené zväčša trojuholníkové systémy sa potom riešia podľa algoritmov, ktoré sú tiež v tejto práci opísané.

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