15.4.2  Lösungsschritte des Gauß’schen Algorithmus

Die Lösung eines linearen Gleichungssystems A · x^→ = c^→ erfolgt durch Umformung in zwei, ggf. drei Schritten:
I. Vorwärtselimination mit
Ia. eventueller Pivotisierung (d.h. Vertauschen von Zeilen, bis die Diagonalelemente ≠ 0)
II. Rückwärtselimination
I. Vorwärtselimination

1. Eliminationsschritt: (a₁₁≠ 0)
   

   subtrahiere	a21 a11-fache der 1.Zeile von 2.Zeile
   ⋮	a31 a11-fache der 1.Zeile von 3.Zeile
   ⋮	⋮

   
   Durch den ersten Eliminationsschritt entstehen in der 1. Spalte der Matrix Nullen, außer a₁1 sind alle a_i1 = 0.
2. Eliminationsschritt: (a₂₂≠ 0)
   

   subtrahiere	a32 a22-fache der 2.Zeile von 3.Zeile
   ⋮	a42 a22-fache der 2.Zeile von 4.Zeile
   ⋮	⋮

3. Solange wiederholen, bis die Dreiecksform vorliegt. (Die Koeffizienten der Matrix in Dreiecksform werden ab hier der Übersichtlichkeit halber mit Koeffizienten a′_ik bzw. c′_i bezeichnet.)

Ia. Pivotisierung

1. Das Gauß-Verfahren versagt, falls das Diagonalelement oder Pivotelement (engl. für Dreh- und Angelpunkt) a_kk eines Eliminationsschrittes gleich Null ist, a_kk = 0 (Abbruch des Verfahrens bei Division durch Null).
2. Pivotsuche: Ist ein Diagonalelement a_kk = 0, so vertauscht man die Pivot-Zeile k vor Ausführung des k-ten Eliminationsschrittes mit derjenigen Zeile m > k, die den betragsmäßig größten Koeffizienten für x_k besitzt:

3. Neue Pivotzeile m, neues Pivotelement a_mk.

II. Rückwärtselimination
Aus der Dreiecksform werden die Lösungen x_i durch schrittweises Rückwärtseinsetzen gewonnen:

1. Zuerst die unterste Zeile nach x_n auflösen.
2. Die anderen Elemente x_i, i= n − 1, ⋯ , 1 des Lösungsvektors x bestimmt man dann rekursiv mit der Gleichung x_n = c′_n/ a′_nn , x_i = c′_i/ a′_ii − ∑_k=i+1ⁿ x_k· a′_ik/ a′_ii , i=n−1, ⋯,1
   

.
Sei A eine 4x4-Matrix, dann lautet das Gleichungssystem A· x^→ = c^→ mit dem unbekannten Vektor x^→ = ( x₋1,x₂, ⋯ x_n)^T:

x₄ erhält man aus der letzten Zeile: x₄ = c₄ / a₄₄
 

Der Wert für x₄ wird in die vorletzte Zeile eingesetzt, diese nach x₃ aufgelöst: x₃ = c₃−a₃₄x₄ / a₃₃ .
.
Das gleiche Schema wird auf die darüberliegenden Zeilen angewandt, bis alle Werte von x^→ bestimmt sind.