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

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

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: [math]~{{x}_{1}}=\frac{{{D}_{1}}}{D},{{x}_{2}}=\frac{{{D}_{2}}}{D},~\ldots ,~{{x}_{n}}=\frac{{{D}_{n}}}{D}[/math] kde D je determinant matice sústavy A a [math]D_k[/math] 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

[math]A^{-1}[/math] pre ktorú platí: [math]{{A}^{-1}}A=A{{A}^{-1}}=I[/math].

Potom platí [math]A\left( {{A}^{-1}}b \right)=\left( A{{A}^{-1}} \right)b=Ib=b[/math].

Potom z jednoznačnosti riešenia dostávame, že [math]x={{A}^{-1}}b[/math]. Toto vyjadrenie riešenia sme dostali, tak že sme obe strany rovnosti [math]Ax=b[/math] zľava vynásobili maticou [math]A^{-1}[/math]. Táto metóda tiež nie je vhodná pre matice väčších rozmerov [5].

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 [math]\frac{{{a}_{i1}}}{{{a}_{11}}}[/math] , od i-tej rovnice , pre i=2,3, .... n , dostaneme

[math]\begin{align} & {{a}_{11}}{{x}_{1}}+{{a}_{12}}{{x}_{2}}+...+{{a}_{1n}}{{x}_{n}}={{b}_{1}} \\ & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\ a_{22}^{\left( 1 \right)}{{x}_{2}}+...+a_{2n}^{\left( 1 \right)}{{x}_{n}}=b_{2}^{\left( 1 \right)} \\ & \ \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\vdots \\ & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\ a_{n2}^{\left( 1 \right)}{{x}_{2}}+...+a_{nn}^{\left( 1 \right)}{{x}_{n}}=b_{n}^{\left( 1 \right)} \\ \end{align}[/math]

Nové koeficienty vypočítame ako [math]a_{ij}^{(1)}=-\frac{{{a}_{i1}}}{{{a}_{11}}}*{{a}_{1j}}~~~~,~kde~~i=2,3,\ldots ,n~~~~j=2,3,\ldots ,n+1[/math]. Teraz budeme pomocou vhodných násobkov druhej rovnice eliminovať [math]x_2[/math] v tretej, štvrtej a n-tej rovnici. Opäť ak je [math]a_{22}=0[/math], vymeníme druhú rovnicu s prvou z ďalších rovníc, v ktorej [math]x_2[/math] je nenulová. Touto úpravou dostávame:

[math]\begin{align} & {{a}_{11}}{{x}_{1}}+{{a}_{12}}{{x}_{2}}+{{a}_{13}}{{x}_{3}}+...+{{a}_{1n}}{{x}_{n}}={{b}_{1}} \\ & \,\,\,\,\,\,\,\,\,\,\,\,\,\ a_{22}^{\left( 1 \right)}{{x}_{2}}+{{a}_{23}}{{x}_{3}}+...+a_{2n}^{\left( 1 \right)}{{x}_{n}}=b_{2}^{\left( 1 \right)} \\ & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,a_{33}^{\left( 2 \right)}{{x}_{3}}+...+a_{3n}^{\left( 2 \right)}{{x}_{n}}=b_{3}^{\left( 2 \right)} \\ & \ \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\vdots \\ & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,a_{n3}^{\left( 2 \right)}{{x}_{2}}+...+a_{nn}^{\left( 2 \right)}{{x}_{n}}=b_{n}^{\left( 2 \right)} \\ \end{align}[/math]

kde [math]{{a}_{ij}}^{(2)}={{a}_{ij}}^{(1)}-\frac{a_{i2}^{\left( 1 \right)}}{a_{22}^{\left( 1 \right)}}*{{a}_{ij}}^{(1)}[/math], kde i=3,4,…,n j=3,4,…,n+1.

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

[math]\begin{align} & {{a}_{11}}{{x}_{1}}+{{a}_{12}}{{x}_{2}}+{{a}_{13}}{{x}_{3}}+...+{{a}_{1n}}{{x}_{n}}={{b}_{1}} \\ & \,\,\,\,\,\,\,\,\,\,\,\,\,\ a_{22}^{\left( 1 \right)}{{x}_{2}}+{{a}_{23}}{{x}_{3}}+...+a_{2n}^{\left( 1 \right)}{{x}_{n}}=b_{2}^{\left( 1 \right)} \\ & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,a_{33}^{\left( 2 \right)}{{x}_{3}}+...+a_{3n}^{\left( 2 \right)}{{x}_{n}}=b_{3}^{\left( 2 \right)} \\ & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,a_{nn}^{\left( n-1 \right)}{{x}_{n}}=b_{n}^{\left( n-1 \right)} \\ \end{align}[/math]

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

[math]{{x}_{n}}=\frac{b_{n}^{\left( n-1 \right)}}{a_{nn}^{\left( n-1 \right)}}[/math]

[math]{{x}_{n-1}}=\frac{1}{a_{n-1n-1}^{(n-2)}}*\left( b_{n-1}^{(n-2)}-~a_{n-1n}^{(n-2)}*{{x}_{n}} \right)[/math]

...

[math]{{x}_{1}}=\frac{1}{{{a}_{11}}}*\left( {{b}_{1n+1}}-{{a}_{12}}{{x}_{2}}-{{a}_{13}}{{x}_{3}}-\ldots -{{a}_{1n}}{{x}_{n}} \right)[/math]

Toto sa nazýva spätná substitúcia. Číslo [math]a_{kk}^{(k-1)}[/math] 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 [math]n^3[/math] 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 sa používajú pri niektorých iných metódach [4][5].

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 [math]A=L+D+U[/math] , 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

[math]\begin{align} & D=\left( \begin{matrix} {{a}_{11}} & 0 & ... & 0 \\ 0 & {{a}_{22}} & {} & 0 \\ \vdots & {} & \ddots & \vdots \\ 0 & 0 & ... & {{a}_{nn}} \\ \end{matrix} \right) \\ & L=\left( \begin{matrix} 0 & ... & ... & 0 \\ {{a}_{21}} & 0 & {} & 0 \\ \vdots & \ddots & \ddots & \vdots \\ {{a}_{n1}} & ... & {{a}_{n,n-1}} & 0 \\ \end{matrix} \right) \\ & U=\left( \begin{matrix} 0 & {{a}_{12}} & ... & {{a}_{1n}} \\ \vdots & \ddots & \ddots & \vdots \\ 0 & {} & 0 & {{a}_{n-1,n}} \\ 0 & ... & ... & 0 \\ \end{matrix} \right) \\ \end{align}[/math]

Jacobiho iteračnú metódu definujeme na základe rozkladu   A=M-N , kde M=D a N=-(L+U) a zapisujeme ju v tvare [math]D{{x}_{k+1}}=b-\left( L+U \right){{x}_{k}}[/math].

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

[math]x_{i}^{(k+1)}=\frac{1}{{{a}_{ii}}}\left( {{b}_{i}}-\underset{\begin{matrix} j=1 \\ j\ne i \\ \end{matrix}}{\overset{n}{\mathop \sum }}\,{{a}_{ij}}x_{j}^{(k)} \right)~kde\,~i=1,2,\ldots ,n.[/math]

(2.1)

Analýzou vlastností iteračnej matice [math]T=-{{D}^{(-1)}}(L+U)[/math] možno ukázať , že Jacobiho metóda konverguje , keď A je rýdzo diagonálne dominantná.

Definícia: Hovoríme, že matica [math]~A=\left\{ {{a}_{ij}} \right\}_{i,j=1}^{n}[/math] je rýdzo diagonálne dominantná, ak platí:

[math]\left| {{a}_{ii}} \right|\gt \underset{\begin{matrix} j=1 \\ j\ne i \\ \end{matrix}}{\overset{n}{\mathop \sum }}\,{{a}_{ij~}},~kde~i=1,2,\ldots ,n.[/math]

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

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.

[math]x_{i}^{(k+1)}=\frac{1}{{{a}_{ii}}}\left( {{b}_{i}}-\underset{j=1}{\overset{i-1}{\mathop \sum }}\,{{a}_{ij}}x_{j}^{(k+1)}-\underset{j=i+1}{\overset{n}{\mathop \sum }}\,{{a}_{ij}}x_{j}^{(k)} \right)~kde~i=1,2,\ldots ,n[/math]

(2.2)

V maticovom tvare : [math]\left( D+L \right){{x}_{k+1}}=b-U{{x}_{k}}[/math]

Analýzou vlastností iteračnej matice [math]T=-{{(D+L)}^{-1}}~U[/math] 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í: [math]{{x}^{T}}\cdot A\cdot x\gt 0[/math] .

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