náhled|Animace Gaussovy eliminace. Červený řádek eliminuje následující řádky. Zelené řádky mění pořadí. Šedě jsou počáteční úseky nul. Gaussova eliminační metoda, jednoduše Gaussova eliminace, 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 metoda vyžaduje asymptoticky 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 druhy 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). náhled|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 typu je v odstupňovaném tvaru, pokud existují a rostoucí posloupnost přirozených čísel takové, že:
Pivotem je prvek na pozici pro každé . Číslo je hodnost matice .
Odstupňovaná tvar odpovídá soustavě, jejíž netriviální rovnice (tj. 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:
V tabulce je předveden postup Gaussovy eliminace současně na rozšířené matici soustavy i na soustavě rovnic samotné.
{| style="background-color:white;" class="wikitable" |- ! Rozšířená matice soustavy !! Soustava rovnic |- align="center"
|ke 2. řádku přičteme 1. řádek ke 3. řádku přičteme 1. řádek | z 1. rovnice vyjádříme
a dosadíme je do ostatních dvou |- align="center"
|od 3. řádku odečteme 2. řádek | ze 2. rovnice vyjádříme
a dosadíme je do 3. rovnice |- align="center"
|- align="center" | 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 (tj. na levé straně) neobsahují pivot:
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
odpovídá hodnota 10 v pravém horním rohu součtu hodnot v prvním řádku . 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 a zároveň má odpovídat řádkovému součtu . 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:
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.
náhled|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 typu je v redukovaném odstupňovaném tvaru, pokud existují a rostoucí posloupnost přirozených čísel takové, že:
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.
{| style="background-color:white;" class="wikitable" |- ! Rozšířená matice soustavy !! Soustava rovnic |- align="center"
|- align="center" |3. řádek vydělíme -1 |ze 3. rovnice odvodíme |- align="center"
|- align="center" |k 1. řádku přičteme 3. od 2. řádku odečteme 3. řádek |dosadíme do předchozích rovnic |- align="center"
|- align="center" |2. řádek vynásobíme 2 |ze 2. rovnice odvodíme |- align="center"
|- align="center" |od 1. řádku odečteme 2. |dosadíme do 1. rovnice |- align="center"
|- align="center" |1. řádek vydělíme 2 |z 1. rovnice odvodíme |- align="center"
|- align="center" |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í
je poslední rovnice vždy splněna a neovlivňuje množinu řešení. Neznámá odpovídá sloupci bez pivotu, a je proto volná. Z druhé rovnice lze vyjádřit v závislosti na , konkrétně z rovnice vyplývá, že . Dosazení do první rovnice dává rovnici . Z ní lze vyjádřit .
Stejný postup zapsaný pomocí matic dává redukovaný odstupňovaný tvar:
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 za . 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 0 1 -1 8 -3 -1 2 -11 -2 1 2 -3 +Přerovnání řádků -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 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ů 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 s regulární maticí , 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 na součin levé dolní, normalizované trojúhelníkové matice (angl. „left“ nebo „lower“) a pravou horní trojúhelníkovou matici (z angl. „upper“ - horní, též angl. „right“ pak bývá značena ). Rozklad ilustruje následující ukázka:
Matice zaznamenává provedené úpravy, neboť tyto odpovídají součinům s Frobeniovými maticemi, a je v odstupňovaném tvaru. Diagonální prvky matice jsou zpravidla normalizovány na 1. Zapamatování úprav prostřednictvím matice má tu výhodu, že soustavy rovnic , které se liší jen pravými stranami , lze po jednom provedení rozkladu matice už efektivně řešit jen dvojicí zpětných substitucí závisejících jen na vektoru .
Je-li nevyhnutelné provádět i přerovnání řádků, lze je v rozkladu interpretovat pomocí permutační matice :
Permutační matice 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 existují permutační matice , čtvercová dolní normalizovaná trojúhelníková matice a čtvercová horní trojúhelníková matice , všechny stejného řádu jako , splňující:
.
Neúplné rozklady