Tschebyschow-Iteration

Verfahren zur Lösung von linearen Gleichungssystemen

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.