Prinzip des Gaußschen Eliminationsverfahrens

Durch die elementaren Umformungen

1. Vertauschen von Zeilen und
2. Addition eines Vielfachen einer Zeile zu einer anderen Zeile

wird das System (19.26) in ein sogenanntes gestaffeltes Gleichungssystem

überführt. Da dabei nur äquivalente Umformungen vorgenommen werden, besitzt dieselbe Lösung wie . Man erhält sie aus (19.27):

Die durch die Formel (19.28) angegebene Vorschrift nennt man Rückwärtseinsetzen, da die Gleichungen von (19.27) in der umgekehrten Reihenfolge ihrer Entstehung benutzt werden.

Der Übergang von zu erfolgt in n-1 sogenannten Eliminationsschritten, deren Durchführung am ersten Schritt gezeigt werden soll. Dieser überführt die Matrix in die Matrix :

Dabei ist wie folgt vorzugehen:

1. Man bestimme ein . Falls kein solches existiert, stop: ist singulär. Andernfalls heißt a_r1 Pivot.
2. Man vertausche die 1. und die r-te Zeile von und . Das Ergebnis sind die Matrix und der Vektor .
3. Man subtrahiere für das l_i1-fache der 1. Zeile von der i-ten Zeile der Matrix .

Als Ergebnis erhält man die Matrix und analog die neue rechte Seite mit folgenden Elementen:

a_ik⁽¹⁾ =

b_i⁽¹⁾ = (19.30)

Die in der Matrix (19.29) eingerahmte Teilmatrix ist vom Typ (n-1,n-1) und wird analog zu behandelt; usw. Diese Vorgehensweise bezeichnet man als GAUSSsches Eliminationsverfahren oder GAUSSschen Algorithmus.