Lineares Gleichungssystem mit n Gleichungen und n Unbekannten

Betrachtet wird eine Beziehung der Form

Lineares Gleichungssystem

mit quadratischer Matrix A, ein Gleichungssystem mit n Gleichungen und n Unbekannten, das - ausführlich aufgeschrieben - so aussieht:

Lineares Gleichungssystem in ausführlicher Schreibweise

Es soll zunächst vorausgesetzt werden, dass nicht alle bi gleich Null sind (die so genannten homogenen Gleichungssysteme, für die das erfüllt ist, erfordern eine gesonderte Betrachtung) und dass die Matrix A regulär ist (ihre Determinante ist ungleich Null). Dann hat das lineare Gleichungssystem eine eindeutige Lösung.

Idee des Gaußschen Algorithmus

Der Gaußsche Algorithmus verfolgt folgende Strategie:

Durch geeignete Linearkombination der Gleichungen (Multiplikation einer Gleichung mit einem geeigneten Faktor und Subtraktion von einer anderen Gleichung) wird die Koeffizientenmatrix A sukzessive zu einer Rechtsdreiecksmatrix R, dabei ändern sich auch die Werte auf der rechten Seite, aus b wird b* (man sieht leicht ein, dass diese Operationen an der Lösung des Gleichungssystems nichts ändern).

Aus dem so entstehenden "gestaffelten System"

Gestaffeltes System

bzw.

Gestaffeltes System, Ausgangspunkt für das Rückwärtseinsetzen

kann dann jeweils genau eine Unbekannte aus einer Gleichung (beginnend mit xn aus der letzten Gleichung) berechnet werden.

Einfaches Beispiel

Das lineare Gleichungssystem

Beispiel für ein kleines Gleichungssystem

wird schrittweise nach dem Gaußschen Algorithmus gelöst.

1. Eliminationsschritt:

Gleichungssystem nach dem 1. Eliminationsschritt

2. Eliminationsschritt:

Gleichungssystem nach dem 2. Eliminationsschritt (gestaffeltes System)

Rückwärtseinsetzen:

Entsprechend den Eigenschaften von Determinanten (Wert einer Determinante ändert sich nicht, wenn man von einer Zeile ein Vielfaches einer anderen Zeile subtrahiert), hat sich der Wert der Determinante der Matrix A beim Eliminationsprozess nicht geändert (die Determinante der Dreiecksmatrix R hat den gleichen Wert wie die Determinante der Matrix A). Nach den Regeln des Laplaceschen Entwicklungssatzes ist der Wert der Determinante einer Dreiecksmatrix besonders einfach zu berechnen. Man verifiziert leicht, dass dieser sich aus dem Produkt aller Diagonalelemente ergibt, für das Beispiel gilt also:

det (A) = 2 · (-12) · 11 = -264 .

Elimination, Zeilentausch, Singularität, Pivotisierung

Aus dem einfachen Beispiel lassen sich folgende Aussagen über den Gaußschen Algorithmus für ein Gleichungssystem mit n Gleichungen und n Unbekannten ableiten:

det (A) = (-1) z · r11 · r22 · r33 · .... · rnn