Direkt zum Inhalt

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}

hängt von den Spektraleigenschaften, insbesondere der Konditionszahl, der Matrix A ab.

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}

Es ist dann also

\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}

Man nennt dann das Gleichungssystem \(\tilde{A}\tilde{x}{\rm{\hspace{0.17em}}}={\rm{\hspace{0.17em}}}\tilde{b}\) ein vorkonditioniertes Gleichungssystem.

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.

Lesermeinung

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.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos