Gauß-Jordan-Algorithmus

Der Gauß-Jordan-Algorithmus ist ein Algorithmus aus den mathematischen Teilgebieten der linearen Algebra und Numerik. Mit dem nach Carl Friedrich Gauß und Wilhelm Jordan benannten Verfahren lässt sich die Lösung eines linearen Gleichungssystems berechnen. Es ist eine Erweiterung des gaußschen Eliminationsverfahrens, bei dem in einem zusätzlichen Schritt das Gleichungssystem bzw. dessen erweiterte Koeffizientenmatrix auf die reduzierte Stufenform gebracht wird. Daraus lässt sich dann die Lösung direkt ablesen.

Umformungsschritte

1. Man sucht in der ersten Spalte ein von Null verschiedenes Element und vertauscht ggf. diese Zeilen, sodass an der Position (1,1) ein von :Null verschiedenes Element steht.
2. Man dividiere die erste Zeile durch dieses von Null verschiedene Element.
3. Man subtrahiere von den übrigen Zeilen entsprchende Vielfache der ersten Zeile mit dem Ziel, dass die erste Spalte der Matrix die Form S = (1 0 . . . 0) besitzt.
4. Dieses Verfahren wir mit der Restmatrix fortgesetzt.
5. Ziehe danach von den darüberliegenden Zeilen entsprechende Vielfache ab, sodass über einer führenden 1 nur Nullen stehen.

Beispiel

Eine Parabel soll durch folgende Punkte laufen:

1. (x, y) = (1; 0) ,
2. (x, y) = (2; 1) ,
3. (x, y) = (3; 3) .

Die allgemeine Grundgleichung der Parabel lautet:

$ax^{2}+bx+c=y$.

Durch Einsetzen jeweils eines x-y-Paares ergeben sich drei Gleichungen:

$a+b+c=0$ ;

$4a+2b+c=1$ ;

$9a+3b+c=3$ .

Die drei Gleichungen enthalten drei Unbekannte, wodurch das Gleichungssystem lösbar wird. Anstatt nun durch Einsetzen und Gleichsetzen zu lösen, werden die Faktoren in eine Matrix geschrieben und die Matrix so umgeformt, dass man die Lösung ablesen kann.

In der ersten Spalte stehen die Faktoren der Variable a, in der zweiten die der Variable b, in der dritten die der Variable c und letztendlich die Faktoren der anderen Gleichungsseite:

${\begin{pmatrix}1&1&1&|&0\\4&2&1&|&1\\9&3&1&|&3\end{pmatrix}}$

Es werden nun folgende Zeilentransformationen vorgenommen:

• Zu Zeile 2 wird addiert: -4 * Zeile 1.
• Zu Zeile 3 wird addiert: -9 * Zeile 1.

Damit ergibt sich:

${\begin{pmatrix}1&\ 1&\ 1&|&0\\0&-2&-3&|&1\\0&-6&-8&|&3\end{pmatrix}}$

• Zu Zeile 3 wird addiert: -3 * Zeile 2.
• Zeile 2 wird dividiert durch -2.

${\begin{pmatrix}1&1&1&|&\ 0\\0&1&{3 \over 2}&|&-{1 \over 2}\\0&0&1&|&\ 0\end{pmatrix}}$

• Zu Zeile 1 wird addiert: -1 * Zeile 3.
• Zu Zeile 2 wird addiert: -3/2 * Zeile 3.

${\begin{pmatrix}1&1&0&|&\ 0\\0&1&0&|&-{1 \over 2}\\0&0&1&|&\ 0\end{pmatrix}}$

• Zu Zeile 1 wird addiert: -1 * Zeile 2.

${\begin{pmatrix}1&0&0&|&\ {1 \over 2}\\0&1&0&|&-{1 \over 2}\\0&0&1&|&\ 0\end{pmatrix}}$

Diese Matrix wird auf unsere Gleichungen zurück übertragen. Wir erhalten:

$a={\frac {1}{2}}\;;\ b=-{\frac {1}{2}}\;;\ c=0$ .

Die gesuchte Funktion lautet also:

${1 \over 2}x^{2}-{1 \over 2}x=y$.

Literatur

• Howard Anton: Lineare Algebra. Spektrum Akademischer Verlag GmbH Heidelberg, Berlin, IBAN 3-8274-0324-3

Weblinks

• Applet zum Lösen linearer Gleichungssysteme