9.6 Nichtstationäre interative Verfahren

Definition: (Nichtstationäre Iteration)

Eine Iteration $x(k+1)$ :=$T$_k(x^(k)) dabei k = 0 , 1 , 2 ....., ist nichtstationär, wenn die Iterationsvorschrift T_k vom jeweiligen Iterationsschritt abhängt.
Zu den nichtstationären iterativen Lösungsmethoden linearer Gleichungssysteme zählen unter anderem folgende Verfahren.

CG_Verfahren :

Es wird eine Folge konjugierten Vektoren, die sich als Residuen der Iterationsvektoren ergeben, erzeugt (vgl. Abschnitt 16.7.4). Die konjugierten Vektoren sind Gradienten eines quadratischen Funktionals, dessen Minimierung äquivalent zur Lösung des linearen Gleichungssystems ist. Ist die Koeffizientenmatrix positiv definit, so sind CG-Verfahren höchst effektiv.

MINRES und SYMMLQ Verfahren :

MINRES- und SYMMLQ-Verfahren sind Alternativen zu den CG-Verfahren, falls die Koeffizientenmatrix symmetrisch, aber nicht notwendigerweise positiv definit ist. Bei positiv definiten Matrizen liefem die SYMMLQ-Verfahren dieselbe Lösung wie die CG-Verfahren

CGNE-und CGNR-Verfahren :

CGNE- und CGNR-Verfahren sind spezielle CG-Verfahren für Probleme, deren Koeffizientenmatrix A nichtsymmetrisch und nichtsingulär ist. Sie beruhen darauf, daß die Matrizen AA^T und A^TA stets symmetrisch und positiv definit sind. Das CGNE-Verfahren berechnet y aus ( AA^T )y = b und anschließend x = A^Ty . Das CGNR-Verfahren löst . Wegen des für CG-Verfahren ungünstigeren Spektrums der Normalgleichungsmatrizen A^TA und AA^T kann die Konvergenz dieser beiden Verfahren unter Umständen sehr langsam sein.

GMRES-Verfahren :

GMRES-Verfahren: Wie beim MINRES-Verfahren wird eine Folge orthogonaler Vektoren erzeugt, die durch Lösung und Aktualisierung mit der Methode der kleinsten Quadrate kombiniert werden. Da in jedem Iterationsschritt die gesamte bisher ermittelte Folge benötigt wird, ist der Speicheraufwand weit höher als beim MINRES-Verfahren. Daher empfiehlt es sich, das GMRES-Verfahren nur für Gleichungssysteme mit allgemeinen nichtsymmetrischen Matrizeii einzusetzen.

BiCG-Verfahren :

BiCG-Verfahren: Es werden zwei Vektorfolgen generiert, eine für die Matrix A und eine für die Matrix A ^T , die wechselseitig orthogonalisiert ("biorthogonalisiert") werden. Das Verfahren ist im Fall nichtsymmetrischer, nichtsingulärer Matrizen von Nutzen.

QMR-Verfahren:

Das QMR-Verfahren wendet auf die BiCG-Residuenvektoren die Methode der kleinsten Quadrate an, wodurch unregelmäßige Konvergenz und die Möglichkeit eines Versagens weitgehend vermieden werden.

CGS-Verfahren:

Das CGS-Verfahren ist eine Variante des BiCG-Verfahren, bei der die zur A- bzw. A ^T -Folge gehörigen Operationen auf dieselben Vektoren angewendet werden. Dem Vorteil der Einsparung der Multiplikation mit A^T steht jedoch in der Praxis ein schwer überschaubares Konvergenzverhalten gegenüber.

Das BiCGSTAB-Verfahren :

Das BiCGSTAB-Verfahren ist wie das CGS-Verfahren eine Variante des BiCG-Verfahrens. Allerdings werden hier für die A^T-Folge andere Aktualisierungen (updates) vorgenommen, um die Konvergenz regelmäßiger zu machen.

Tschebyscheff-Verfahren :

Tschebyscheff-Iteration: Bei dieser Methode werden rekursiv Polynome bestimmt, deren Koeffizienten so gewählt sind, daß die Norm der Residuenvektoren im "Minimax-Sinn" minimiert wird. A muß positiv definit sein, und Information über die extremalen Eigenwerte ist erforderlich. Ein Vorteil dieses Verfahrens ist, daß keine inneren Produkte gebildet werden müssen.

---

[ < ] [ globale Übersicht ] [ Kapitelübersicht ] [ Stichwortsuche ] [ > ]