Gauss-eliminatie

Gauss-eliminatie, genoemd naar Carl Friedrich Gauss, maar niet door hem ontdekt, is een techniek om een stelsel van lineaire vergelijkingen op te lossen. De techniek leent zich daardoor ook om een willekeurige matrix in echelonvorm te brengen. De techniek bestaat erin achtereenvolgens een van de volgende elementaire rijoperaties toe te passen op de betreffende vergelijkingen of de matrix:

• twee rijen verwisselen;
• een rij met een scalair ongelijk aan 0 vermenigvuldigen;
• bij een rij een veelvoud van een andere rij optellen (of aftrekken).

Het toepassen van deze eliminatiewijze wordt wel "het vegen van een matrix" genoemd, omdat steeds een kolom wordt 'geveegd' om te zorgen dat er maar één rij is die in die kolom een waarde heeft. Na toepassing ontstaat een bovendriehoeks-matrix waarbij (indien er een oplossing bestaat) de oplossing kan worden gevonden door de oplossing van de onderste rij steeds te substitueren in de rij erboven.

Bij de Gauss-Jordaneliminatie wordt de Gauss-eliminatie nogmaals uitgevoerd, maar dan 'andersom', zodat ook de rechterbovenhoek wordt schoongeveegd en er (als er een oplossing bestaat) een eenheidsmatrix overblijft, zodat de oplossing direct afgelezen kan worden.

Veel wiskundige computerprogramma's (waaronder MATLAB) en grafische rekenmachines (zoals de TI-83 van Texas Instruments en de ClassPad 300 van Casio) hebben een operatie die een matrix door middel van Gauss-eliminatie kan omzetten naar de rijgereduceerde echelonvorm (rref).

Het volgende stelsel lineaire vergelijkingen wordt opgelost met Gauss-eliminatie.

${\displaystyle {\begin{aligned}-2&x&-4&y&&=&4\\2&x&+&y&+6z&=&5\\-2&x&-2&y&&=&6\end{aligned}}}$

Tel de eerste vergelijking op bij de tweede:

${\displaystyle {\begin{aligned}-2&x&-4&y&&=&4\\0&x&-3&y&+6z&=&9\\-2&x&-2&y&&=&6\end{aligned}}}$

Trek van de derde vergelijking de eerste af:

${\displaystyle {\begin{aligned}-2&x&-4&y&&=&4\\0&x&-3&y&+6z&=&9\\0&x&+2&y&&=&2\end{aligned}}}$

Als laatste stap wordt 2/3 maal de tweede vergelijking bij de derde opgeteld:

${\displaystyle {\begin{aligned}-2&x&-4&y&&=&4\\0&x&-3&y&+6z&=&9\\0&x&+0&y&+4z&=&8\end{aligned}}}$

Deze vergelijkingen kunnen nog vereenvoudigd worden tot:

${\displaystyle {\begin{aligned}&x&+2&y&&&=&&-2\\&&&y&-2&z&=&&-3\\&&&&&z&=&&2\end{aligned}}}$

Door van onder naar boven te werken, kunnen ${\displaystyle x,\ y}$ en ${\displaystyle z}$ nu gemakkelijk berekend worden:

${\displaystyle {\begin{array}{rcl}z&=&2\\y-2\times 2=-3\ \ \Rightarrow \ \ y-4=-3\ \ \Rightarrow \ \ y&=&1\\x+2\times 1=-2\ \ \Rightarrow \ \ x+2=-2\ \ \Rightarrow \ \ x&=&-4\end{array}}}$

De hele procedure kan als volgt in matrixvorm geschreven worden.

${\displaystyle {\begin{bmatrix}-2&-4&0&|&4\\2&1&6&|&5\\-2&-2&0&|&6\end{bmatrix}}}$

De bovenstaande stappen leiden achtereenvolgens tot:

${\displaystyle {\begin{bmatrix}-2&-4&0&|&4\\0&-3&6&|&9\\-2&-2&0&|&6\end{bmatrix}}}$

${\displaystyle {\begin{bmatrix}-2&-4&0&|&4\\0&-3&6&|&9\\0&2&0&|&2\end{bmatrix}}}$

${\displaystyle {\begin{bmatrix}-2&-4&0&|&4\\0&-3&6&|&9\\0&0&4&|&8\end{bmatrix}}}$

${\displaystyle {\begin{bmatrix}1&2&0&|&-2\\0&1&-2&|&-3\\0&0&1&|&2\end{bmatrix}}}$

Dit voert natuurlijk tot hetzelfde stelsel als boven.

Als het er alleen om gaat een matrix te vegen tot de echelonvorm, ziet de procedure er zo uit:

${\displaystyle {\begin{bmatrix}-2&-4&0\\2&1&6\\-2&-2&0\end{bmatrix}}}$

Tel de eerste rij op bij de tweede; de matrix gaat over in:

${\displaystyle {\begin{bmatrix}-2&-4&0\\0&-3&6\\-2&-2&0\end{bmatrix}}}$

Trek van de derde rij de eerste rij af; de matrix gaat over in:

${\displaystyle {\begin{bmatrix}-2&-4&0\\0&-3&6\\0&2&0\end{bmatrix}}}$

Als laatste stap tellen we 2/3 maal de tweede rij bij de derde op:

${\displaystyle {\begin{bmatrix}-2&-4&0\\0&-3&6\\0&0&4\end{bmatrix}}}$

De matrix is nu in echelonvorm. Men vereenvoudigt deze vorm nog wel zo dat de rijen na de nullen met een 1 beginnen:

${\displaystyle {\begin{bmatrix}1&2&0\\0&1&-2\\0&0&1\end{bmatrix}}}$.