Gaussova eliminační metoda

Z Wikipedie, otevřené encyklopedie

Tento článek z oblasti matematiky potřebuje úpravy. Můžete Wikipedii pomoci tím, že ho vhodně vylepšíte. Inspiraci k vylepšení lze hledat v radách na stránce Vzhled a styl, případně na diskusní stránce článku.

Gaussova eliminační metoda (Gaussova eliminace) je metodou exaktního řešení soustavy lineárních algebraických rovnic.

Gaussovu eliminaci lze také použít pro výpočet inverzní matice nebo pro výpočet determinantu matice (viz Gaussova eliminace v článku Determinant).

Obecně řečeno, Gaussova eliminace představuje řešení problému vyjádřeného pomocí matice převedením dané matice na horní trojúhelníkovou nebo na diagonální matici.

Obsah

1 Řešení soustavy lineárních rovnic
- 1.1 Příklad
- 1.2 Maticový tvar
2 Výpočet inverzní matice
3 Podívejte se také na
4 Externí odkazy
5 Reference

[editovat] Řešení soustavy lineárních rovnic

Obecné zadání problému je následující:

$\sum_{j=1}^n a_{i,j}x_{j} = a_{i,n+1}, \mbox{ pro } i = 1, 2, \ldots{}, n$

Soustavu lineárních algebraických rovnic lze vyjádřit rozšířenou maticí soustavy. Řádkovými (nikoliv sloupcovými) úpravami převádíme tuto matici do tvaru, kdy se pod hlavní diagonálou nachází pouze nuly. Upravená matice pak odpovídá soustavě rovnic, která je ekvivalentní s původní soustavou.

Po těchto úpravách lze obvykle ihned zjistit, zda existují nějaká řešení soustavy. Pokud je hodnost upravené matice (tzn. bez pravé strany) různá od hodnosti upravené rozšířené matice, potom podle Frobeniovy věty soustava nemá žádné řešení. Je-li hodnost upravené matice stejná jako hodnost upravené rozšířené matice, a současně je tato hodnost rovna počtu neznámých soustavy, pak má soustava právě jedno řešení. Pokud je hodnost upravené matice stejná jako hodnost upravené rozšířené matice, avšak menší než počet neznámých soustavy, má soustava nekonečně mnoho řešení, přičemž $n - h$ neznámých, kde $n$ je počet neznámých a $h$ je hodnost upravené matice, zvolíme libovolně a ostatní jsou touto volbou jednoznačně určeny.

[editovat] Příklad

Máme soustavu rovnic:

 8x -  y - 2z =  0
- x + 7y -  z = 10
-2x -  y + 9z = 23

a hledáme čísla x, y, z, která jsou řešením dané soustavy.

Cílem je eliminovat jednotlivé neznámé z jednotlivých rovnic soustavy: z první rovnice eliminujeme x (pomocí úprav druhé a třetí rovnice), z druhé y, z třetí z.

Jsou povoleny následující operace, které nezmění hodnost soustavy:

násobení či dělení jednotlivých řádků nenulovým číslem
prohazování libovolných řádků soustavy
přičítání násobků jednotlivých řádků k jinému řádku

Postup pro výše uvedený příklad:

První krok – eliminace x z druhého a třetího řádku.

první řádek neupravujeme
druhý řádek násobíme 8 a přičteme první řádek
třetí řádek násobíme 4 a přičteme první řádek

 8x - y -  2z =  0
    55y - 10z = 80
    -5y + 34z = 92

Druhý krok – eliminace y ze třetího řádku

první řádek neupravujeme
druhý řádek neupravujeme
třetí řádek násobíme 11 a přičteme druhý řádek
vydělíme třetí řádek 364 a získáme řešení z = 3

 8x - y -  2z =  0
    55y - 10z = 80
            z =  3

Třetí krok – zpětné dosazení

v druhém řádku dosadíme za z a vyřešíme y
v prvním řádku dosadíme za z a y a dořešíme x

x = 1
y = 2
z = 3

[editovat] Maticový tvar

Maticové řešení je často přehlednější a tento tvar je též vhodný k algoritmizaci.

Do matice zapisujeme koeficienty následujícím způsobem - levá strana (matice $n \times n$ ) koeficienty od neznámých, pravý sloupec obsahuje vektor pravých stran - výsledná matice $(n+1) \times n$ se nazývá rozšířená matice soustavy lineárních rovnic.

Zadání:

$\begin{pmatrix} 8 & -1 & -2 & 0 \\ -1 & 7 & -1 & 10 \\ -2 & -1 & 9 & 23 \end{pmatrix}$

Po prvním kroku:
$\begin{pmatrix} 8 & -1 & -2 & 0 \\ 0 & 55 & -10 & 80 \\ 0 & -5 & 34 & 92 \end{pmatrix}$

Po druhém kroku:
$\begin{pmatrix} 8 & -1 & -2 & 0 \\ 0 & 55 & -10 & 80 \\ 0 & 0 & 1 & 3 \end{pmatrix}$

Po třetím kroku:
Získáváme diagonální matici pro koeficienty s hodnotami pro neznámé v posledním sloupci:

$\begin{pmatrix} 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 2 \\ 0 & 0 & 1 & 3 \end{pmatrix}$

[editovat] Výpočet inverzní matice

Viz také Výpočet inverzní matice a Příklad v článku Inverzní matice.

Gaussovou eliminací lze také použít pro výpočet inverzní matice A^-1 k dané čtvercové matici A o velikosti (n × n) podle následujícího postupu.

Sestavíme matici B o rozměru (n × 2n) složenou z původní matice A a jednotkové matice I_n. (Odborně řečeno, řešíme současně n pravých stran tvořených bázovými vektory.)

$\bold B = \begin{pmatrix} \bold A & \Big| & \bold I_n \end{pmatrix} = \begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1n} & \Big| & 1 & 0 & \cdots & 0 \\ a_{21} & a_{22} & \cdots & a_{2n} & \Big| & 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots & \Big| & \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nn} & \Big| & 0 & 0 & \cdots & 1 \end{pmatrix}$

Povolenými řádkovými úpravami (záměna řádků, vynasobení řádku skalárem, přičtení jednoho řádku k jinému) převedeme matici B do tvaru, kdy jednotková matice I_n bude vlevo. V takovém případě bude inverzní matice A^-1 v pravé polovině upravené matice.

$\begin{pmatrix} \bold I_n & \Big| & \bold A^{-1} \end{pmatrix}$