Klasické metódy riešenia sústav lineárnych rovníc: Rozdiel medzi revíziami
| (3 medziľahlé úpravy od jedného ďalšieho používateľa nie sú zobrazené) | |||
| Riadok 2: | Riadok 2: | ||
[[Kategória:Ročníkové práce]] | [[Kategória:Ročníkové práce]] | ||
[[Kategória:Matematika]] | [[Kategória:Matematika]] | ||
| − | {{Praca_uvod|2|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| | + | {{Praca_uvod|2|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|Priame metódy pre riešenie veľkých sústav rovníc|Moderné metódy riešenia veľkých sústav rovníc|Softvérové balíky pre riešenie veľkých lineárnych systémov|}} |
__TOC__ | __TOC__ | ||
= = | = = | ||
| Riadok 13: | Riadok 13: | ||
=== Cramerovo pravidlo === | === 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: | 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. | |
| − | |||
| Riadok 20: | Riadok 19: | ||
Uvažujme sústavu (1.1) . Keďže je matica sústavy regulárna, existuje k nej inverzná matica | Uvažujme sústavu (1.1) . Keďže je matica sústavy regulárna, existuje k nej inverzná matica | ||
| − | A-1 pre ktorú platí: | + | <math>A^{-1}</math> pre ktorú platí: <math>{{A}^{-1}}A=A{{A}^{-1}}=I</math>. |
| − | |||
| − | Potom z jednoznačnosti riešenia dostávame, že | + | 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) === | === 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). | 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 | + | 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 | ||
| − | < | + | {{vzorec|<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|>\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. | |
| + | {{vzorec|<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>0</math> . | ||
| − | + | Gauss-seidelova metóda konverguje rýchlejšie, a vyžaduje približne polovicu iterácií oproti Jacobiho metóde [7]. | |
Aktuálna revízia z 21:17, 30. júl 2010
Obsah
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].
