Direkte und indirekte Methoden zur Lösung linearer Gleichungssysteme

Direkte Methoden

1a) Gauß-Eliminationsmethode

Die Gauß-Eliminationsmethode besteht darin, die Matrix in eine äquivalente Matrix mit Nullen unterhalb der Diagonalen von A zu transformieren. Die erste Gleichung hat dann n Variablen, die zweite n-1, bis man zur letzten Gleichung gelangt, die nur noch eine Variable hat. Sind die Nullen erzeugt, werden die Werte der Variablen, beginnend mit der letzten, sukzessive berechnet und in die vorherigen Gleichungen eingesetzt, wodurch das System gelöst wird.

1b) Gauß-Jordan-Methode

Die Gauß-Jordan-Methode zielt darauf ab, anstelle einer Dreiecksmatrix eine Diagonalmatrix zu erhalten. Die Variablen werden direkt aus dem entwickelten System ohne weitere Substitutionen ermittelt. Diese Einsparung im letzten Schritt geht auf Kosten einer (leichten) Erhöhung der Komplexität des Algorithmus im Zwischenschritt, da wir sowohl mit den Elementen der Matrix oberhalb als auch unterhalb der Diagonalen Nullen erzeugen müssen.

Indirekte Methoden

2a) Jacobi-Verfahren

Das Jacobi-Verfahren wandelt das ursprüngliche System in ein anderes um (identisch mit der Formel, die wir bei Gauß gesehen haben), da wir die exakte Lösung nicht kennen, nehmen wir ursprüngliche Werte an. Aus diesen ersten Werten erhalten wir eine Reihe von Werten, indem wir die Formeln mehrfach anwenden, bis zu einer maximalen Anzahl von Iterationen oder bis der Wert in einem Schritt, mit Ausnahme eines sehr kleinen Epsilon, gleich dem im vorherigen Schritt erhaltenen Wert ist. Die Kodierung eines Verfahrens, das diese Methode verwendet (A, n, X), basiert auf einem beliebigen Startvektor, z. B.: X = [0,0,0 ....., 0], wobei bei jedem Schritt "k" ein neuer Vektor X erhalten wird, der der exakten Lösung näher kommt. Es lässt sich zeigen, dass das Verfahren konvergiert, solange die Matrix diagonal dominant ist, d. h. in allen Zeilen ist das Element der Hauptdiagonalen, in absoluten Zahlen, größer als die Summe der absoluten Werte der restlichen Elemente. Dies ist verständlich, wenn wir bedenken, dass bei Erfüllung dieser Bedingung der Term der Summe in der obigen Formel im Vergleich zum unabhängigen Term klein ist, daher wird dieser Term in den Iterationen dominant.

2b) Gauß-Seidel-Methode

In der Jacobi-Methode wird jeder Vektor der Folge gleichzeitig berechnet. Um eine schnellere Konvergenz zu erreichen, werden die Werte von x, die wir erhalten, für die Berechnung der folgenden Komponenten verwendet, bevor die Iteration beendet ist. Anstatt alle Werte von X in der ersten Iteration zu verwenden, nutzen wir sie für die erste Komponente und verwenden den Wert in der folgenden Berechnung der aktuellen Iteration. Das Gleiche gilt für die restlichen Komponenten. Diese Methode konvergiert genau dann, wenn auch die Jacobi-Methode konvergiert. Die beiden beschriebenen Methoden sind in dem Fall anwendbar, dass wir Matrizen mit beträchtlichen Dimensionen oder mit vielen Nullen haben (z. B. Matrizen, die durch Diagonalblöcke mit "n" sehr groß gebildet werden).