Gaussova eliminační metoda

Gaussova eliminační metoda jednoduše Gaussova eliminace^[1] je v lineární algebře numerická metoda řešení soustav lineárních algebraických rovnic pojmenovaná po Carlu Friedrichu Gaussovi (1777–1855). Jedná se o postup vedoucí k přesnému řešení soustavy v konečně mnoha krocích. Metoda je založena na skutečnosti, že elementární ekvivalentní úpravy mění soustavu rovnic, ale zachovávají množinu řešení. Vhodnou volbou elementárních úprav lze každou rozšířenou matici soustavy převést do odstupňovaného tvaru, ze kterého lze zpětnou substitucí snadno určit množinu všech řešení i její dimenzi. Zahrnutí zpětné substituce do algoritmu vede ke Gaussově–Jordanově eliminaci, pojmenovanou navíc po německém geodetu Wilhelmu Jordanovi (1842-1899), jež pro danou matici určí jednoznačný redukovaný odstupňovaný tvar.

Na čtvercových maticích řádu $n$ metoda vyžaduje asymptoticky $n^{3}$ aritmetických operací. Algoritmus je v základní podobě náchylný na zaokrouhlovací chyby, ale s malými úpravami, tzv. pivotací, představuje standardní metodu řešení obecných soustav lineárních rovnic. Je také součástí všech hlavních programových knihoven pro numerickou lineární algebru, jako je NAG, IMSL a LAPACK .

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

Definice

Elementární ekvivalentní úpravy

Existují tři druh základních řádkových úprav, které lze provádět na rovnicích soustavy, resp. řádcích odpovídající matice:

Záměna pozice dvou rovnic soustavy / řádků matice.
Vynásobení rovnice soustavy / řádku matice nenulovým skalárem .
Přičtení k jedné rovnici / jednomu řádku matice skalární násobek jiné rovnice / jiného řádku.

Uvedené operace nemění množinu řešení soustavy. Pro usnadnění argumentace lze nejprve ukázat, že první a třetí typ úpravy lze odvodit z vynásobení nenulovým skalárem (druhý typ úprav) a prostého přičtení (třetí typ, kde je přičten jen 1-násobek).

Odstupňovaný tvar matice. Pivoty jsou zvýrazněny červeně. Modře jsou nulové prvky před pivoty. Podbarvené části mají svým tvarem připomínat stupně schodiště.

Odstupňovaný tvar matice

Pokud se řádek matice neskládá pouze z nul, pak se první nenulová položka nazývá vedoucí koeficient stručně pivot tohoto řádku. Pokud každý nenulový řádek má svůj pivot více vpravo, než je pozice pivotu o řádek výše (s výjimkou prvního řádku, kde tato podmínka nemá smysl) a všechny nulové řádky jsou až pod nenulovými, pak se říká, že matice je v (řádkově) odstupňovaném tvaru. Slovo "odstupňovaný" naznačuje, že část matice obsahující nulové prvky před pivoty se podobá stupňům schodiště při pohledu z boku (a podobně i část matice nad ní).

Formálně, matice ${\boldsymbol {A}}$ typu $m\times n$ je v odstupňovaném tvaru, pokud existují $r\in \{0,1,\dots ,m\}$ a rostoucí posloupnost přirozených čísel $1\leq j_{1}<j_{2}<\cdots <j_{r}\leq n$ takové, že:

a_{ij}\ {\begin{cases}=0&{\text{pro }}i<j_{i}{\text{ a }}i\leq r\\\neq 0&{\text{pro }}j=j_{i}{\text{ a }}i\leq r\\=0&{\text{pro }}i>r\\\end{cases}}

Pivotem je prvek na pozici $a_{i,j_{i}}$ pro každé $i\in \{1,\dots ,r\}$ . Číslo $r$ je hodnost matice ${\boldsymbol {A}}$ .

Odstupňovaná tvar odpovídá soustavě, jejíž netriviální rovnice (t.j. v nichž alespoň jedna strana je nenulová) lze seřadit tak, že indexy prvních neznámých ve dvou po sobě jdoucích rovnicích rostou. Jinými slovy neznámé druhé rovnice začínají vyšším indexem než neznámé první rovnice atd.

Gaussova eliminace

Nachází-li se dva pivoty různých řádků ve stejném sloupci, pak lze použít řádkovou operaci typu 3, aby se jeden z těchto koeficientů stal nulovým. V řeči rovnic je proměnná odpovídající sloupci s pivotem vyjádřena z jedné z těchto dvou rovnic a dosazena do druhé, čímž je z ní eliminována. Řádky matice lze průběžně třídit tak, aby každý nenulový řádek měl svůj pivot ve stejném sloupci nebo více vpravo, než je pivot o řádek výše a všechny nulové řádky byly až pod nenulovými. Uvedený postup opakujeme tak dlouho, dokud lze nalézt dva pivoty ve stejném sloupci.

V každém kroku se pivot jednoho z řádků posune doprava nebo je řádek zcela vynulován, neboli vzroste celkový počet nul před pivoty a v nulových řádcích. Algoritmus je proto konečný. Po ukončení algoritmu nelze mít dva pivoty ve stejném sloupci, a proto je výsledná matice v odstupňovaném tvaru.

Ukázky

Předpokládejme, že cílem je najít a popsat množinu řešení následující soustavy lineárních rovnic:

{\begin{alignedat}{4}2x_{1}&{}+{}&x_{2}&{}-{}&x_{3}&{}={}&8\\-3x_{1}&{}-{}&x_{2}&{}+{}&2x_{3}&{}={}&-11\\-2x_{1}&{}+{}&x_{2}&{}+{}&2x_{3}&{}={}&-3\end{alignedat}}

V tabulce je předveden postup Gaussovy eliminace současně na rozšířené matici soustavy i na soustavě rovnic samotné.

Rozšířená matice soustavy	Soustava rovnic
$\left({\begin{array}{rrr\|r}2&1&-1&8\\-3&-1&2&-11\\-2&1&2&-3\end{array}}\right)$	${\begin{alignedat}{4}2x_{1}&{}+{}&x_{2}&{}-{}&x_{3}&{}={}&8&\\-3x_{1}&{}-{}&x_{2}&{}+{}&2x_{3}&{}={}&-11&\\-2x_{1}&{}+{}&x_{2}&{}+{}&2x_{3}&{}={}&-3&\end{alignedat}}$
ke 2. řádku přičteme ${\frac {3}{2}}\times$ 1. řádek ke 3. řádku přičteme 1. řádek	z 1. rovnice vyjádříme $x_{1}={\frac {1}{2}}(8-x_{2}+x_{3})$ a dosadíme je do ostatních dvou
$\left({\begin{array}{rrr\|r}2&1&-1&8\\0&{\frac {1}{2}}&{\frac {1}{2}}&1\\0&2&1&5\end{array}}\right)$	${\begin{alignedat}{4}2x_{1}&{}+{}&x_{2}&{}-{}&x_{3}&{}={}&8&\\&&{\tfrac {1}{2}}x_{2}&{}+{}&{\tfrac {1}{2}}x_{3}&{}={}&1&\\&&2x_{2}&{}+{}&x_{3}&{}={}&5&\end{alignedat}}$
od 3. řádku odečteme $4\times$ 2. řádek	ze 2. rovnice vyjádříme $x_{2}=2-x_{3}$ a dosadíme je do 3. rovnice
$\left({\begin{array}{rrr\|r}2&1&-1&8\\0&{\frac {1}{2}}&{\frac {1}{2}}&1\\0&0&-1&1\end{array}}\right)$	${\begin{alignedat}{4}2x_{1}&{}+{}&x_{2}&{}-{}&x_{3}&{}={}&8&\\&&{\tfrac {1}{2}}x_{2}&{}+{}&{\tfrac {1}{2}}x_{3}&{}={}&1&\\&&&&-x_{3}&{}={}&1&\end{alignedat}}$
Matice je v odstupňovaném tvaru	Indexy prvních neznámých rostou

Může se stát, že při eliminaci vznikne nulový řádek, anebo že některé sloupce odpovídající neznámým (t.j. na levé straně) neobsahují pivot:

\left({\begin{array}{rrr|r}1&3&1&9\\1&1&-1&1\\3&11&5&35\end{array}}\right)\to \left({\begin{array}{rrr|r}1&3&1&9\\0&-2&-2&-8\\0&2&2&8\end{array}}\right)\to \left({\begin{array}{rrr|r}1&3&1&9\\0&-2&-2&-8\\0&0&0&0\end{array}}\right)

Kontrolní součty

Správnost výpočtu lze částečně ověřit pomocí řádkových součtů, zapisovaných jako dodatečný sloupec matice. Například v ukázce

$\left({\begin{array}{rrr|r|r}2&1&-1&8&10\\-3&-1&2&-11&-13\\-2&1&2&-3&-2\end{array}}\right)\to \left({\begin{array}{rrr|r|@{1pt}|r}2&1&-1&8&10\\0&{\frac {1}{2}}&{\frac {1}{2}}&1&2\\0&2&1&5&8\end{array}}\right)$

odpovídá hodnota 10 v pravém horním rohu součtu hodnot v prvním řádku $2+1-1+8=10$ . Provedení obou elementárních úprav na celé řádky zachovává i řádkové součty. Např. 8 v pravém dolním rohu odpovídá úpravě přičtení prvního řádku ke třetímu $-2+10=8$ a zároveň má odpovídat řádkovému součtu $2+1+5=8$ . Uvedená kontrola je schopna odhalit jednu numerickou chybu v každé elementární úpravě.

Zpětná substituce

Má-li výsledná matice pivot v posledním sloupci, potom podle Frobeniovy věty soustava nemá žádné řešení, protože je nemá ani odpovídající rovnice:

0x_{1}+\cdots +0x_{n}=b\neq 0

V opačném případě má soustava alespoň jedno řešení. Řešení je jednoznačné, pokud každý sloupec odpovídající neznámé proměnné obsahuje pivot. Pak lze postupně odvozovat hodnoty proměnných odpovídajících pivotům, nazývané bázické nebo též závislé proměnné, počínaje poslední rovnicí a dosazovat je do předchozích rovnic. Soustava může obsahovat i proměnné odpovídající sloupcům bez pivotů, ty se pak nazývají volné. Platí, že pro libovolnou volbu volných proměnných lze odvodit jednoznačně hodnoty bázických proměnných, tak aby společně tvořily řešení soustavy.

Gaussova–Jordanova eliminace

Gaussova–Jordanova eliminace navazuje na Gaussovu eliminaci v tom smyslu, že postup zpětné substituce je proveden na rozšířené matici soustavy pomocí elementárních úprav. Nenulové řádky jsou vyděleny hodnotou pivotu (čili vynásobeny jeho převrácenou hodnotou), aby byl každý pivot roven jedné. Počínaje posledním pivotem jsou pomocí pivotů eliminovány nenulové prvky nad nimi.

Redukovaný odstupňovaný tvar matice. Pivoty jsou znormalizovány na 1. Hnědě zabarvené prvky nad pivoty jsou zredukovány na 0.

Redukovaný odstupňovaný tvar matice

Matice získaná Gaussovou–Jordanovou eliminací je v tzv. redukovaném odstupňovaném tvaru.

Formálně, matice ${\boldsymbol {A}}$ typu $m\times n$ je v redukovaném odstupňovaném tvaru, pokud existují $r\in \{0,1,\dots ,m\}$ a rostoucí posloupnost přirozených čísel $1\leq j_{1}<j_{2}<\cdots <j_{r}\leq n$ takové, že:

a_{ij}={\begin{cases}0&{\text{pro }}i<j_{i}{\text{ a }}i\leq r\\1&{\text{pro }}j=j_{i}{\text{ a }}i\leq r\\0&{\text{pro }}j=j_{k}\in \{j_{1},\dots ,j_{r}\}{\text{ a }}i<k\\0&{\text{pro }}i>r\\\end{cases}}

Lze dokázat, že pro každou matici je její redukovaný odstupňovaný tvar jednoznačně dán.

Ukázky

V následující tabulce je předvedeno dokončení Gaussovy–Jordanovy eliminace i zpětná substituce pro soustavu z první ukázky.

Rozšířená matice soustavy	Soustava rovnic
$\left({\begin{array}{rrr\|r}2&1&-1&8\\0&{\frac {1}{2}}&{\frac {1}{2}}&1\\0&0&-1&1\end{array}}\right)$	${\begin{alignedat}{4}2x_{1}&{}+{}&x_{2}&{}-{}&x_{3}&{}={}&8&\\&&{\tfrac {1}{2}}x_{2}&{}+{}&{\tfrac {1}{2}}x_{3}&{}={}&1&\\&&&&-x_{3}&{}={}&1&\end{alignedat}}$
3. řádek vydělíme -1	ze 3. rovnice odvodíme $x_{3}=-1$
$\left({\begin{array}{rrr\|r}2&1&-1&8\\0&{\frac {1}{2}}&{\frac {1}{2}}&1\\0&0&1&-1\end{array}}\right)$	${\begin{alignedat}{4}2x_{1}&{}+{}&x_{2}&{}-{}&x_{3}&{}={}&8&\\&&{\tfrac {1}{2}}x_{2}&{}+{}&{\tfrac {1}{2}}x_{3}&{}={}&1&\\&&&&x_{3}&{}={}&-1&\end{alignedat}}$
k 1. řádku přičteme 3. od 2. řádku odečteme ${\tfrac {1}{2}}\times$ 3. řádek	dosadíme $x_{3}$ do předchozích rovnic
$\left({\begin{array}{rrr\|r}2&1&0&7\\0&{\frac {1}{2}}&0&{\frac {3}{2}}\\0&0&1&-1\end{array}}\right)$	${\begin{alignedat}{4}2x_{1}&{}+{}&x_{2}&&&{}={}&7&\\&&{\tfrac {1}{2}}x_{2}&&&{}={}&{\tfrac {3}{2}}&\\&&&\quad &x_{3}&{}={}&-1&\end{alignedat}}$
2. řádek vynásobíme 2	ze 2. rovnice odvodíme $x_{2}=3$
$\left({\begin{array}{rrr\|r}2&1&0&7\\0&1&0&3\\0&0&1&-1\end{array}}\right)$	${\begin{alignedat}{4}2x_{1}&{}+{}&x_{2}&&&{}={}&7&\\&&x_{2}&\quad &&{}={}&3&\\&&&&x_{3}&{}={}&-1&\end{alignedat}}$
od 1. řádku odečteme 2.	dosadíme $x_{2}$ do 1. rovnice
$\left({\begin{array}{rrr\|r}2&0&0&4\\0&1&0&3\\0&0&1&-1\end{array}}\right)$	${\begin{alignedat}{4}2x_{1}&\quad &&&&{}={}&4&\\&&x_{2}&\quad &&{}={}&3&\\&&&\quad &x_{3}&{}={}&-1&\end{alignedat}}$
1. řádek vydělíme 2	z 1. rovnice odvodíme $x_{1}=2$
$\left({\begin{array}{rrr\|r}1&0&0&2\\0&1&0&3\\0&0&1&-1\end{array}}\right)$	${\begin{alignedat}{4}x_{1}&\quad &&&&{}={}&2&\\&&x_{2}&\quad &&{}={}&3&\\&&&\quad &x_{3}&{}={}&-1&\end{alignedat}}$
Matice je v redukovaném odstupňovaném tvaru.	Rovnice vyjadřují hodnoty neznámých odpovídajících sloupcům s pivoty.

Ve druhé ukázce s rozšířenou maticí

\left({\begin{array}{rrr|r}1&3&1&9\\0&-2&-2&-8\\0&0&0&0\end{array}}\right)

je poslední rovnice $0x_{1}+0x_{2}+0x_{3}=0$ vždy splněna a neovlivňuje množinu řešení. Neznámá $x_{3}$ odpovídá sloupci bez pivotu, a je proto volná. Z druhé rovnice lze vyjádřit $x_{2}$ v závislosti na $x_{3}$ , konkrétně z rovnice $-2x_{2}-2x_{3}=-8$ vyplývá, že $x_{2}=4-x_{3}$ . Dosazení $x_{2}$ do první rovnice dává rovnici $x_{1}+3(4-x_{3})+x_{3}=9$ . Z ní lze vyjádřit $x_{1}=2x_{3}-3$ .

Stejný postup zapsaný pomocí matic dává redukovaný odstupňovaný tvar:

\left({\begin{array}{rrr|r}1&3&1&9\\0&-2&-2&-8\\0&0&0&0\end{array}}\right)\to \left({\begin{array}{rrr|r}1&3&1&9\\0&1&1&4\\0&0&0&0\end{array}}\right)\to \left({\begin{array}{rrr|r}1&0&-2&-3\\0&1&1&4\\0&0&0&0\end{array}}\right)

Pivotace

Pivotace je proces, kterým lze ovlivnit průběh Gaussovy eliminace. Pro eliminaci může být v některých případech nezbytné provést výměnu řádků, jako například v následující ukázce, která se od předchozí liší pouze nahrazením $a_{11}=1$ za $a_{11}=0$ . Algoritmus je třeba začít tříděním podle pozice pivotů, přičemž za pivot, který zůstane v prvním sloupci zachován, lze zvolit libovolný nenulový prvek z prvního sloupce matice.

Volba pivotu
$x_{1}$	$x_{2}$	$x_{3}$	$b$
0	1	-1	8
-3	-1	2	-11
-2	1	2	-3

Přerovnání řádků
$x_{1}$	$x_{2}$	$x_{3}$	$b$
-3	-1	2	-11
-2	1	2	-3
0	1	-1	8

Při ručním výpočtu je užitečné zvolit za pivot 1 nebo -1, aby nebylo nutné dělit. Při výpočtu na počítači je pro numerickou stabilitu algoritmu obvykle vybírán prvek s největší absolutní hodnotou. Výběr pivotu z aktuálního sloupce se nazývá sloupcová pivotace. Podobně lze pivotovat i v rámci aktuálního řádku matice.

Volba pivotu
$x_{1}$	$x_{2}$	$x_{3}$	$b$
0	1	-1	8
-3	-1	2	-11
-2	1	2	-3

V tomto případě jsou odpovídajícím způsobem přerovnány sloupce matice.

Přerovnání sloupců
$x_{2}$	$x_{1}$	$x_{3}$	$b$
1	0	-1	8
-1	-3	2	-11
1	-2	2	-3

Při zpětné substituci si je třeba si uvědomit, že proměnné změnily svou pozici v soustavě rovnic. Pro usnadnění manipulací s řádky a sloupci matice se využívají vektory indexů, které uchovávají informace o prováděných výměnách. Tímto způsobem lze efektivně aplikovat pivotaci bez nutnosti fyzických operací s maticemi.

V metodě nazývané úplná pivotace se za pivot volí prvek s největší absolutní hodnotou z celé matice. Tento přístup využívá přerovnání řádků i sloupců zároveň.

Vlastnosti

Všechny uvedené výpočty lze provádět na maticích jejich prvky patří do libovolného komutativního tělesa, čili nejenom na reálných maticích jako v uvedených ukázkách či na komplexních maticích.

LU rozklad

Průběh Gaussovy eliminace poskytuje také tzv. LU rozklad původní matice, což může být užitečné pro studium matic a analýzu algoritmu. Elementární řádkové úpravy mohou být interpretovány tak, že původní matice je násobena zleva elementárními maticemi. Alternativně lze na posloupnost elementárních operací, které upravují jeden řádek, pohlížet jako na součin s Frobeniovou maticí zleva.

Úvodní ukázka

Je-li třeba vyřešit soustavu ${\boldsymbol {Ax}}={\boldsymbol {b}}$ s regulární maticí ${\boldsymbol {A}}$ , je možné Gaussovu eliminaci v počítači implementovat jako LU rozklad (také nazývaný LU faktorizace nebo LR rozklad nebo trojúhelníkový rozklad ). Jedná se o rozklad regulární matice ${\boldsymbol {A}}$ na součin levé dolní, normalizované trojúhelníkové matice ${\boldsymbol {L}}$ (angl. „left“ nebo „lower“) a pravou horní trojúhelníkovou matici ${\boldsymbol {U}}$ (z angl. „upper“ - horní, též angl. „right“ pak bývá značena ${\boldsymbol {R}}$ ). Rozklad ilustruje následující ukázka:

{\boldsymbol {A}}={\begin{pmatrix}1&2&3\\1&1&1\\3&3&1\\\end{pmatrix}}={\begin{pmatrix}1&0&0\\1&1&0\\3&3&1\\\end{pmatrix}}\cdot {\begin{pmatrix}1&2&3\\0&-1&-2\\0&0&-2\\\end{pmatrix}}={\boldsymbol {LU}}

Matice ${\boldsymbol {L}}$ zaznamenává provedené úpravy, neboť tyto odpovídají součinům s Frobeniovými maticemi, a ${\boldsymbol {U}}$ je v odstupňovaném tvaru. Diagonální prvky matice ${\boldsymbol {L}}$ jsou zpravidla normalizovány na 1. Zapamatování úprav prostřednictvím matice ${\boldsymbol {L}}$ má tu výhodu, že soustavy rovnic ${\boldsymbol {Ax}}={\boldsymbol {b}}$ , které se liší jen pravými stranami ${\boldsymbol {b}}$ , lze po jednom provedení rozkladu matice ${\boldsymbol {A}}$ už efektivně řešit jen dvojicí zpětných substitucí závisejících jen na vektoru ${\boldsymbol {b}}$ .

Je-li nevyhnutelné provádět i přerovnání řádků, lze je v rozkladu interpretovat pomocí permutační matice ${\boldsymbol {P}}$ :

{\boldsymbol {PA}}={\boldsymbol {LU}}

Permutační matice ${\boldsymbol {P}}$ je matice, která je vytvořena z jednotkové matice libovolným přerovnáním jejích řádků.

Věta o existenci

Pro jakoukoli čtvercovou matici ${\boldsymbol {A}}$ existují permutační matice ${\boldsymbol {P}}$ , čtvercová dolní normalizovaná trojúhelníková matice ${\boldsymbol {L}}$ a čtvercová horní trojúhelníková matice ${\boldsymbol {U}}$ , všechny stejného řádu jako ${\boldsymbol {A}}$ , splňující:

{\boldsymbol {PA}}={\boldsymbol {LU}}

.

Neúplné rozklady

LU faktorizace nebývá efektivní v tom smyslu, že rozklad řídké matice obvykle nedává řídké matice ${\boldsymbol {L}}$ a ${\boldsymbol {U}}$ . Pokud se namísto všech nenulových prvků matic ${\boldsymbol {L}}$ a ${\boldsymbol {U}}$ vezmou v potaz jen některé, dává výsledný součin ${\boldsymbol {LU}}$ aproximaci matice ${\boldsymbol {A}}$ a nazývá se neúplný LU rozklad. U symetrických pozitivně semidefinitních matic se hovoří o neúplném Choleského rozkladu a tyto rozklady se používají v iterativních přibližných metodách.

Zobecnění

Buchbergerův algoritmus je zobecněním Gaussovy eliminace na soustavy polynomiálních rovnic. Toto zobecnění do značné míry závisí na uspořádání monických polynomů. Volba pořadí proměnných je implicitně obsažena již v Gaussově eliminaci a projevuje se jako volba postupu zleva doprava při výběru polohy pivotů.

Vypočítat hodnost tenzoru řádu většího než 2 je NP-těžké. Pokud tedy $P\neq NP$ , nemůže existovat analogie Gaussovy eliminace v polynomiálním čase pro tenzory vyšších řádů (matice jsou reprezentace tenzorů řádu 2).

Aplikace

Výpočet hodnosti a báze

Odstupňovaný tvar podává řadu informací o výchozí matici ${\boldsymbol {A}}$ . Počet pivotů v odstupňovaném tvaru je roven hodnosti matice ${\boldsymbol {A}}$ . Řádky s pivoty jsou lineárně nezávislé a generují řádkový prostor a proto tvoří jeho bázi. Stejný vztah platí pro sloupce s pivoty a sloupcový prostor.

Vše uvedené platí i pro redukovaný odstupňovaný tvar, což je zvláštní případ odstupňovaného tvaru.

Výpočet inverzní matice

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

Gaussovu eliminaci lze použít pro výpočet inverzní matice ${\boldsymbol {A}}^{-1}$ k dané čtvercové matici ${\boldsymbol {A}}$ řádu $n$ podle následujícího postupu.

Z původní matice ${\boldsymbol {A}}$ a jednotkové matice $\mathbf {I} _{n}$ je nejprve sestavena bloková matice typu $n\times 2n$ :

\left({\boldsymbol {A}}\mid \mathbf {I} _{n}\right)=\left({\begin{array}{cccc|cccc}a_{11}&a_{12}&\cdots &a_{1n}&1&0&\cdots &0\\a_{21}&a_{22}&\cdots &a_{2n}&0&1&\cdots &0\\\vdots &\vdots &\ddots &\vdots &\vdots &\vdots &\ddots &\vdots \\a_{n1}&a_{n2}&\cdots &a_{nn}&0&0&\cdots &1\end{array}}\right)

Uvedená matice je Gaussovou–Jordanovou eliminací upravena do tvaru, kdy se vlevo nachází jednotková matice $\mathbf {I} _{n}$ . Inverzní matice ${\boldsymbol {A}}^{-1}$ je pak v pravé polovině výsledné matice $\left(\mathbf {I} _{n}\mid {\boldsymbol {A}}^{-1}\right)$ . Jinými slovy, řešíme současně $n$ lineárních rovnic s maticí soustavy ${\boldsymbol {A}}$ , přičemž za pravé strany postupně dosazujeme vektory přirozené báze.

Pro důkaz korektnosti uvedeného postupu si stačí uvědomit, že každou řádkovou úpravu lze provést součinem s elementární maticí zleva. Nechť ${\boldsymbol {B}}$ značí matici danou součinem všech použitých elementárních matic. Výsledek v levém bloku odpovídá vztahu ${\boldsymbol {BA}}=\mathbf {I} _{n}$ , a proto ${\boldsymbol {B}}={\boldsymbol {A}}^{-1}$ . Pravý blok pak obsahuje součin ${\boldsymbol {B}}\mathbf {I} _{n}={\boldsymbol {B}}$ .

Explicitnímu výpočtu inverzní matice se lze obvykle v praktických aplikacích vyhnout.

Determinant

Gaussova metoda poskytuje efektivní způsob výpočtu determinantu matice ${\boldsymbol {A}}$ řádu $n$ . Při provádění elementárních úprav se determinant mění následovně:

Záměna dvou řádků se změní znaménko determinantu.
Vynásobením řádku nenulovým skalárem se determinant vynásobí stejným skalárem.
Přičtení skalárního násobku řádku k jinému determinant nezmění.

Výsledná matice ${\boldsymbol {B}}$ v odstupňovaném tvaru je horní trojúhelníková a její determinant je roven součinu prvků na diagonále $\prod _{i=1}^{n}b_{ii}$ . Odtud vyplývá, že

\det {\boldsymbol {A}}={\frac {1}{d}}\prod _{i=1}^{n}b_{ii}

,

kde $d$ označuje součin skalárů, kterými byl determinant vynásoben podle výše uvedených pravidel.

Pro matici řádu $n$ tato metoda vyžaduje pouze $O(n^{3})$ aritmetických operací. Pro srovnání, výpočet determinantu podle Leibnizova vzorce vyžaduje $O(n!)$ aritmetických operací (počet sčítanců ve vzorci) a rekurentní výpočet podle Laplaceova rozvoje vyžaduje $O(2^{n})$ operací (počet dílčích determinantů k výpočtu, pokud žádný není počítán dvakrát). Dokonce i na nejrychlejších počítačích jsou tyto dvě metody pro $n$ nad 20 nepraktické nebo ani neproveditelné.

Výpočetní složitost

Počet aritmetických operací potřebných k provedení Gaussovy eliminace je jedním ze způsobů měření efektivity algoritmu. Například k vyřešení soustavy $n$ rovnic o $n$ neznámých převodem na odstupňovaný tvar a následnou zpětnou substitucí je třeba provést $n(n+1)/2$ podílů, $(2n^{3}+3n^{2}-5n)/6$ součinů a $(2n^{3}+3n^{2}-5n)/6$ součtů, což je celkem přibližně $2n^{3}/3$ operací. Časová složitost výpočtu je tudíž $O(n^{3})$ .

Tato složitost je dobrým měřítkem času potřebného pro celý výpočet, jen pokud je čas provedení každé aritmetické operace přibližně konstantní, například když jsou koeficienty soustavy reprezentovány čísly s plovoucí desetinnou čárkou nebo když patří do konečného tělesa. Pokud jsou koeficienty přesně reprezentovány celými čísly nebo racionálními čísly, mohou čísla v mezivýpočtech exponenciálně narůstat, takže bitová složitost je exponenciální. Bareissův algoritmus je varianta Gaussovy eliminace, která se tomuto exponenciálnímu růstu mezivýpočtů vyhýbá a při stejné aritmetické složitosti $O(n^{3})$ má bitovou složitost jen $O(n^{5})$ .

Tento algoritmus lze použít na počítači pro systémy s tisíci rovnic a neznámými. U systémů s miliony rovnic se však cena stává neúnosnou. Tyto velké systémy jsou obecně řešeny pomocí iteračních metod. Ty se přibližují k výsledku řešení krok za krokem a pro matici řádu $n$ vyžadují v každé iteraci obvykle ${\mathcal {O}}(n^{2})$ aritmetických operací. Rychlost konvergence těchto metod do značné míry závisí na vlastnostech matice a je obtížné předpovědět konkrétní požadovaný výpočetní čas.

Specifické metody existují pro soustavy, jejichž koeficienty tvoří v matici nějaký pravidelný vzor (viz soustavy lineárních rovnic ). Například výpočet Choleského rozkladu symetrické pozitivně definitní matice vyžaduje pouze poloviční množství aritmetických operací a paměti. Dalším ukázkou jsou Toeplitzovy matice s pevným počtem nenulových diagonál v okolí hlavní diagonály. Je-li tento počet, nazýván šířka pásma, roven $m$ , pak zde LU rozklad zachovává pásmovou strukturu a tak se snižuje náročnost na ${\mathcal {O}}(nm^{2})$ operací. Pro několik speciálních řídkých matic je možné využít jejich strukturu tak, že LU rozklad také zůstane řídký. Obojí je doprovázeno sníženými paměťovými nároky.

Aby bylo možné čtvercovou matici řádu $n$ převést do redukovaného odstupňovaného tvaru pomocí řádkových úprav, potřebujeme $n^{3}$ aritmetických operací, což je přibližně o polovinu více oproti neredukovanému tvaru.^[2]

Numerické záležitosti

Jedním z možných problémů je numerická nestabilita, způsobená možností dělení velmi malými čísly. Pokud je například pivot některého řádku velmi blízký nule, pak pro eliminaci ostatních řádků matice by bylo nutné dělit tímto číslem. To znamená, že jakákoliv chyba u čísla, které se blížilo nule, bude znásobena. Gaussova eliminace je numericky stabilní pro diagonálně dominantní nebo pozitivně definitní matice. Pro obecné matice je Gaussova eliminace obvykle považována za stabilní při použití částečné pivotace, jak ukázal James H. Wilkinson po druhé světové válce. Existují však příklady matic, u kterých konstanta stability roste exponenciálně s rozměrem matice. Stabilita může být dále zlepšena úplnou pivotací, čímž se ovšem zároveň zvyšují nároky potřebné pro vyhledávání pivotů o ${\mathcal {O}}(n^{3})$ , takže se tento postup používá jen zřídka. QR rozklady mají obecně lepší stabilitu, ale jsou také složitější na výpočet.

Pro striktně diagonální dominantní nebo pozitivně definitní matice (viz také Choleského rozklad) je Gaussova metoda stabilní a lze ji provádět bez pivotace, protože se na diagonále neobjeví žádné nuly.

Pseudokód

Gaussova eliminace transformuje danou matici ${\boldsymbol {A}}$ typu $m\times n$ na matici v řádkově odstupňovaném tvaru.

V následujícím pseudokódu značí symbol A[i, j] prvek dané a pak postupně přetvářené matice ${\boldsymbol {A}}$ v $i$ -tém řádku a $j$ -tém sloupci s indexy začínajícími od 1. Transformace se provádí na místě, což znamená, že původní matice je ztracena, protože byla nakonec nahrazena jejím odstupňovaným tvarem.

Vstup: Matice A

h := 1 /* Inicializace řádku s pivotem */
k := 1 /* Inicializace sloupce s pivotem */

while h ≤ m and k ≤ n
    /* Najdi k-tý pivot: */
    i_max := argmax (i = h ... m, abs(A[i, k]))
    if A[i_max, k] = 0
        /* Ve sloupci není pivot, přejdi na další */
        k := k + 1
    else
        swap rows(h, i_max)
        /* Proveď pro všechny řádky pod pivotem: */
        for i = h + 1 ... m:
            f := A[i, k] / A[h, k]
            /* Vyplň nulami část sloupce pod pvivotem: */
            A[i, k] := 0
            /* Pro všechny zbývající prvky v aktuálním řádku: */
            for j = k + 1 ... n:
                A[i, j] := A[i, j] - A[h, j] * f
        /* Přejdi na další pivot */
        h := h + 1
        k := k + 1

return A

Uvedený pseudokód se mírně liší od výše popsaného algoritmu výběrem pivotu s největší absolutní hodnotou. Tato částečná pivotace může být provedena, má-li matice v místě předpokládaného pivotu nulovou hodnotu. V každém případě volba největší možné absolutní hodnoty pivotu zlepšuje numerickou stabilitu algoritmu, reprezentují-li se reálná čísla pomocí plovoucí desetinné čárky.

Historie

Matematická metoda eliminace, spojená s řešením soustav lineárních rovnic, má historické kořeny v čínské matematické knize Matematika v devíti kapitolách, která vznikla mezi lety 200 př. n. l. a 100 n. l. Tento starověký text obsahoval ilustraci této metody v osmnácti úlohách se dvěma až pěti rovnicemi a také algoritmus pro řešení soustav se třemi neznámými. První zmínka o této knize se datuje do roku 179 př. n. l., přičemž zůstala populární v Číně a okolních zemích až do 16. století. V roce 263 následoval obsáhlý komentář od Liou Chuej, který posléze doplnil obsah této knihy.

V Evropě se metoda Gaussovy eliminace začala objevovat díky poznámkám Isaaca Newtona. V roce 1670 napsal, že všechny jemu známé knihy algebry postrádají lekce o algebraickém řešení soustav rovnic, což sám později doplnil. Cambridgeská univerzita vydala jeho poznámky jako Arithmetica Universalis v roce 1707, dlouho poté, co Newton opustil akademický život. Tyto poznámky byly hojně napodobovány, což způsobilo, že se (dnes nazývaná) Gaussova eliminace stala koncem 18. století standardním učivem v učebnicích algebry. V kontinentální Evropě teprve až v roce 1759 zveřejnil Joseph-Louis Lagrange metodu obsahující základní prvky eliminace.

Carl Friedrich Gauss se v rámci rozvoje a aplikace metody nejmenších čtverců zabýval soustavami lineárních rovnic a normálními rovnicemi, které se zde vyskytují. Jeho první publikace na uvedené téma pochází z roku 1810 (Disquisitio de elementis ellipticis Palladis), ale již v roce 1798 se ve svých denících záhadně zmínil, že vyřešil problém eliminace. Jisté je, že metodu použil k výpočtu oběžné dráhy asteroidu Pallas v letech 1803 až 1809. V roce 1810 Gauss vylepšil zápis pro symetrickou eliminaci, která se v 19. století stala důležitou pro profesionální ruční výpočty při řešení normálních rovnic v metodou nejmenších čtverců. Ve 20. letech 19. století popsal LU rozklad, později známý jako Gaussova–Jordanova eliminace, která našla uplatnění zejména v geodézii díky práci geodeta Wilhelma Jordana. Termín „Gaussova–Jordanova eliminace“ vychází z varianty Gaussovy eliminace, jak ji Jordan popsal v roce 1888. Metoda se však objevuje i v článku Clasena publikovaném ve stejném roce. Jordan a Clasen pravděpodobně objevili Gaussovu–Jordanovu eliminaci nezávisle. I přes svou historickou důležitost byl algoritmus pojmenován až v 50. letech 20. století kvůli dohadům ohledně jeho původu.

Během a po druhé světové válce se studium numerických metod stalo důležitějším a Gaussova metoda byla nyní stále více aplikována na problémy nezávislé na metodě nejmenších čtverců. John von Neumann a Alan Turing definovali LU rozklad v podobě, která je dnes běžná, a zkoumali fenomén zaokrouhlovacích chyb. Tyto otázky uspokojivě vyřešil až v 60. letech James Hardy Wilkinson, který ukázal, že metoda s pivotací je zpětně stabilní.

Odkazy

Reference

V tomto článku byly použity překlady textů z článků Gaussian elimination na anglické Wikipedii a Gaußsches Eliminationsverfahren na německé Wikipedii.

↑ REKTORYS, Karel. Přehled užité matematiky: II. 7. vyd. Praha: Prometheus, 2000. 874 s. ISBN 80-7196-181-7. S. 553.
↑ J. B. Fraleigh and R. A. Beauregard, Linear Algebra. Addison-Wesley Publishing Company, 1995, Chapter 10.

Literatura

REKTORYS, Karel. Přehled užité matematiky: II. 7. vyd. Praha: Prometheus, 2000. 874 s. ISBN 80-7196-181-7. Kapitola 30. Numerické metody lineární algebry, s. 553–558.
BEČVÁŘ, Jindřich. Lineární algebra. 1.. vyd. Praha: Matfyzpress, 2019. 436 s. ISBN 978-80-7378-392-1.
HLADÍK, Milan. Lineární algebra (nejen) pro informatiky. 1.. vyd. Praha: Matfyzpress, 2019. 328 s. ISBN 978-80-7378-378-5. S. 39.
OLŠÁK, Petr. Lineární algebra [online]. Praha: 2007 [cit. 2023-02-20]. Dostupné online.
MOTL, Luboš; ZAHRADNÍK, Miloš. Pěstujeme lineární algebru [online]. [cit. 2023-02-20]. Dostupné online.

Související články

Externí odkazy

Řešení soustavy lineárních rovnic Gaussovou eliminací: https://web.archive.org/web/20070106223157/http://www.fsid.cvut.cz/cz/U201/zapg9.htm
Gaussova a Gaussova–Jordanova eliminace: http://kfe.fjfi.cvut.cz/~limpouch/numet/linalg/node7.html
Gaussova eliminace bez výběru hlavního prvku: https://web.archive.org/web/20070108015335/http://e-learning.tul.cz/elearning/obr/system/matlab/246/583/gauss2_vstupni.html

[1] REKTORYS, Karel. Přehled užité matematiky: II. 7. vyd. Praha: Prometheus, 2000. 874 s. ISBN 80-7196-181-7. S. 553.

[2] J. B. Fraleigh and R. A. Beauregard, Linear Algebra. Addison-Wesley Publishing Company, 1995, Chapter 10.

[1]

[2]