imported>Rita2008: HC: Ergänze Kategorie:Pafnuti Lwowitsch Tschebyschow

2024-11-18T21:56:51Z

HC: Ergänze Kategorie:Pafnuti Lwowitsch Tschebyschow

Neue Seite

Die '''Tschebyschow-Iteration''' (nach [[Pafnuti Lwowitsch Tschebyschow]]) ist ein [[Numerische Mathematik|numerisches Verfahren]] zur Lösung von [[Lineares Gleichungssystem|linearen Gleichungssystemen]] <math>Ax=b</math> mit <math>A \in \R^{n \times n}</math> und wird auch als semi-iteratives Verfahren bezeichnet, da sie als ein einfacher Iterationsschritt eines [[Splitting-Verfahren]]s mit nachgeschalteter Extrapolation interpretiert werden kann. Grundlage ist die Rekursionsformel für [[Tschebyschow-Polynom]]e. Das Verfahren erreicht für [[Symmetrische Matrix|symmetrische]] [[positiv definit]]e Matrizen die Geschwindigkeit des [[CG-Verfahren]]s, kann aber auch für unsymmetrische Matrizen angepasst werden, wenn Informationen über die Lage der [[Eigenwert]]e vorliegen.

== Das semi-iterative Verfahren ==
Grundlage ist die Idee, dass man aus der Vektorfolge <math>(x_k)_{k\ge0}</math>, die man mit einem [[Splitting-Verfahren]] erhält, durch allgemeine Linearkombination eine bessere Folge
:<math> y_k = \sum_{j=0}^k\alpha_{kj}x_j</math>
konstruiert. Um eine exakte Lösung <math>\hat x</math> nicht wieder zu verlassen, ist <math>\sum_{j=0}^k\alpha_{kj}=1</math> erforderlich. Da für die Fehler beim Splitting-Verfahren <math>x_k-\hat x=M^k(x_0-\hat x),\ M=I-B^{-1}A</math> gilt, erhält man für den neuen Fehler
:<math> 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).</math>
Also wird der Startfehler <math>x_0-\hat x</math> mit dem Matrix-[[Polynom]] <math>p_k(M)</math> multipliziert mit dem Ziel, diesen zu verkleinern.
Hat die Matrix <math>A</math> nur reelle Eigenwerte in einem Intervall <math>[a,b],\,a>0</math>, ist dasjenige [[Polynom]] mit kleinster Schranke für den Spektralradius <math>\rho(p_k(A))</math> ein verschobenes [[Tschebyschow-Polynom]] <math>T_k</math>.
Da für letztere eine zweistufige Rekursionsformel gilt, kann die Tschebyschow-Iteration ebenfalls als zweistufiges Verfahren ausgeführt werden:
:<math>\,\! y_1= y_0+\gamma (b-Ay_0)</math>
:<math> y_{k+1} = \omega_k(y_k+\gamma (b-Ay_k))+(1-\omega_k)y_{k-1},\ k=1,2,\ldots</math>
mit den Parametern
:<math> \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}.</math>
In der Vorschrift für <math>y_{k+1}</math> ist zu erkennen, dass in der Klammer ein optimaler Schritt des [[Richardson-Verfahren]]s steht.

Für eine symmetrisch-definite Matrix <math>A</math> ist diese Iteration eng verwandt mit dem CG-Verfahren, welches aber die Parameter <math>\gamma,\omega_k</math> anders bestimmt, und besitzt die gleiche [[Konvergenzgeschwindigkeit]]. Die Tschebyschow-Iteration kann aber auch auf unsymmetrische Matrizen mit komplexen [[Eigenwert]]en angewendet werden, wenn diese sich in einer [[Ellipse]] einschließen lassen, welche den Nullpunkt nicht enthält.

== Konvergenz des Verfahrens ==
Für eine symmetrische, positiv definite Matrix <math>A</math> gilt in der euklidischen Norm die [[Fehlerschranke]]
:<math> \|y_k-\hat x\|\le 2\left(\frac{\sqrt{\kappa}-1}{\sqrt{\kappa}+1}\right)^m\|y_0-\hat x\|,
\ m\ge0,\quad \kappa=b/a,</math>
ähnlich dem [[CG-Verfahren]], wobei <math>\kappa</math> eine Schranke für die [[Kondition (Mathematik)|Kondition]]szahl der Matrix <math>A</math> ist <math>\kappa\ge \kappa_2(A)=\lambda_{\rm max}(A)/\lambda_{\rm min}(A)</math>.
Für <math>m\to\infty</math> 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 (Geometrie)|Kreis]] schließlich ist das einfache Verfahren mit <math>\omega_k\equiv1</math> optimal.

== Literatur ==
* Gene H. Golub, Charles van Loan: ''Matrix Computations'', Johns Hopkins University Press.

[[Kategorie:Numerische lineare Algebra]]
[[Kategorie:Pafnuti Lwowitsch Tschebyschow]]

Tschebyschow-Iteration - Versionsgeschichte

imported>Rita2008: HC: Ergänze Kategorie:Pafnuti Lwowitsch Tschebyschow