Gaussova eliminace: algoritmus pro řešení soustav lineárních rovnic

Gaussova eliminace: srozumitelný krok‑za‑krokem návod pro řešení soustav lineárních rovnic, vysvětlení řádkových operací, příklady a tipy pro Gauss‑Jordanovu redukci.

Autor: Leandro Alegsa

V matematice je Gaussova eliminace (nazývaná také redukce řádků) metoda používaná k řešení soustav lineárních rovnic. Je pojmenována po Carlu Friedrichu Gaussovi, slavném německém matematikovi, který o této metodě psal, ale nevynalezl ji. Metoda převádí soustavu rovnic na maticový tvar a pomocí elementárních řádkových operací postupně zjednodušuje rozšířenou matici, až je možné snadno určit řešení soustavy (pokud existuje).

Základní princip a elementární řádkové operace

Pro použití Gaussovy eliminace se koeficienty rovnic zapíší do tzv. rozšířené matice (augmented matrix), kde poslední sloupec obsahuje pravé strany rovnic. Během eliminace se používají tři typy elementárních řádkových operací, které nezmění množinu řešení soustavy:

  • Prohození dvou řádků (swapping řádků).
  • Násobení řádku nenulovým číslem (škálování řádku).
  • Přičtení násobku jednoho řádku k druhému (řádková kombinace).

Algoritmus (postup krok za krokem)

Obvyklý postup Gaussovy eliminace lze shrnout takto:

  • Sestavte rozšířenou matici soustavy.
  • Pro každý sloupec (od prvního po předposlední, pokud řešíte n neznámých, projděte n sloupců):
    • Vyberte pivot (neboli hlavní prvek) v aktuálním sloupci. Pokud je pivot nulový, proveďte prohození s nižším řádkem, který obsahuje nenulový prvek (tzv. částečné pivotování).
    • Pomocí operace škálování upravte pivot tak, aby byl 1 (volitelné; nemusí se dělat hned).
    • Eliminujte všechny prvky pod pivotelementem (přičtením vhodných násobků pivotního řádku k řádkům pod ním), čímž vytvoříte nuly pod pivotem.
  • Po provedení těchto kroků pro všechny sloupce získáte matici v řádkovém echelonovém tvaru (REF). Pokud chcete, můžete pokračovat v eliminaci i nad pivoty, čímž získáte redukovaný řádkový echelonový tvar (RREF) — tomu se říká Gaussova–Jordanova eliminace.
  • Ze získaného (redukovaného) tvaru pak zpětnou substitucí (pokud máte REF) určíte hodnoty neznámých. V RREF jsou hodnoty obvykle ihned čitelné.

Řádkový echelon a redukovaný řádkový echelon

Matice je v řádkovém echelonovém tvaru (REF), pokud platí:

  • Všechny nulové řádky (pokud existují) jsou pod všemi nenulovými řádky.
  • První nenulový prvek (pivot) v každém nenulovém řádku je vpravo od pivotu v řádku nad ním.

Matice je v redukovaném řádkovém echelonovém tvaru (RREF), pokud je navíc každý pivot roven 1 a je jediným nenulovým prvkem ve svém sloupci (tj. nad i pod pivotem jsou nuly). Gaussova eliminace může skončit v REF (běžný postup) nebo pokračovat do RREF (Gaussova–Jordanova eliminace).

Možné výsledky soustavy

Po eliminaci lze rozlišit tři základní případy:

  • Jednoznačné řešení: Každá proměnná je určena — matice má plný počet pivotů (rank = počet proměnných).
  • Infinitně mnoho řešení: Existují volné proměnné (sloupce bez pivotu), které lze parametry vyjádřit. Rank je menší než počet proměnných, ale rozšířená matice nekontradikuje (žádný řádek typu [0 ... 0 | c] s c ≠ 0).
  • Žádné řešení (inkonzistence): Po eliminaci vznikne řádek tvaru [0 0 ... 0 | c] s c ≠ 0, což znamená, že soustava je neslučitelná.

Krátký příklad (2×2)

Řešme soustavu:
2x + y = 5
4x − 6y = −2

Sestavíme rozšířenou matici:

[ 2 1 | 5 ]
[ 4 −6 | −2 ]

Eliminace: použijeme R2 ← R2 − 2·R1:

[ 2 1 | 5 ]
[ 0 −8 | −12 ]

Teď z druhého řádku dostaneme y = (−12)/(−8) = 3/2. Dosadíme do prvního řádku: 2x + (3/2) = 5 → 2x = 7/2 → x = 7/4.

Řešení: x = 7/4, y = 3/2.

Numerické aspekty a složitost

Ve výpočetní praxi je důležité dbát na stabilitu a přesnost:

  • Pivotování: Pokud je pivot příliš malý (blízko nule), aritmetické chyby mohou způsobit velké odchylky výsledku. Proto se často používá částečné pivotování (prohození s řádkem, který má v aktuálním sloupci největší absolutní hodnotu pivotu) nebo úplné pivotování (prohození řádků i sloupců).
  • Škálování: Normalizace řádků/sloupců může zlepšit numerickou stabilitu.
  • Složitost: Standardní Gaussova eliminace má výpočetní složitost O(n^3) pro n×n matici (počítáno v základních aritmetických operacích).

Použití

Gaussova eliminace je základní nástroj v lineární algebře a numerických výpočtech — používá se například při řešení soustav v technických aplikacích, při výpočtu inverzních matic, ve výpočtech determinantů, v analýze sítí, při interpolacích a v mnoha algoritmech numerické lineární algebry.

Shrnutí: Gaussova eliminace je systematická metoda přetvoření rozšířené matice soustavy do tvaru, ze kterého lze určit, zda soustava má jediné řešení, nekonečně mnoho řešení nebo je neslučitelná. Při praktické implementaci je vhodné dbát na pivotování kvůli číselné stabilitě.

Příklad

Předpokládejme, že cílem je najít odpovědi na tuto soustavu lineárních rovnic.

2 x + y - z = 8 ( R 1 ) - 3 x - y + 2 z = - 11 ( R 2 ) - 2 x + y + 2 z = - 3 ( R 3 ) {\displaystyle {\begin{alignedat}{7}2x&&\;+\;&&y&&\;-\;&&z&&\;=\;&&8&\qquad (R_{1})\\-3x&&\;-\;&&y&&\;+\;&&2z&&\;=\;&&-11&\qquad (R_{2})\\-2x&&\;+\;&&y&&\;+\;&&2z&&\;=\;&&-3&\qquad (R_{3})\end{alignedat}}} {\displaystyle {\begin{alignedat}{7}2x&&\;+\;&&y&&\;-\;&&z&&\;=\;&&8&\qquad (R_{1})\\-3x&&\;-\;&&y&&\;+\;&&2z&&\;=\;&&-11&\qquad (R_{2})\\-2x&&\;+\;&&y&&\;+\;&&2z&&\;=\;&&-3&\qquad (R_{3})\end{alignedat}}}

Nejprve je třeba systém přeměnit na rozšířenou matici. V rozšířené matici se každá lineární rovnice stává řádkem. Na jedné straně rozšířené matice se koeficienty každého členu lineární rovnice stanou čísly v matici. Na druhé straně rozšířené matice jsou konstantní členy, kterým se rovná každá lineární rovnice. Pro tuto soustavu je rozšířená matice následující:

[ 2 1 - 1 8 - 3 - 1 2 - 11 - 2 1 2 - 3 ] {\displaystyle \left[{\begin{array}{ccc|c}2&1&-1&8\-3&-1&2&-11\-2&1&2&-3\end{array}}\right]} {\displaystyle \left[{\begin{array}{ccc|c}2&1&-1&8\\-3&-1&2&-11\\-2&1&2&-3\end{array}}\right]}

Poté lze s rozšířenou maticí provést řádkové operace, které ji zjednoduší. Následující tabulka ukazuje postup řádkové redukce soustavy rovnic a rozšířené matice.

Soustava rovnic

Řádkové operace

Rozšířená matice

2 x + y - z = 8 - 3 x - y + 2 z = - 11 - 2 x + y + 2 z = - 3 {\displaystyle {\begin{alignedat}{7}2x&&\;+\;&&y&&\;-\;&&z&&\;=\;&&8&&\\-3x&&\;-\;&&y&&\;+\;&&2z&& \;=\;&&-11&\\-2x&&\;+\;&&y&&\;+\;&&2z&&\;=\;&&-3&\end{alignedat}}} {\displaystyle {\begin{alignedat}{7}2x&&\;+\;&&y&&\;-\;&&z&&\;=\;&&8&\\-3x&&\;-\;&&y&&\;+\;&&2z&&\;=\;&&-11&\\-2x&&\;+\;&&y&&\;+\;&&2z&&\;=\;&&-3&\end{alignedat}}}

[ 2 1 - 1 8 - 3 - 1 2 - 11 - 2 1 2 - 3 ] {\displaystyle \left[{\begin{array}{ccc|c}2&1&-1&8\-3&-1&2&-11\-2&1&2&-3\end{array}}\right]} {\displaystyle \left[{\begin{array}{ccc|c}2&1&-1&8\\-3&-1&2&-11\\-2&1&2&-3\end{array}}\right]}

2 x + y - z = 8 1 2 y + 1 2 z = 1 2 y + z = 5 {\displaystyle {\begin{alignedat}{7}2x&&\;+&&&y&&\;-&&&\;z&&&\;=\;&&8&\\&&&&{\frac {1}{2}}y&&\;+&&\;{\frac {1}{2}}z&&\;=\;&&1&\\&&&&2y&&\;+&&\;z&&\;=\;&&5&\end{alignedat}}} {\displaystyle {\begin{alignedat}{7}2x&&\;+&&y&&\;-&&\;z&&\;=\;&&8&\\&&&&{\frac {1}{2}}y&&\;+&&\;{\frac {1}{2}}z&&\;=\;&&1&\\&&&&2y&&\;+&&\;z&&\;=\;&&5&\end{alignedat}}}

R 2 + 3 2 R 1 → R 2 {\displaystyle R_{2}+{\frac {3}{2}}R_{1}\rightarrow R_{2}}} {\displaystyle R_{2}+{\frac {3}{2}}R_{1}\rightarrow R_{2}}
R 3 + R 1 → R 3 {\displaystyle R_{3}+R_{1}\rightarrow R_{3}} {\displaystyle R_{3}+R_{1}\rightarrow R_{3}}

[ 2 1 - 1 8 0 1 / 2 1 / 2 1 0 2 1 5 ] {\displaystyle \left[{\begin{array}{ccc|c}2&1&-1&8\0&1/2&1/2&1\0&2&1&5\end{array}}\right]} {\displaystyle \left[{\begin{array}{ccc|c}2&1&-1&8\\0&1/2&1/2&1\\0&2&1&5\end{array}}\right]}

2 x + y - z = 8 1 2 y + 1 2 z = 1 - z = 1 {\displaystyle {\begin{alignedat}{7}2x&&\;+&&&y\;&&-&&\;z\;&&=\;&&8&\\&&&&{\frac {1}{2}}y\;&&+&&\;{\frac {1}{2}}z\;&&=\;&&1&\\&&&&&&&&\;-z\;& &\;=\;&&1&\end{alignedat}}} {\displaystyle {\begin{alignedat}{7}2x&&\;+&&y\;&&-&&\;z\;&&=\;&&8&\\&&&&{\frac {1}{2}}y\;&&+&&\;{\frac {1}{2}}z\;&&=\;&&1&\\&&&&&&&&\;-z\;&&\;=\;&&1&\end{alignedat}}}

R 3 + - 4 R 2 → R 3 {\displaystyle R_{3}+-4R_{2}\rightarrow R_{3}} {\displaystyle R_{3}+-4R_{2}\rightarrow R_{3}}

[ 2 1 - 1 8 0 1 / 2 1 / 2 1 0 0 - 1 1 ] {\displaystyle \left[{\begin{array}{ccc|c}2&1&-1&8\0&1/2&1/2&1\0&0&-1&1\end{array}}\right]} {\displaystyle \left[{\begin{array}{ccc|c}2&1&-1&8\\0&1/2&1/2&1\\0&0&-1&1\end{array}}\right]}

Matice je nyní v řádkovém tvaru. Tomuto tvaru se také říká trojúhelníkový tvar.

Soustava rovnic

Řádkové operace

Rozšířená matice

2 x + y = 7 1 2 y = 3 / 2 - z = 1 {\displaystyle {\begin{alignedat}{7}2x&&\;+&&y\;&&&&\;\;&&=\;&&7&\\&&&&&&{\frac {1}{2}}y\;&&&&\;\;&&=\;&&3/2&\\&&&&&&&&\;-z\;&&\;=\;&&1&\end{alignedat}}} {\displaystyle {\begin{alignedat}{7}2x&&\;+&&y\;&&&&\;\;&&=\;&&7&\\&&&&{\frac {1}{2}}y\;&&&&\;\;&&=\;&&3/2&\\&&&&&&&&\;-z\;&&\;=\;&&1&\end{alignedat}}}

R 2 + 1 2 R 3 → R 2 {\displaystyle R_{2}+{\frac {1}{2}}R_{3}\rightarrow R_{2}} {\displaystyle R_{2}+{\frac {1}{2}}R_{3}\rightarrow R_{2}}
R 1 - R 3 → R 1 {\displaystyle R_{1}-R_{3}\rightarrow R_{1}} {\displaystyle R_{1}-R_{3}\rightarrow R_{1}}

[ 2 1 0 7 0 1 / 2 0 3 / 2 0 0 - 1 1 ] {\displaystyle \left[{\begin{array}{ccc|c}2&1&0&7\0&1/2&0&3/2\0&0&1&1\end{array}}\right]} {\displaystyle \left[{\begin{array}{ccc|c}2&1&0&7\\0&1/2&0&3/2\\0&0&-1&1\end{array}}\right]}

2 x + y = 7 y = 3 z = - 1 {\displaystyle {\begin{alignedat}{7}2x&&\;+&&y\;&&&&\;\;&&=\;&&7&\\&&&&&y\;&&&&\;\;&&=\;&&3&\\&&&&&&&&\;z\;&&\;=\;&&-1&\end{alignedat}}} {\displaystyle {\begin{alignedat}{7}2x&&\;+&&y\;&&&&\;\;&&=\;&&7&\\&&&&y\;&&&&\;\;&&=\;&&3&\\&&&&&&&&\;z\;&&\;=\;&&-1&\end{alignedat}}}

2 R 2 → R 2 {\displaystyle 2R_{2}\rightarrow R_{2}} {\displaystyle 2R_{2}\rightarrow R_{2}}
R 3 → R 3 {\displaystyle -R_{3}\rightarrow R_{3}} {\displaystyle -R_{3}\rightarrow R_{3}}

[ 2 1 0 7 0 1 0 3 0 0 1 - 1 ] {\displaystyle \left[{\begin{array}{ccc|c}2&1&0&7\0&1&0&3\0&0&1&-1\end{array}}\right]} {\displaystyle \left[{\begin{array}{ccc|c}2&1&0&7\\0&1&0&3\\0&0&1&-1\end{array}}\right]}

x = 2 y = 3 z = - 1 {\displaystyle {\begin{alignedat}{7}x&&\;&&\;&&&&\;\;&&=\;&&2&\\&&&& y\;&&&&\;\;&&=\;&&3&\\&&&&&&&&\;z\;&&\;=\;&&-1&\end{alignedat}}} {\displaystyle {\begin{alignedat}{7}x&&\;&&\;&&&&\;\;&&=\;&&2&\\&&&&y\;&&&&\;\;&&=\;&&3&\\&&&&&&&&\;z\;&&\;=\;&&-1&\end{alignedat}}}

R 1 - R 2 → R 1 {\displaystyle R_{1}-R_{2}\rightarrow R_{1}} {\displaystyle R_{1}-R_{2}\rightarrow R_{1}}
1 2 R 1 → R 1 {\displaystyle {\frac {1}{2}}R_{1}\rightarrow R_{1}} {\displaystyle {\frac {1}{2}}R_{1}\rightarrow R_{1}}

[ 1 0 0 2 0 1 0 3 0 0 1 - 1 ] {\displaystyle \left[{\begin{array}{ccc|c}1&0&0&2\0&1&0&3\0&0&1&-1\end{array}}\right]} {\displaystyle \left[{\begin{array}{ccc|c}1&0&0&2\\0&1&0&3\\0&0&1&-1\end{array}}\right]}

Matice je nyní v redukovaném řádkovém tvaru. Přečtením této matice zjistíme, že řešení této soustavy rovnic nastane, když x = 2, y = 3 a z = -1.

Otázky a odpovědi

Otázka: Co je to Gaussova eliminace?


Odpověď: Gaussova eliminace je metoda používaná v matematice k řešení soustav lineárních rovnic.

Otázka: Po kom je pojmenována?


Odpověď: Je pojmenována po Carlu Friedrichu Gaussovi, slavném německém matematikovi, který o této metodě psal, ale nevynalezl ji.

Otázka: Jak se Gaussova eliminace provádí?


Odpověď: Gaussova eliminace se provádí tak, že se pomocí koeficientů členů v soustavě lineárních rovnic vytvoří rozšířená matice. Poté se ke zjednodušení matice použijí základní řádkové operace.

Otázka: Jaké tři typy řádkových operací se používají při Gaussově eliminaci?


Odpověď: V Gaussově eliminaci se používají tyto tři typy řádkových operací: Prohození jednoho řádku s jiným řádkem, Násobení řádku nenulovým číslem a Sčítání nebo odečítání řádku od jiného řádku.

Otázka: Co je cílem Gaussovy eliminace?


Odpověď: Cílem Gaussovy eliminace je získat matici v řádkovém echelonovém tvaru.

Otázka: Co je to řádkový echelonový tvar?


Odpověď: Pokud je matice v řádkově-echelonovém tvaru, znamená to, že při čtení zleva doprava bude každý řádek začínat alespoň o jeden nulový člen více než řádek nad ním.

Otázka: Co je to redukovaná řádkově-echelonová forma?


Odpověď: Redukovaná řádková echelonová forma znamená, že matice je v řádkové echelonové formě a jediný nenulový člen v každém řádku je 1. Gaussova eliminace, která vytváří výsledek redukované řádkové echelonové matice, se někdy nazývá Gaussova-Jordanova eliminace.


Vyhledávání
AlegsaOnline.com - 2020 / 2025 - License CC3