Methode zur Konvergenzbeschleunigung von Krylow-Raum-Verfahren zur Lösung von linearen Gleichungssystemen.

Die Konvergenzrate von Iterationsverfahren zur Lösung von linearen Gleichungssystemen

\begin{eqnarray}Ax{\rm{\hspace{0.17em}}}={\rm{\hspace{0.17em}}}b{\rm{\hspace{0.17em}}},{\rm{\hspace{0.17em}}}A{\rm{\hspace{0.17em}}}\in {\rm{\hspace{0.17em}}}{{\mathbb{R}}}^{n\times n}\end{eqnarray}

Man versucht nun, das Gleichungssystem Ax = b in ein äquivalentes Gleichungssystem \(\tilde{A}\tilde{x}{\rm{\hspace{0.17em}}}={\rm{\hspace{0.17em}}}\tilde{b}\) zu überführen, für welches das Iterationsverfahren ein besseres Konvergenzverhalten hat. Zur Bestimmung des neuen Gleichungssystems berechnet man häufig zwei nichtsinguläre Matrizen B und \(C{\rm{\hspace{0.17em}}}\in {\rm{\hspace{0.17em}}}{{\mathbb{R}}}^{n\times n}\), und transformiert das Gleichungssystem Ax = b in das äquivalentes Gleichungssystem

\begin{eqnarray}{C}^{-1}A{B}^{-1}(Bx){\rm{\hspace{0.17em}}}={\rm{\hspace{0.17em}}}{C}^{-1}b.\end{eqnarray}

\begin{eqnarray}\tilde{A}{\rm{\hspace{0.17em}}}={\rm{\hspace{0.17em}}}{C}^{-1}A{B}^{-1}{\rm{\hspace{0.17em}}},{\rm{\hspace{0.17em}}}\tilde{x}{\rm{\hspace{0.17em}}}={\rm{\hspace{0.17em}}}Bx{\rm{\hspace{0.17em}}},{\rm{\hspace{0.17em}}}\tilde{b}{\rm{\hspace{0.17em}}}={\rm{\hspace{0.17em}}}{C}^{-1}b.\end{eqnarray}

Im Prinzip kann das Iterationsverfahren nun direkt auf das vorkonditionierte Gleichungssystem \(\tilde{A}\tilde{x}{\rm{\hspace{0.17em}}}={\rm{\hspace{0.17em}}}\tilde{b}\) angewendet werden. Dann ist am Schluß aus der resultierenden Näherungslösung \(\tilde{x}{\rm{\hspace{0.17em}}}\) die Näherungslösung x des gegeben Systems Ax = b durch Lösen eines Gleichungssystems \(Bx{\rm{\hspace{0.17em}}}={\rm{\hspace{0.17em}}}\tilde{x}{\rm{\hspace{0.17em}}}\) zu bestimmen. Es ist jedoch üblich und zweckmäßiger, das Iterationsverfahren so neu zu formulieren, daß direkt mit den gegebenen Größen A, b, C, B gearbeitet wird, und eine Folge von Näherungslösungen x^(k) erzeugt wird, welche Näherungen an die gesuchte Lösung x darstellen. (Siehe konjugiertes Gradientenverfahren für ein Beispiel).

Es existieren verschiedene Ansätze zur Wahl der Vorkonditionierungsmatrizen B und C, eine allgemeingültige Regel zur Bestimmung der Vorkonditionierungsmatrizen gibt es bisher nicht.

Die Berechnung sollte natürlich nicht mehr Zeit in Anspruch nehmen als durch die Konvergenzbeschleunigung gewonnen wird.