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

Abstract

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