Gaussova eliminacijska metoda

V matematiki je Gaussova eliminacija (imenovana tudi redukcija vrstic) metoda, ki se uporablja za reševanje sistemov linearnih enačb. Imenuje se po Carlu Friedrichu Gaussu, slavnem nemškem matematiku, ki je o tej metodi pisal, vendar je ni izumil.

Za izvedbo Gaussove eliminacije se koeficienti členov v sistemu linearnih enačb uporabijo za oblikovanje vrste matrike, ki se imenuje razširjena matrika. Nato se za poenostavitev matrike uporabijo osnovne vrstne operacije. Uporabljajo se tri vrste vrstnih operacij:

Tip 1: Zamenjava ene vrstice z drugo.

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

Tip 3: dodajanje ali odvzemanje vrstice iz druge vrstice.

Cilj Gaussove eliminacije je dobiti matriko v vrstično-ekelonski obliki. Č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. Nekatere definicije Gaussove eliminacije pravijo, da mora biti rezultat matrike v reducirani vrstično-ekelonski obliki. To pomeni, da je matrika v vrstično-echelonski obliki in da je edini neničelni člen v vsaki vrstici 1. Gaussova eliminacija, ki ustvari reduciran vrstično-echelonski rezultat matrike, se včasih imenuje Gauss-Jordanova eliminacija.

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}}} ${\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]} $\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}}} ${\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]} $\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}}} ${\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}} $R_{2}+{\frac {3}{2}}R_{1}\rightarrow R_{2}$ R 3 + R 1 → R 3 {\displaystyle R_{3}+R_{1}\rightarrow R_{3}} $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]} $\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}}} ${\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}} $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]} $\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}}} ${\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}} $R_{2}+{\frac {1}{2}}R_{3}\rightarrow R_{2}$ R 1 - R 3 → R 1 {\displaystyle R_{1}-R_{3}\rightarrow R_{1}} $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]} $\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}}} ${\begin{alignedat}{7}2x&&\;+&&y\;&&&&\;\;&&=\;&&7&\\&&&&y\;&&&&\;\;&&=\;&&3&\\&&&&&&&&\;z\;&&\;=\;&&-1&\end{alignedat}}$	2 R 2 → R 2 {\displaystyle 2R_{2}\rightarrow R_{2}} $2R_{2}\rightarrow R_{2}$ R 3 → R 3 {\displaystyle -R_{3}\rightarrow R_{3}} $-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]} $\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}}} ${\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}} $R_{1}-R_{2}\rightarrow R_{1}$ 1 2 R 1 → R 1 {\displaystyle {\frac {1}{2}}R_{1}\rightarrow R_{1}} ${\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]} $\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.