Vorkonditionierung

In der numerischen Mathematik bezeichnet Vorkonditionierung eine Technik, mittels derer ein Problem so umgeformt wird, dass die Lösung erhalten bleibt, sich jedoch für das gewählte numerische Lösungsverfahren positive Eigenschaften wie bessere Kondition oder schnellere Konvergenz ergeben.

Die gebräuchlichste Form der Vorkonditionierung ist die lineare, bei der ein lineares Gleichungssystem $Ax=b$ äquivalent umgeformt wird. Diese Art der Vorkonditionierung findet insbesondere bei der Lösung des Gleichungssystems mittels Krylow-Unterraum-Verfahren Anwendung. Eine andere wichtige Form entsteht durch Multiplikation des Zeitableitungsterms einer partiellen Differentialgleichung mit einer nichtlinearen Vorkonditionierung. Hierbei bleibt die stationäre Lösung der Gleichung erhalten.

Lineare Vorkonditionierung

Hier unterscheidet man zwischen Linksvorkonditionierung, bei der das Gleichungssystem $Ax=b$ von links mit einer regulären Matrix multipliziert wird: $MAx=Mb$ und Rechtsvorkonditionierung, bei der das Gleichungssystem $AMy=b$ mit $y=M^{-1}x$ gelöst wird. Der Vorkonditionierer sollte die Inverse von $A$ mit geringstmöglichem Aufwand bestmöglich approximieren. Prinzipiell ist jedes iterative Gleichungslösungsverfahren wie das Jacobi- oder das Gauß-Seidel-Verfahren als Vorkonditionierer einsetzbar, dabei ist die Matrix $M$ für die Vorkonditionierung die Inverse $B^{-1}$ der als $B$ bezeichneten Matrix im Artikel Splitting-Verfahren.

Ein einfaches Beispiel eines Vorkonditionierers ist die Äquilibrierung, also die Skalierung der Zeilen oder Spalten des Gleichungssystems mit individuellen Faktoren, so dass alle Zeilen bzw. Spalten der Matrix anschließend die gleiche Norm besitzen.

Im Kontext von Krylow-Unterraum-Verfahren wie dem CG-Verfahren ist es günstig, wenn die Systemmatrix eine geringe Kondition bzw. insbesondere eine „gute“ Eigenwertverteilung hat. Hier ist die Hauptanwendung von Vorkonditionierern zu finden, da die Konvergenzgeschwindigkeit von Krylow-Unterraum-Verfahren so maßgeblich verbessert werden kann.

Neben den schon oben genannten iterativen Verfahren sind unvollständige LU-Zerlegungen, genannt ILU-Zerlegungen, von besonderem Interesse. Diese berechnen mittels des Gauß-Algorithmus eine fehlerbehaftete Zerlegung der Systemmatrix $A$, bei der nur festgelegte Elemente berechnet werden, um Zeit und Speicher zu sparen.

Seit den 1990er Jahren gewinnen Multilevel-Verfahren wie geometrische und algebraische Mehrgitterverfahren immer mehr an Bedeutung.

Nichtlineare Vorkonditionierer

Die Berechnung stationärer Lösungen einer partiellen Differentialgleichung kann mittels nichtlinearer Vorkonditionierung effizienter gestaltet werden. Hierzu wird die Zeitableitung mit einem Vorkonditionierer multipliziert, die Zeit geht also für bestimmte Zellen oder Variablen langsamer oder schneller. Dies geschieht vor allem, um die CFL-Bedingung bei steifen Problemen zu umgehen.

Literatur

• A. Meister: Numerik linearer Gleichungssysteme, Vieweg 1999, ISBN 3-528-03135-2
• Y. Saad: Iterative Methods for Sparse Linear Systems, 2nd edition, SIAM Society for Industrial & Applied Mathematics 2003, ISBN 0-898-71534-2

Weblinks

• Y. Saad: Iterative Methods for Sparse Linear Systems, 1st edition, PWS 1996
• Templates for the Solution of Linear Systems