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=bAx=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=bAx=b von links mit einer regulären Matrix multipliziert wird: MAx=MbMAx=Mb und Rechtsvorkonditionierung, bei der das Gleichungssystem AMy=bAMy=b mit y=M−1xy=M^{-1}x gelöst wird. Der Vorkonditionierer sollte die Inverse von AA mit geringstmöglichem Aufwand bestmöglich approximieren. Prinzipiell ist jedes iterative Gleichungslösungsverfahren wie das Jacobi-Verfahren 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 AA, 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.

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
 
 

Manche Menschen haben einen Gesichtskreis vom Radius Null und nennen ihn ihren Standpunkt.

David Hilbert

Copyright- und Lizenzinformationen: Diese Seite basiert dem Artikel Vorkonditionierung aus der frеiеn Enzyklοpädιe Wιkιpеdιa und stеht unter der Dοppellizеnz GNU-Lιzenz für freie Dokumentation und Crеative Commons CC-BY-SA 3.0 Unportеd (Kurzfassung). In der Wιkιpеdιa ist eine Listе dеr Autorеn des Originalartikels verfügbar. Da der Artikel geändert wurde, reicht die Angabe dieser Liste für eine lizenzkonforme Weiternutzung nicht aus!
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе
Datenschutzerklärung

 

Numerische Verfahren