Vorkonditionierung
aus Wikipedia, der freien Enzyklopädie
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.
Inhaltsverzeichnis |
[Bearbeiten] 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 − 1x 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.
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 algebraische Mehrgitterverfahren immer mehr an Bedeutung.
Ein einfaches Beispiel ist die Äquilibrierung, also die Skalierung der Zeilen oder Spalten des Gleichungssystems mit individuellen Faktoren, so dass alle Spalten oder Zeilen der Matrix anschließend die gleiche Spalten- oder Zeilensummennorm besitzen.
[Bearbeiten] 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.
[Bearbeiten] 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
