Prejsť na obsah
Domov

Gaussova eliminácia: definícia, postup a príklady riešenia rovníc

Naučte sa Gaussovu elimináciu: definícia, krok za krokom postup a prehľadné príklady riešenia sústav lineárnych rovníc vrátane Gauss–Jordanovej metódy.

Autor: Vytvorené: Aktualizované:

V matematike je Gaussova eliminácia (nazývaná aj redukcia riadkov) metóda používaná na riešenie sústav lineárnych rovníc. Je pomenovaná po Carlovi Friedrichovi Gaussovi, slávnom nemeckom matematikovi, ktorý o tejto metóde písal, hoci ju nevynašiel.

Galéria obrázkov

3 Obrázky
Gaussian elimination animated
en.wikipedia.org · CC BY-SA 4.0

Základná myšlienka

Na vykonanie Gaussovej eliminácie sa koeficienty členov v sústave lineárnych rovníc zapíšu do tzv. rozšírenej matice (augmented matrix). Potom sa pomocou základných riadkových operácií matica upravuje, až kým nedosiahne jednoduchší tvar, z ktorého sa riešenie sústavy dá ľahko získať.

Riadkové operácie

Používajú sa tri základné typy riadkových operácií, ktoré nemenia množinu riešení sústavy:

  • Typ 1: výmena dvoch riadkov.
  • Typ 2: násobenie riadku nenulovým číslom.
  • Typ 3: pripočítanie násobku jedného riadku k druhému (sčítanie/odčítanie riadku).

Požadované tvary matice

Cieľom Gaussovej eliminácie je dosiahnuť maticu v riadkovom echelónovom tvare (row echelon form). To znamená, že každý riadok začína o jednu (alebo viac) nul viac ako riadok nad ním pri čítaní zľava doprava a všetky nulové riadky (ak existujú) sú pod nenulovými riadkami. Ak ďalej v každom riadku urobíme vedúci (prvý nenulový) prvok rovný 1 a zabezpečíme, aby v jeho stĺpci boli všetky ostatné prvky nulové, dostaneme redukovaný riadkovo-echelónový tvar (reduced row echelon form, RREF).

Gaussova-Jordanova eliminácia je varianta, ktorá priamo vedie k RREF a umožňuje bez ďalšieho back-substitution čítať riešenia priamo z matice.

Postup (algoritmus)

  1. Zapíšte sústavu ako rozšírenú maticu (koeficienty a pravé strany).
  2. Prejdite stĺpce zľava doprava a v každom stĺpci vyberte pivot (prvý nenulový prvok zhora, prípadne pomocou výmeny riadkov zabezpečte nenulový pivot). Odporúča sa čiastočné pivotovanie (výmena s riadkom, ktorý má najväčšiu absolútnu hodnotu v stĺpci) kvôli numerickej stabilite.
  3. Pomocou pivotu eliminujte všetky prvky pod ním (t. j. urobte ich nulovými) pripočítaním vhodných násobkov pivotového riadku k riadkom pod ním.
  4. Opakujte pre ďalší stĺpec a riadky posunuté o jednu doprava až dovtedy, kým nepokryjete všetky premenné alebo riadky.
  5. Ak chcete RREF, po získaní echelónového tvaru ešte eliminujte nad pivotmi (urobte prvky nad pivotmi nulovými) a škálujte pivoty na 1.
  6. Pre klasickú Gaussovu elimináciu použite back-substitution na zistenie hodnôt premenných z echelónového tvaru.

Možné výsledky sústavy

  • Jediné riešenie: počet pivotov rovná sa počtu premenných (matica má plný stĺpcový hodnosť).
  • Žiadne riešenie (inkonzistentná sústava): počas eliminácie vznikne riadok tvaru [0 0 ... 0 | b] s b ≠ 0, čo znamená protirečenie 0 = b.
  • Infinitne veľa riešení: počet pivotov je menší než počet premenných — existujú voľné premenné (parameters), ktoré možno nastaviť libovolne a ostatné premenné vyjadriť pomocou nich.

Komplexnosť

Pre maticu n × n má priamy Gaussov algoritmus časovú zložitosť O(n^3) (operácie sčítania/násobenia). Pre veľké systémy sa často používajú metódy špeciálne prispôsobené štruktúre matice (riedke matice, symetrické, atď.).

Príklad (krok za krokom)

Riešme sústavu 3 rovníc so 3 neznámymi:

 x + 2y -  z = 1 2x + 3y +  z = 4 - x +  y + 2z = -1

Zapíšeme rozšírenú maticu:

 [ 1  2 -1 |  1 ] [ 2  3  1 |  4 ] [-1  1  2 | -1 ]

Krok 1: eliminujeme prvky pod pivotom v prvom stĺpci.

R2 ← R2 - 2·R1, R3 ← R3 + R1

 [ 1   2  -1 |  1 ] [ 0  -1   3 |  2 ] [ 0   3   1 |  0 ]

Krok 2: ako pivot v druhom kroku použijeme druhý riadok (môžeme ho vynásobiť -1, aby pivot bol 1): R2 ← -1·R2

 [ 1  2  -1 |  1 ] [ 0  1  -3 | -2 ] [ 0  3   1 |  0 ]

Krok 3: eliminujeme prvky v druhom stĺpci pod pivotom: R3 ← R3 - 3·R2

 [ 1  2  -1 |  1 ] [ 0  1  -3 | -2 ] [ 0  0  10 |  6 ]

Krok 4: teraz riešime pre z z tretieho riadku: 10z = 6 ⇒ z = 6/10 = 3/5.

Krok 5: spätnou substitúciou nájdeme y z druhého riadku: y - 3z = -2 ⇒ y = -2 + 3·(3/5) = -2 + 9/5 = (-10 + 9)/5 = -1/5.

Krok 6: z prvého riadku nájdeme x: x + 2y - z = 1 ⇒ x = 1 - 2y + z = 1 - 2·(-1/5) + 3/5 = 1 + 2/5 + 3/5 = 1 + 1 = 2.

Riešenie sústavy je x = 2, y = -1/5, z = 3/5.

Tipy a poznámky

  • Pri numerických výpočtoch sa odporúča pivotovanie (zvyčajne čiastočné pivotovanie: výber najväčšieho absolútneho prvku v aktuálnom stĺpci) kvôli zlepšeniu stability a zníženiu zaokrúhľovacích chýb.
  • Pre veľké a riedke matice sa používajú špecializované implementácie, ktoré zachovávajú riedosť, aby sa znížila pamäťová náročnosť a zrýchlil výpočet.
  • Gaussova eliminácia nie je len na riešenie sústav; používa sa aj pri výpočte inverznej matice (aplikovaním eliminácie na rozšírenú maticu [A | I]) a pri výpočte hodnosti matice.

Príklad

Predpokladajme, že cieľom je nájsť odpovede na túto sústavu lineárnych rovníc.

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}}}

Najskôr je potrebné premeniť systém na rozšírenú maticu. V rozšírenej matici sa každá lineárna rovnica stáva riadkom. Na jednej strane rozšírenej matice sa koeficienty každého člena lineárnej rovnice stanú číslami v matici. Na druhej strane rozšírenej matice sú konštantné členy, ktorým sa rovná každá lineárna rovnica. Pre tento systém je rozšírená matica:

[ 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]}

Potom možno na rozšírenej matici vykonať riadkové operácie na jej zjednodušenie. V nasledujúcej tabuľke je uvedený postup redukcie riadkov na sústave rovníc a na rozšírenej matici.

Sústava rovníc

Riadkové operácie

Rozšírená matica

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]}

Matica je teraz vo forme riadkov a echelónov. Tento tvar sa nazýva aj trojuholníkový tvar.

Sústava rovníc

Riadkové operácie

Rozšírená matica

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]}

Matica je teraz v redukovanom riadkovo-echelónovom tvare. Čítanie tejto matice nám hovorí, že riešenie tejto sústavy rovníc nastane, keď x = 2, y = 3 a z = -1.

Otázky a odpovede

Otázka: Čo je to Gaussova eliminácia?

Odpoveď: Gaussova eliminácia je metóda používaná v matematike na riešenie sústav lineárnych rovníc.

Otázka: Po kom je pomenovaná?

Odpoveď: Je pomenovaná po Carlovi Friedrichovi Gaussovi, slávnom nemeckom matematikovi, ktorý o tejto metóde písal, ale nevynašiel ju.

Otázka: Ako sa vykonáva Gaussova eliminácia?

Odpoveď: Gaussova eliminácia sa vykonáva pomocou koeficientov členov v sústave lineárnych rovníc na vytvorenie rozšírenej matice. Potom sa na zjednodušenie matice použijú základné riadkové operácie.

Otázka: Aké tri typy riadkových operácií sa používajú pri Gaussovej eliminácii?

Odpoveď: V Gaussovej eliminácii sa používajú tieto tri typy riadkových operácií: Výmena jedného riadku za iný riadok, Vynásobenie riadku nenulovým číslom a Sčítanie alebo odčítanie riadku od iného riadku.

Otázka: Čo je cieľom Gaussovej eliminácie?

Odpoveď: Cieľom Gaussovej eliminácie je získať maticu v riadkovom echelónovom tvare.

Otázka: Čo je to riadkovo-echelónová forma?

Odpoveď: Ak je matica v riadkovo-echelónovej forme, znamená to, že pri čítaní zľava doprava bude každý riadok začínať aspoň o jeden nulový člen viac ako riadok nad ním.

Otázka: Čo je redukovaná riadková echelónová forma?

Odpoveď: Redukovaná riadkovo-echelónová forma znamená, že matica je v riadkovo-echelónovej forme a jediný nenulový člen v každom riadku je 1. Gaussova eliminácia, ktorá vytvára výsledok redukovanej riadkovo-echelónovej matice, sa niekedy nazýva Gaussova-Jordanova eliminácia.

Autor

AlegsaOnline.com Gaussova eliminácia: definícia, postup a príklady riešenia rovníc

URL: https://sk.alegsaonline.com/art/37750

Zdieľať