Gauss-Jordaneliminatie

Gauss-Jordaneliminatie of methode van Gauss-Jordan is een uitbreiding van Gauss-eliminatie, een techniek waarmee een willekeurige matrix tot echelonvorm (trapvorm) kan worden teruggebracht. Met deze techniek kunnen onder andere lineaire vergelijkingen opgelost worden. De techniek bestaat, net als Gauss-eliminatie, uit rijoperaties op de matrix. Het verschil met Gauss-eliminatie is dat de matrix niet alleen van boven naar onder wordt geveegd, waarbij de getallen onder de diagonaal 0 worden, maar ook van onder naar boven, zodat er uiteindelijk alleen getallen op de diagonaal overblijven.

Gauss-Jordaneliminatie is aanzienlijk minder efficiënt dan Gauss-eliminatie met terugsubstitutie bij het oplossen van een stelsel van lineaire vergelijkingen. De methode is echter uitstekend geschikt voor het berekenen van inverse matrices.

De methode is genoemd naar Carl Friedrich Gauss en Wilhelm Jordan.

Berekenen van de inverse van een matrix

Gauss-Jordaneliminatie kan worden gebruikt om de inverse van een matrix uit te rekenen. Voor de inverse ${\displaystyle A^{-1}}$ van de vierkante matrix ${\displaystyle A}$ geldt onder andere dat

${\displaystyle AA^{-1}=I}$,

met I de betrokken eenheidsmatrix. Door de vergelijking op te lossen met Gauss-Jordaneliminatie kan de inverse gevonden worden.

Gauss-Jordaneliminatie in software

Matlab

Softwareprogramma's zoals Matlab ondersteunen het Gauss-Jordaneliminatieproces. In Matlab kan een vergelijking

${\displaystyle Ax=B}$

met Gauss-Jordaneliminatie opgelost worden voor ${\displaystyle x}$ met:

${\displaystyle x=A\setminus B}$

Een matrix ${\displaystyle A}$ kan geveegd worden met Gauss-Jordaneliminatie met het commando: rref(A) (rref staat voor Reduced Row Echelon Form).

De inverse

${\displaystyle B=A^{-1}}$

van een matrix kan worden gevonden met het commando: B = A\eye(n), waarin ${\displaystyle n}$ het aantal rijen (en aantal kolommen, want ${\displaystyle A}$ is vierkant) voorstelt. Het commando: 'eye' levert de eenheidsmatrix op en met de backslash ('\') wordt de vergelijking opgelost voor de eenheidsmatrix.

Voorbeeld

Het volgende stelsel vergelijkingen wordt opgelost met Gauss-Jordaneliminatie.

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

Daartoe wordt de bijbehorende uitgebreide matrix

${\displaystyle B={\begin{bmatrix}3&2&-1&4\\1&1&1&6\\2&-2&3&7\end{bmatrix}}}$

geveegd.

Het element ${\displaystyle B_{1,1}=3\neq 0}$, dus hoeft de eerste rij niet met een andere rij omgewisseld te worden. Vermenigvuldig nu voor het gemak de tweede en de derde rij met ${\displaystyle B_{1,1}=3}$:

${\displaystyle {\begin{bmatrix}3&2&-1&4\\3&3&3&18\\6&-6&9&21\end{bmatrix}}}$

Trek vervolgens de eerste rij van de tweede af en 2 keer de eerste rij van de derde:

${\displaystyle {\begin{bmatrix}3&2&-1&4\\0&1&4&14\\0&-10&11&13\end{bmatrix}}}$

Nu staan in de eerste kolom onder de hoofddiagonaal nullen, en gaat men verder met de tweede rij. Het element ${\displaystyle B_{2,2}=1\neq 0}$, dus hoeft de tweede rij niet met de derde omgewisseld te worden.

Trek 2 keer de tweede rij af van de eerste en tel 10 keer de tweede rij bij de derde op:

${\displaystyle {\begin{bmatrix}3&0&-9&-24\\0&1&4&14\\0&0&51&153\end{bmatrix}}}$

Deel rij 1 door 3 en rij 3 door 51.

${\displaystyle {\begin{bmatrix}1&0&-3&-8\\0&1&4&14\\0&0&1&3\end{bmatrix}}}$

Tel 3 keer de derde rij op bij de eerste en trek 4 keer de derde rij af van de tweede:

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

Daarmee is de eliminatie voltooid en het stelsel opgelost:

${\displaystyle x=1,y=2,z=3}$

De hier gevolgde procedure is niet systematisch. Een systematische methode deelt de eerste rij door de zogeheten spil ${\displaystyle B_{1,1}=3}$ zodat op die plaats direct het getal 1 komt te staan:

${\displaystyle {\begin{bmatrix}1&2/3&-1/3&4/3\\1&1&1&6\\2&-2&3&7\end{bmatrix}}}$

Trek nu voldoende vaak rij 1 af van de rijen 2 en 3 zodat in de eerste kolom nullen komen te staan:

${\displaystyle {\begin{bmatrix}1&2/3&-1/3&4/3\\0&1/3&4/3&14/3\\0&-10/3&11/3&13/3\end{bmatrix}}}$

Deel nu de tweede rij door de spil op positie (2,2):

${\displaystyle {\begin{bmatrix}1&2/3&-1/3&4/3\\0&1&4&14\\0&-10/3&11/3&13/3\end{bmatrix}}}$

Trek voldoende vaak rij 2 af van de rijen 1 en 3 zodat in de tweede kolom nullen komen te staan:

${\displaystyle {\begin{bmatrix}1&0&-3&-8\\0&1&4&14\\0&0&51/3&153/3\end{bmatrix}}}$

Deel de derde rij door de spil op positie (3,3):

${\displaystyle {\begin{bmatrix}1&0&-3&-8\\0&1&4&14\\0&0&1&3\end{bmatrix}}}$

Trek voldoende vaak rij 3 af van de rijen 1 en 2 zodat in de derde kolom nullen komen te staan:

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

Het eindresultaat is natuurlijk hetzelfde.