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.	Metódy riešenia veľkých sústav lineárnych rovníc

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 <nowiki>sa používajú pri niektorých iných metódach [4][5].