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.	Priame metódy pre riešenie veľkých sústav rovníc
4.	Moderné metódy riešenia veľkých sústav rovníc
5.	Softvérové balíky pre riešenie veľkých lineárnych systémov

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₁,x₂,...,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 mn je sústava mn čísiel, ktoré sú usporiadané v tvare obdĺžnikovej tabuľky. Všeobecná matica typu mn je opísaná nasledovne:

[math]A=\left[ \begin{matrix} {{a}_{11}} & \cdots & {{a}_{1n}} \\ \vdots & \ddots & \vdots \\ {{a}_{m1}} & \cdots & {{a}_{mn}} \\ \end{matrix} \right][/math]

Prvok v i-tom riadku a j-tom stĺpci označujeme [math]a_{ij}[/math] (i=1, ..., m , j=1, ..., n)sú reálne prvky matice.

Matica [math]A={{\left[ {{a}_{ij}} \right]}_{m\times n}}[/math] sa nazýva štvorcová ak m=n, teda ak má rovnaký počet riadkov a stĺpcov.

[math]A=~\left[ \begin{matrix} {{a}_{11}} & \cdots & {{a}_{1n}} \\ \vdots & \ddots & \vdots \\ {{a}_{n1}} & \cdots & {{a}_{nn}} \\ \end{matrix} \right][/math]

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.

[math]I=\left[ \begin{matrix} 1 & \cdots & 0 \\ \vdots & \ddots & \vdots \\ 0 & \cdots & 1 \\ \end{matrix} \right][/math]

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 :

[math]{{A}^{T}}=\left[ \begin{matrix} {{a}_{11}} & \cdots & {{a}_{1m}} \\ \vdots & \ddots & \vdots \\ {{a}_{n1}} & \cdots & {{a}_{nm}} \\ \end{matrix} \right][/math]

Inverzná matica [math]A^{-1}[/math] k štvorcovej [math]n~\times n[/math] matici A je taká, pre ktorú platí [math]{{A}^{-1}}A=~A*{{A}^{-1}}=I[/math], kde I je identická matica typu [math]n~\times n[/math]. K matici A existuje inverzná matica vtedy, keď je determinant matice A nenulový. Matica, ku ktorej existuje inverzná matica sa nazýva regulárna matica[5][6].

Diagonálne matice

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

[math]A=\left[ \begin{matrix} {{a}_{11}} & 0 & 0 \\ 0 & {{a}_{22}} & 0 \\ 0 & 0 & {{a}_{33}} \\ \end{matrix} \right][/math]

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

[math]\left[ \begin{matrix} \times & \times & {} & {} \\ {} & \times & \times & {} \\ {} & {} & \times & \times \\ {} & {} & {} & \times \\ \end{matrix} \right][/math]

Dolná bidiagonálna matica

[math]\left[ \begin{matrix} \times & {} & {} & {} \\ \times & \times & {} & {} \\ {} & \times & \times & {} \\ {} & {} & \times & \times \\ \end{matrix} \right][/math]

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

[math]\left[ \begin{matrix} \times & \times & {} & {} \\ \times & \times & \times & {} \\ {} & \times & \times & \times \\ {} & {} & \times & \times \\ \end{matrix} \right][/math]

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

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:

[math]\left[ \begin{matrix} {{a}_{11}} & 0 & 0 \\ {{a}_{21}} & {{a}_{22}} & 0 \\ {{a}_{31}} & {{a}_{32}} & {{a}_{33}} \\ \end{matrix} \right][/math]

Horná trojuholníková matica:

[math]\left[ \begin{matrix} {{a}_{11}} & {{a}_{12}} & {{a}_{13}} \\ 0 & {{a}_{22}} & {{a}_{23}} \\ 0 & 0 & {{a}_{33}} \\ \end{matrix} \right][/math]

[5][6]

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 [math]A_{ij}[/math].

Majme nasledovnú maticu A.

[math]A=\left[ \begin{matrix} {{a}_{11}} & \ldots & {{a}_{1n}} \\ \vdots & \ddots & \vdots \\ {{a}_{n1}} & \ldots & {{a}_{nn}} \\ \end{matrix} \right][/math]

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

[math]A=\left[ \begin{matrix} {{A}_{11}} & {{A}_{12}} \\ {{A}_{21}} & {{A}_{22}} \\ \end{matrix} \right][/math]

kde je blok matice [math]A_{ij}[/math] tvorený prvkami matice A:

[math]{{\text{A}}_{\text{11}}}=~\left[ \begin{matrix} {{a}_{1,1}} & \ldots & {{a}_{1,q}} \\ \vdots & \ddots & \vdots \\ {{a}_{p,1}} & \ldots & {{a}_{p,q}} \\ \end{matrix} \right][/math] [math]{{\text{A}}_{\text{12}}}=~\left[ \begin{matrix} {{a}_{1,q+1}} & \ldots & {{a}_{1,n}} \\ \vdots & \ddots & \vdots \\ {{a}_{p,q+1}} & \ldots & {{a}_{p,n}} \\ \end{matrix} \right][/math]

[math]{{\text{A}}_{\text{21}}}=~\left[ \begin{matrix} {{a}_{p+1,1}} & \ldots & {{a}_{p+1,q}} \\ \vdots & \ddots & \vdots \\ {{a}_{n,1}} & \ldots & {{a}_{n,q}} \\ \end{matrix} \right][/math] [math]{{\text{A}}_{\text{22}}}=~\left[ \begin{matrix} {{a}_{p+1,q+1}} & \ldots & {{a}_{p+1,n}} \\ \vdots & \ddots & \vdots \\ {{a}_{n,q+1}} & \ldots & {{a}_{n,n}} \\ \end{matrix} \right][/math]

[3][6]

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 n×n je ortogonálna, ak [math]Q{{Q}^{T}}=I[/math]. Podľa tejto rovnice má matica Q inverznú maticu a  platí [math]{{Q}^{T}}={{Q}^{(-1)}}[/math]. Potom platí [math]{{Q}^{T}}Q=I[/math]. Potom tieto tri vzťahy sú ekvivalentné a môžeme ich považovať za definíciu ortogonálnej matice [6].