Gauss-eliminatie

Gauss-eliminatie is een techniek om een stelsel van lineaire vergelijkingen op te lossen, vernoemd naar Carl Friedrich Gauss, maar niet door hem ontdekt. De techniek leent zich daardoor ook om een willekeurige (bijvoorbeeld inverse) 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 c ≠ 0 vermenigvuldigen;
• bij een rij een veelvoud van een andere optellen of aftrekken.

Het toepassen van deze eliminatiewijze wordt ook 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.

Gauss-Jordaneliminatie

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.

Gauss-eliminatie in software

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 d.m.v. Gauss-eliminatie kan omzetten naar de rijgereduceerde echelonvorm (rref).

Voorbeeld

We lossen het volgende stelsel lineaire vergelijkingen op:

3x + 2y -  z = 4
 x +  y +  z = 6
2x - 2y + 3z = 7

Trek 2 keer de 2e af van de 3e:

3x + 2y -  z =  4
 x +  y +  z =  6
   - 4y +  z = -5

Vermenigvuldig de 2e met 3:

3x + 2y -  z =  4
3x + 3y + 3z = 18
   - 4y +  z = -5

Trek de 1e af van de 2e:

3x + 2y -  z =  4
      y + 4z = 14
   - 4y +  z = -5

Tel de 2e 4 keer op bij de 3e:

3x + 2y -  z =  4
      y + 4z = 14
         17z = 51

De nu ontstane "driehoek" (de echelonvorm) kan direct opgelost worden:

           z = 51/17 = 3
      y + 4z = y + 12 =14, 

dus

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

dus

           x = 1

Voorbeeld

Stel dat de matrix A gedefinieerd wordt door:

$A=\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:

$\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:

$\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:

$\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:

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