Tschebyschow-Iteration

Die Tschebyschow-Iteration (nach Pafnuti Lwowitsch Tschebyschow) ist ein numerisches Verfahren zur Lösung von linearen Gleichungssystemen A x = b {\displaystyle Ax=b} mit A ∈ R n × n {\displaystyle A\in \mathbb {R} ^{n\times n}} 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.

Grundlage ist die Idee, dass man aus der Vektorfolge ( x k ) k ≥ 0 {\displaystyle (x_{k})_{k\geq 0}} , die man mit einem Splitting-Verfahren erhält, durch allgemeine Linearkombination eine bessere Folge

y k = ∑ j = 0 k α k j x j {\displaystyle y_{k}=\sum _{j=0}^{k}\alpha _{kj}x_{j}}

konstruiert. Um eine exakte Lösung x ^ {\displaystyle {\hat {x}}} nicht wieder zu verlassen, ist ∑ j = 0 k α k j = 1 {\displaystyle \sum _{j=0}^{k}\alpha _{kj}=1} erforderlich. Da für die Fehler beim Splitting-Verfahren x k − x ^ = M k ( x 0 − x ^ ) ,   M = I − B − 1 A {\displaystyle x_{k}-{\hat {x}}=M^{k}(x_{0}-{\hat {x}}),\ M=I-B^{-1}A} gilt, erhält man für den neuen Fehler

y k − x ^ = ∑ j = 0 k α k j ( x j − x ^ ) = ∑ j = 0 k α k j M j ( x 0 − x ^ ) = p k ( M ) ( x 0 − x ^ ) . {\displaystyle y_{k}-{\hat {x}}=\sum _{j=0}^{k}\alpha _{kj}(x_{j}-{\hat {x}})=\sum _{j=0}^{k}\alpha _{kj}M^{j}(x_{0}-{\hat {x}})=p_{k}(M)(x_{0}-{\hat {x}}).}

Also wird der Startfehler x 0 − x ^ {\displaystyle x_{0}-{\hat {x}}} mit dem Matrix-Polynom p k ( M ) {\displaystyle p_{k}(M)} multipliziert mit dem Ziel, diesen zu verkleinern. Hat die Matrix A {\displaystyle A} nur reelle Eigenwerte in einem Intervall [ a , b ] , a > 0 {\displaystyle [a,b],\,a>0} , ist dasjenige Polynom mit kleinster Schranke für den Spektralradius ρ ( p k ( A ) ) {\displaystyle \rho (p_{k}(A))} ein verschobenes Tschebyschow-Polynom T k {\displaystyle T_{k}} . Da für letztere eine zweistufige Rekursionsformel gilt, kann die Tschebyschow-Iteration ebenfalls als zweistufiges Verfahren ausgeführt werden:

y 1 = y 0 + γ ( b − A y 0 ) {\displaystyle \,\!y_{1}=y_{0}+\gamma (b-Ay_{0})}

y k + 1 = ω k ( y k + γ ( b − A y k ) ) + ( 1 − ω k ) y k − 1 ,   k = 1 , 2 , … {\displaystyle y_{k+1}=\omega _{k}(y_{k}+\gamma (b-Ay_{k}))+(1-\omega _{k})y_{k-1},\ k=1,2,\ldots }

mit den Parametern

γ = 2 a + b , ω k = 2 μ T k ( μ ) T k + 1 ( μ ) , μ = b + a b − a . {\displaystyle \gamma ={\frac {2}{a+b}},\quad \omega _{k}=2\mu {\frac {T_{k}(\mu )}{T_{k+1}(\mu )}},\quad \mu ={\frac {b+a}{b-a}}.}

In der Vorschrift für y k + 1 {\displaystyle y_{k+1}} ist zu erkennen, dass in der Klammer ein optimaler Schritt des Richardson-Verfahrens steht.

Für eine symmetrisch-definite Matrix A {\displaystyle A} ist diese Iteration eng verwandt mit dem CG-Verfahren, welches aber die Parameter γ , ω k {\displaystyle \gamma ,\omega _{k}} 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.

Für eine symmetrische, positiv definite Matrix A {\displaystyle A} gilt in der euklidischen Norm die Fehlerschranke

‖ y k − x ^ ‖ ≤ 2 ( κ − 1 κ + 1 ) m ‖ y 0 − x ^ ‖ ,   m ≥ 0 , κ = b / a , {\displaystyle \|y_{k}-{\hat {x}}\|\leq 2\left({\frac {{\sqrt {\kappa }}-1}{{\sqrt {\kappa }}+1}}\right)^{m}\|y_{0}-{\hat {x}}\|,\ m\geq 0,\quad \kappa =b/a,}

ähnlich dem CG-Verfahren, wobei κ {\displaystyle \kappa } eine Schranke für die Konditionszahl der Matrix A {\displaystyle A} ist κ ≥ κ 2 ( A ) = λ m a x ( A ) / λ m i n ( A ) {\displaystyle \kappa \geq \kappa _{2}(A)=\lambda _{\rm {max}}(A)/\lambda _{\rm {min}}(A)} . Für m → ∞ {\displaystyle m\to \infty } 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 ω k ≡ 1 {\displaystyle \omega _{k}\equiv 1} optimal.

• Gene H. Golub, Charles van Loan: Matrix Computations, Johns Hopkins University Press.