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:

Súbor:Untitled 1 html 51683075.png , Súbor:Untitled 1 html m3491dee3.png kde D je determinant matice sústavy A a Súbor:Untitled 1 html 18d6a5a7.png 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

A-1 pre ktorú platí: Súbor:Untitled 1 html 5e10b471.png .

Potom platí Súbor:Untitled 1 html m18a5a089.png.

Potom z jednoznačnosti riešenia dostávame, že Súbor:Untitled 1 html 2884beac.png. Toto vyjadrenie riešenia sme dostali, tak že sme obe strany rovnosti Súbor:Untitled 1 html 3640367f.pngzľava vynásobili maticou Súbor:Untitled 1 html m7e0b28e3.png . 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 Súbor:Untitled 1 html 45c9b1ff.png , od i-tej rovnice , pre i=2,3, .... n , dostaneme

a11 x1 + a12 x2 + ··· + a1n xn = b1 a22 x2 + ··· + a2n xn = b2

an2 x2 + ··· + ann xn = bn

Horný index naznačuje, že sme ukončili prvý krok eliminácie.

Nové koeficienty vypočítame akoSúbor:Untitled 1 html m66602679.png Teraz budeme pomocou vhodných násobkov druhej rovnice eliminovať x2 v tretej, štvrtej a n-tej rovnici. Opäť ak je a22=0, vymeníme druhú rovnicu s prvou z ďalších rovníc, v ktorej x2 je nenulová. Touto úpravou dostávame:

a11 x1 + a12 x2 + a13 x3 ··· + a1n xn = b1

a22 x2 + a23 x3 + ··· + a2n xn = b2

a33 x3 + ··· + a3n xn = b3

an3 x3+ ··· + ann xn = bn

kde Súbor:Untitled 1 html m64a5d78.png

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

a11 x1 + a12 x2 + a13 x3 ··· + a1n xn = b1

a22 x2 + a23 x3 + ··· + a2n xn = b2

a33 x3 + ··· + a3n xn = b3 ann xn = bn

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

Súbor:Untitled 1 html m16d60ed1.png

Súbor:Untitled 1 html 7d21c7ec.png

Súbor:Untitled 1 html 376a8cc5.png

Toto sa nazýva spätná substitúcia. Číslo Súbor:Untitled 1 html 62fe2ece.png 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 n3 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 Súbor:Untitled 1 html m62e15c23.png , 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

Jacobiho iteračnú metódu definujeme na základe rozkladu  Súbor:Untitled 1 html 2d246193.png , kde Súbor:Untitled 1 html 61ae277a.png a Súbor:Untitled 1 html m428e7dc2.png a zapisujeme ju v tvare Súbor:Untitled 1 html 4b590df3.png.

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

Súbor:Untitled 1 html m1dd89cf1.pngAnalýzou vlastností iteračnej matice Súbor:Untitled 1 html m500824df.png možno ukázať , že Jacobiho metóda konverguje , keď A je rýdzo diagonálne dominantná.

Definícia: Hovoríme, že maticaSúbor:Untitled 1 html m1fd48037.png je rýdzo diagonálne dominantná, ak

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.

V maticovom tvare : Súbor:Untitled 1 html m136f2e51.png

Analýzou vlastností iteračnej matice Súbor:Untitled 1 html m3f9eccb1.png 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í: Súbor:Untitled 1 html m40da36b.png .

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