Gauss-eliminatie

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

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.

Gauss-Jordaneliminatie[bewerken]

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

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).

Voorbeeld[bewerken]

De onderstaande matrix wordt met Gauss-eliminatie geveegd:

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

Oplossen van vergelijkingen[bewerken]

Een belangrijke toepassing van Gauss-eliminatie is het oplossen van stelsels van lineaire vergelijkingen.

Als voorbeeld lossen we het volgende stelsel van lineaire vergelijkingen op:

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

Dit schrijven we aldus op als een matrix:

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

We gaan nu een Gauss-eliminatie toepassen op het stuk links van de lijn (voor de duidelijkheid hebben we dezelfde matrix genomen als hierboven), waarbij we het stuk rechts ook mee laten veranderen. Merk op dat de wijzigingen gebruikt voor de Gauss-eliminatie (2 rijen verwisselen, een rij met een constante (niet 0) vermenigvuldigen, een veelvoud van een rij optellen bij of aftrekken van een andere rij) het stelsel omzetten in een equivalent stelsel. Als we dezelfde stappen als hierboven uitvoeren, levert dat:

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

Dit levert dus het stelsel:

-2x -4y      = 4
    -3y + 6z = 9
          4z = 8

Door van onder naar boven te werken, kunnen x , y en z nu gemakkelijk berekend worden:

4z=8, dus z=2
-3y+6z=9 ⇒ -3y+12=9 ⇒ -3y=-3, dus y=1
-2x-4y=4 ⇒-2x-4=4 ⇒ -2x=8, dus x=-4