Lexikon der Mathematik: Vorkonditionierung
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(
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.
Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.