Gauß-Seidel-Verfahren

Diagonaldominanz und Konvergenz

Das Verfahren konvergiert linear, wenn der Spektralradius der Iterationsmatrix T = - (D + L)^-1 U kleiner 1 ist. In diesem Falle ist der Fixpunktsatz von Banach bzw. der Konvergenzsatz der Neumann-Reihe (auf eine hinreichend große Potenz von T) anwendbar und das Verfahren konvergiert. Im gegenteiligen Fall divergiert das Verfahren, wenn die rechte Seite des Gleichungssystems einen Anteil eines Eigenvektor zu einem Eigenwert mit Betrag größer als 1 beinhaltet. Je geringer der Spektralradius, desto schneller konvergiert das Verfahren.

Die Bestimmung des Spektralradius ist für den praktischen Einsatz meist ungeeignet, weswegen über die hinreichende Bedingung, dass eine Matrixnorm der Verfahrensmatrix T kleiner als 1 sein muss, bequemere Kriterien gefunden werden können. Diese Matrixnorm ist gleichzeitig die Kontraktionskonstante im Sinne des banachschen Fixpunktsatzes.

Im Falle, dass sowohl D^-1 U als auch D^-1 L "kleine" Matrizen bzgl. der gewählten Matrixnorm sind, gibt es die folgende Abschätzung der Matrixnorm für (siehe Neumann-Reihe für den ersten Faktor):

Der letzte Ausdruck ist für ||D^-1 L|| + ||D^-1 U|| < 1 ebenfalls kleiner als 1. Obwohl die Konvergenzbedingung diejenige des Jacobi-Verfahrens ist, ist die so erhaltene Abschätzung der Kontraktionskonstante ||T|| des Gauß-Seidel-Verfahrens immer kleinergleich der entsprechenden Abschätzung der Kontraktionskonstante des Jabobi-Verfahrens.

Das einfachste und gebräuchlichste hinreichende Konvergenzkriterium der Diagonaldominanz ergibt sich für die Supremumsnorm der Vektoren und deren induzierter Matrixnorm . Es verlangt die Erfüllung des Zeilensummenkriteriums, also der Ungleichung

für k = 1, ..., n.

Je größer die kleinste Differenz zwischen rechten und linken Seiten der Ungleichung ist, desto schneller konvergiert das Verfahren. Man kann versuchen, diese Differenz mittels Zeilen- und Spaltenvertauschungen zu vergrößern, d. h. durch Umnummerieren der Zeilen und Spalten. Dabei kann man beispielsweise anstreben, die betragsgrößten Elemente der Matrix auf die Diagonale zu bringen. Die Zeilenvertauschungen müssen natürlich auch auf der rechten Seite des Gleichungssystems vollzogen werden.

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