Gaussova eliminacijska metoda: definicija in reševanje sistemov linearnih enačb

V matematiki je Gaussova eliminacija (imenovana tudi redukcija vrstic) metoda za reševanje sistemov linearnih enačb, preverjanje obstoja in števila rešitev ter za izračun drugih povezanih količin. Ime nosi po Carlu Friedrichu Gaussu, slavnem nemškem matematiku, ki je o metodi pisal in jo populariziral, čeprav so podobne postopke poznali že prej. Različica, ki matriko pripelje do popolnoma reducirane oblike, se pogosto imenuje Gauss–Jordanova eliminacija.

Za izvedbo Gaussove eliminacije se iz koeficienti članov in konstant sistema oblikuje razširjena matrika (levi del vsebuje koeficiente spremenljivk, desni stolpec pa konstante). Nato matriko poenostavljamo z osnovnimi vrstičnimi operacijami, dokler ne dobimo preproste oblike, iz katere rešitve preberemo z bodisi nazadnim vstavljanjem bodisi neposredno.

Tip 1: Zamenjava ene vrstice z drugo.

Tip 2: Pomnoževanje vrstice z neničelnim številom.

Tip 3: Dodajanje večkratnika ene vrstice k drugi (ali odštevanje).

Cilj postopka in oblike matrik

Cilj Gaussove eliminacije je dobiti matriko v vrstično‑ešalonski obliki (angl. row echelon form). To pomeni, da velja:

  • Vse ničelne vrstice (če obstajajo) so na dnu.
  • Prvi neničelni element vsake neničelne vrstice (t. i. pivot) je desno od pivota v vrstici nad njo.
  • Vsi elementi pod pivotom v njegovem stolpcu so ničle.

Še strožja je reducirana vrstično‑ešalonska oblika (angl. reduced row echelon form): matrika je v vrstično‑ešalonski obliki, vsak pivot je enak 1 in v pivotnem stolpcu so vsi ostali elementi (nad in pod pivotom) enaki 0. V tej obliki lahko rešitve preberemo neposredno. Gaussova eliminacija, ki nadaljuje eliminiranje tudi nad pivoti (torej do popolnoma reducirane oblike), se pogosto poimenuje Gauss–Jordanova eliminacija.

Postopek reševanja korak za korakom

  • Oblikuj razširjeno matriko sistema.
  • Za vsak stolpec od leve proti desni izberi pivot (če je na pivotnem mestu 0, uporabi zamenjavo vrstic; v praksi pogosto izbereš največji po absolutni vrednosti – delna izbira pivota).
  • Po želji normiraj pivot na 1 (pomnoži vrstico z ustreznim številom).
  • Z vrstičnimi operacijami odpravi vse elemente pod pivotom (pri Gauss–Jordanovi tudi nad pivotom).
  • Ko dosežeš vrstično‑ešalonsko obliko, izračunaj rešitve z nazadnim vstavljanjem; v reducirani obliki rešitve prebereš neposredno.

Vrste rešitev

  • Edinstvena rešitev: vsak stolpec koeficientov spremenljivk ima pivot (ni prostih spremenljivk).
  • Neskončno mnogo rešitev: vsaj en stolpec brez pivota (proste spremenljivke); rešitve opišemo parametrično.
  • Brez rešitve (neskladni sistem): pojavi se vrstica oblike [0 0 … 0 | b] z b ≠ 0.

Kratek primer

Reši sistem: x + y + z = 6, 2x + 3y + z = 11, −x + y + 2z = 7.

Razširjena matrika: [1 1 1 | 6; 2 3 1 | 11; −1 1 2 | 7]

  • R2 ← R2 − 2·R1 → [0 1 −1 | −1]
  • R3 ← R3 + R1 → [0 2 3 | 13]
  • R3 ← R3 − 2·R2 → [0 0 5 | 15]

Iz zadnje vrstice dobimo z = 3; iz druge y − z = −1, torej y = 2; iz prve x + 2 + 3 = 6, torej x = 1. Rešitev je (x, y, z) = (1, 2, 3).

Praktični vidiki in napotki

  • Pivotiranje: če je pivot majhen ali 0, zamenjaj vrstice (delno pivotiranje) ali po potrebi tudi stolpce (polno pivotiranje). To izboljša numerično stabilnost in prepreči deljenje z zelo majhnimi števili.
  • Računska zahtevnost: za kvadratno matriko n × n je časovna zahtevnost približno O(n³), poraba pomnilnika pa O(n²).
  • Posebni primeri: če je det(A) = 0, matrika ni obrnljiva; lahko se pojavi neskončno rešitev ali nobena. Če det(A) ≠ 0, ima sistem edinstveno rešitev.
  • Strošek natančnosti: pri realno‑številskih računih zaokroževanje lahko vnese napake; pivotiranje in skaliranje stolpcev lahko te napake zmanjša.

Povezave z drugimi pojmi

  • Determinanta: produkt pivotov (upoštevajoč spremembe predznaka pri zamenjavah vrstic) daje determinanto.
  • LU‑razcep: sistem lahko rešimo hitreje za več različnih desnih strani b s pomočjo razcepa A = L·U, ki je tesno povezan z Gaussovo eliminacijo.
  • Inverzna matrika: z Gauss–Jordanovim postopkom lahko iz [A | I] dobimo [I | A⁻¹], če A je obrnljiva.

V praksi je koristno zapisovati vse uporabljene vrstične operacije, saj to olajša preverjanje pravilnosti in sledenje napakam. Pri večjih ali numerično občutljivih problemih je priporočena uporaba delnega ali polnega pivotiranja ter računalniških knjižnic, ki implementirajo stabilne različice algoritma.

Primer

Recimo, da je cilj poiskati odgovore na ta sistem linearnih enačb.

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

Najprej je treba sistem spremeniti v razširjeno matriko. V razširjeni matriki vsaka linearna enačba postane vrstica. Na eni strani razširjene matrike koeficienti vsakega člena linearne enačbe postanejo števila v matriki. Na drugi strani razširjene matrike so konstantni členi, ki jim je vsaka linearna enačba enaka. Za ta sistem je razširjena matrika:

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

Nato lahko na razširjeni matriki izvedemo vrstilne operacije, da jo poenostavimo. V spodnji tabeli je prikazan postopek redukcije vrstic na sistemu enačb in na povečani matriki.

Sistem enačb

Operacije v vrstici

Povečana matrika

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

Matrika je zdaj v vrstično-ekelonski obliki. To imenujemo tudi trikotniška oblika.

Sistem enačb

Operacije v vrstici

Povečana matrika

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&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 0 1 - 1 ] {\displaystyle \left[{\begin{array}{ccc|c}2&1&0&7\0&1&0&3\0&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 0 2 0 1 0 3 0 0 0 1 - 1 ] {\displaystyle \left[{\begin{array}{ccc|c}1&0&0&2\0&1&0&3\0&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]}

Matrika je zdaj v reducirani vrstično-ekelonski obliki. Iz te matrike izvemo, da so rešitve tega sistema enačb takrat, ko je x = 2, y = 3 in z = -1.

Vprašanja in odgovori

V: Kaj je Gaussova eliminacija?


O: Gaussova eliminacija je metoda, ki se v matematiki uporablja za reševanje sistemov linearnih enačb.

V: Po kom je poimenovana?


O: Imenuje se po Carlu Friedrichu Gaussu, slavnem nemškem matematiku, ki je o tej metodi pisal, vendar je ni izumil.

V: Kako se izvaja Gaussova eliminacija?


O: Gaussova eliminacija se izvede tako, da se uporabijo koeficienti izrazov v sistemu linearnih enačb, da se ustvari razširjena matrika. Nato se za poenostavitev matrike uporabijo osnovne vrstne operacije.

V: Katere tri vrste vrstilnih operacij se uporabljajo pri Gaussovi eliminaciji?


O: Pri Gaussovi eliminaciji se uporabljajo naslednje tri vrste vrstic: zamenjava ene vrstice z drugo, pomnoževanje vrstice z neničelnim številom in seštevanje ali odštevanje vrstice od druge vrstice.

V: Kakšen je cilj Gaussove eliminacije?


O: Cilj Gaussove eliminacije je dobiti matriko v vrstično-ekelonski obliki.

V: Kaj je vrstica-echelonova oblika?


O: Če je matrika v vrstično-ekelonski obliki, to pomeni, da se vsaka vrstica, če jo beremo od leve proti desni, začne z vsaj enim ničelnim členom več kot vrstica nad njo.

V: Kaj je reducirana vrstno-echelonska oblika?


O: Zmanjšana vrstno-echelonska oblika pomeni, da je matrika v vrstno-echelonski obliki in da je edini neničelni člen v vsaki vrstici 1. Gaussova eliminacija, ki ustvari rezultat zmanjšane vrstno-echelonske matrike, se včasih imenuje Gauss-Jordanova eliminacija.

AlegsaOnline.com - 2020 / 2025 - License CC3