Gauß-Seidel-Verfahren

Beschreibung des Verfahrens

Gegeben ist ein lineares Gleichungssystem in n Variablen mit den n Gleichungen

Um dieses zu lösen, wird ein Iterationsverfahren durchgeführt. Gegeben sei ein Näherungsvektor x^(m) an die exakte Lösung. Nun wird die k-te Gleichung nach der k-ten Variablen x_k aufgelöst, wobei die vorher berechneten Werte des aktuellen Iterationsschritts mit verwendet werden, im Gegensatz zum Jacobi-Verfahren, bei dem nur die Werte des letzten Iterationsschrittes verwendet werden. Das heißt für den (m + 1)-ten Iterationsschritt:

Das Ergebnis der Rechnung ist ein neuer Näherungsvektor x^{(m + 1)} für den gesuchten Lösungsvektor x. Wiederholt man diesen Vorgang, gewinnt man eine Folge von Werten, die sich dem Lösungsvektor im Falle der Konvergenz immer mehr annähern:

Das Gauß-Seidel-Verfahren ist inhärent sequentiell, das heißt bevor eine Gleichung aufgelöst werden kann, müssen die Ergebnisse der vorherigen Gleichungen vorliegen. Es ist damit nicht zur Nutzung auf Parallelrechnern geeignet.

Als Algorithmusskizze mit Abbruchbedingung ergibt sich:

wiederhole

fehler := 0

für k = 1 bis n

fehler := max(fehler, | x^{(m + 1)}_k - x^(m)_k | )

nächstes k

m := m + 1

bis fehler < fehlerschranke

Dabei wurde die Erstbelegung des Variablenvektors, die willkürlich gewählt werden kann, und eine Fehlerschranke als Eingangsgrößen des Algorithmus angenommen, die Näherungslösung ist die vektorielle Rückgabegröße. Die Fehlerschranke misst hier, welche Größe die letzte Änderung des Variablenvektors hatte. Als Bedingung für die Durchführbarkeit des Algorithmus lässt sich festhalten, dass die Diagonalelemente a_kk von Null verschieden sein müssen.

Bei dünnbesetzten Matrizen reduziert sich der Aufwand des Verfahrens pro Iteration deutlich.

Copyright- und Lizenzinformationen: Diese Seite basiert auf dem Artikel Gauß-Seidel-Verfahren aus der freien Enzyklοpädιe Wιkιpedιa und steht unter der Lizenz Creative Commons CC-BY-SA 3.0 Unported (Kurzfassung). Liste der Autoren

Anbieterkennzeichnung