Gaussova eliminační metoda

gauss.php

Gaussovou eliminační metodou lze velice jednoduše a rychle řešit soustavu n rovnic o n neznámých. Hlavní myšlenkou metody je postupné odčítání rovnic násobené různými koeficienty až dojde v jedné z rovnic k eliminaci všech neznámých kromě jedné, jejíž hodnotu poté snadno určíme. Obdobně pak vypočítáme i hodnoty ostatních.

Výpočet můžeme rozdělit na dvě fáze, tzv. přímý a zpětný chod. V přímém chodu postupně násobíme každou rovnicí všechny následující takovým koeficientem, aby v nich právě jedna neznámá byla eliminována. Ukažme si příklad:

I)x + 4y - z= 6
II)2x + 3y + z = 2
III)3x + 7y + 2z = 18

Vynásobíme tedy rovnici I) číslem 2 a odečteme ji od rovnice II), a následně číslem 3 a odečteme od III), abychom v obou eliminovali x. Soustava bude vypadat takto:

I)x + 4y - z = 6
II)2x + 3y + z -2*(x + 4y - z - 6) = 2
III)3x + 7y + 2z -3*(x + 4y - z - 6) = 18

po úpravě:

I)x + 4y - z = 6
II) -5y + 3z  = -10
III) - 5y + 5z = 0

Poté rovnici II) odečteme od rovnice III), abychom eliminovali y:

I)x + 4y - z = 6
II) -5y + 3z = -10
III) 2z = 10

Tomuto tvaru soustavy se říká trojúhelníkovitý tvar (podle vizuální podobnosti s trojúhelníkem). V tuto chvíli můžeme přejít do tzv. zpětného chodu, kde budeme již přímo určovat hodnoty proměnných. Ze soustavy, ve které zůstala pouze jedna proměnná přímo určíme její hodnotu, kterou dosadíme do všech ostatních rovnic, tedy o 1 snížíme počet proměnných v každé rovnici. Opět zůstane jedna rovnice, ve které bude pouze jedna proměnná - postupujeme tedy analogicky až do postupného zjištění hodnot všech.

Na první pohled je vidět že v naší soustavě je z rovno 5. Po dosazení soustava vypadá takto:

I)x + 4y = 11
II)-5y = -25
III)z = 5

vidíme že y je 5, a následným dosazením i že x=-9.

Ovšem ne každá rovnice je takto jednoduchá. Konkrétně při počítání Gaussovou musíme počítat s tzv. singulárními soustavami. Za singulární soustavu považujeme takovou, která buď řešení nemá, nebo jich má nekonečně mnoho. V našem případě ji rozeznáme ve chvíli kdy při eliminaci jedné proměnné eliminujeme zároveň i nějakou další ze všech ostatních. Toto je dost kritický problém, protože při zpětném chodu nebude možnost získat hodnotu oněch dvou proměnných které byly eliminovány najednou. Pokud eliminujeme více proměnných pouze z některých rovnic, lze problém řešit prohozením pořadí jednotlivých rovnic tak, aby vždy došlo k eliminaci právě jedné proměnné (taková soustava tedy singulární není). Opět ukázka:

I)x + y + z + w = 1
II)2x + 2y + 3z + w = 3
III)2x + 4y + 4z + w = 4
IV)2x + 5y + 5z + w = 5

Pokud bychom se pokusili násobit I) dvojkou a následně odečíst od II),III),IV), dostali bychom se do tohoto stavu:

I)x + y + z + w = 1
II)z - w = 1
III)2y + 2z - w = 2
IV)3y + 3z - w = 3

Zachrání nás prohození II) a IV), a následná eliminace y z III) pomocí současné II). Poté už lze soustavu snadno převést na žádaný trojúhelníkový tvar (toto by pravděpodobně intuitivně napadlo každého, zmínil jsem to pouze proto, že při počítačové implementaci je na to třeba pamatovat aby nedošlo k smrtícímu dělení nulou).

Příklady

Spočítejte hodnoty proměnných x, y, z v následující rovnici.

...

...

...

...

...

...

...

...