Die Tschebyschow-Iteration (nach Pafnuti Lwowitsch Tschebyschow) ist ein numerisches Verfahren zur Lösung von linearen Gleichungssystemen mit und wird auch als semi-iteratives Verfahren bezeichnet, da sie als ein einfacher Iterationsschritt eines Splitting-Verfahrens mit nachgeschalteter Extrapolation interpretiert werden kann. Grundlage ist die Rekursionsformel für Tschebyschow-Polynome. Das Verfahren erreicht für symmetrische positiv definite Matrizen die Geschwindigkeit des CG-Verfahrens, kann aber auch für unsymmetrische Matrizen angepasst werden, wenn Informationen über die Lage der Eigenwerte vorliegen.
Das semi-iterative Verfahren Bearbeiten
Grundlage ist die Idee, dass man aus der Vektorfolge , die man mit einem Splitting-Verfahren erhält, durch allgemeine Linearkombination eine bessere Folge
konstruiert. Um eine exakte Lösung nicht wieder zu verlassen, ist erforderlich. Da für die Fehler beim Splitting-Verfahren gilt, erhält man für den neuen Fehler
Also wird der Startfehler mit dem Matrix-Polynom multipliziert mit dem Ziel, diesen zu verkleinern. Hat die Matrix nur reelle Eigenwerte in einem Intervall , ist dasjenige Polynom mit kleinster Schranke für den Spektralradius ein verschobenes Tschebyschow-Polynom . Da für letztere eine zweistufige Rekursionsformel gilt, kann die Tschebyschow-Iteration ebenfalls als zweistufiges Verfahren ausgeführt werden:
mit den Parametern
In der Vorschrift für ist zu erkennen, dass in der Klammer ein optimaler Schritt des Richardson-Verfahrens steht.
Für eine symmetrisch-definite Matrix ist diese Iteration eng verwandt mit dem CG-Verfahren, welches aber die Parameter anders bestimmt, und besitzt die gleiche Konvergenzgeschwindigkeit. Die Tschebyschow-Iteration kann aber auch auf unsymmetrische Matrizen mit komplexen Eigenwerten angewendet werden, wenn diese sich in einer Ellipse einschließen lassen, welche den Nullpunkt nicht enthält.
Konvergenz des Verfahrens Bearbeiten
Für eine symmetrische, positiv definite Matrix gilt in der euklidischen Norm die Fehlerschranke
ähnlich dem CG-Verfahren, wobei eine Schranke für die Konditionszahl der Matrix ist . Für geht der Fehler offenbar gegen null.
Der Konvergenzvorteil gegenüber dem einfachen Splitting-Verfahren bzw. Richardson-Verfahren ist, dass die Konvergenz nur von der Wurzel der Kondition abhängt. Bei komplexen Eigenwerten geht dieser Vorteil umso mehr verloren, je runder die zur Einschließung benötigte Ellipse wird. Bei Einschließung mit einem Kreis schließlich ist das einfache Verfahren mit optimal.
Literatur Bearbeiten
- Gene H. Golub, Charles van Loan: Matrix Computations, Johns Hopkins University Press.