Präkonditionierung (allgemein)

Der Einfluss der Konditionszahl der Koeffizientenmatrix eines linearen Gleichungssystems auf die Lösung wird auf der Seite "Rundungsfehler, Kondition einer Matrix" verdeutlicht. Auf der Seite "Skalierung eines linearen Gleichungssystems" wird eine einfache Möglichkeit beschrieben, die Kondition der Koeffizientenmatrix zu verbessern.

Die Grundidee besteht darin, die Kondition der Koeffizientenmatrix A des linearen Gleichungssystems

AxGleichB14

durch Linksmultiplikation mit einer geeigneten Matrix PL und/oder Rechtsmultiplikation mit einer Matrix PR so zu verändern, dass das modifizierte Gleichungssystem z. B. in dem Sinne besser lösbar ist, dass ein iteratives Verfahren schneller konvergiert. Der allgemeine Fall kann so realisiert werden:

Praekonditionierung

Während die Linksmultiplikation mit PL auf beiden Seiten des Gleichungssystems vorgenommen wird, muss die Rechtsmultiplikation der Matrix A mit PR durch zusätzliche Multiplikation mit deren Inverser kompensiert werden. Es wird also stellvertretend für das Originalsystem das modifizierte System

PraekonditioniertesSystem

mit der (hoffentlich) besser konditionierten Koeffizientenmatrix AP gelöst, dessen Ergebnis anschließend entsprechend

Ruecktransformation

rücktransformiert werden muss.

Das beschriebene Verfahren ist bei beliebigen Lösungsverfahren für das Gleichungssystem anwendbar. Als "Präkonditionierer" PL bzw. PR kann im einfachsten Fall eine skalierende Diagonalmatrix verwendet werden (für die Lösung mit Eliminationsverfahren in der Regel ausreichend, siehe "Skalierung eines linearen Gleichungssystems"). Für iterative Lösungsverfahren, bei denen Präkonditionierung in der Regel zwingend ist, können raffiniertere Strategien verwendet werden, z. B. die so genannten "unvollständigen Dreieckszerlegungen für schwach besetzte Matrizen" (LU, QR, Cholesky), bei denen in der "klasssischen Variante" nur die Elemente der entstehenden Dreiecksmatrizen berechnet werden, die auf Positionen stehen, die auch in der Ausgangsmatrix von Null verschiedene Elemente hatten (die durch das "Fill-in" entstehenden Elemente werden ignoriert, es gibt jedoch auch Varianten, die von "Diagonalmatrix bis zur komplette Dreieckszerlegung" alle Zwischenstufen ermöglichen, vgl. z. B. Test: Präkonditionierung mit "Incomplete Cholesky").

Die in Matlab angebotenen iterativen Verfahren sind alle auf die Übergabe von "Präkonditionierern" eingerichtet. Auf der Seite "Testrechnungen mit Präkonditionierung mit Matlab" findet man dafür Beispielrechnungen.

Präkonditioniertes Konjugierte-Gradienten-Verfahren

Am Beispiel der Methode der konjugierten Gradienten soll gezeigt werden, dass die oben beschriebene Präkonditionierung in das iterative Lösungsverfahren integriert werden kann, so dass der zusätzlich Aufwand gering ist, wenn man die Konditionierungsmatrizen mit erträglichem Aufwand erzeugt. Weil die Methode der konjugierten Gradienten an die Bedingung geknüpft ist, dass die Koeffizientenmatrix A symmetrisch und positiv definit ist, sollte unbedingt mit einem Präkonditionierer PL gearbeitet werden, der diese Eigenschaften erhält, indem A mit PL von links und zusätzlich mit der Transponierten von PL von rechts multipliziert wird (deshalb wird als Präkonditionierer gern die unvollständige Cholesky-Zerlegung gewählt, weil eine Matrix nach Cholesky in ein Produkt aus Links- und Rechtsdreiecksmatrix zerlegt wird, die zueinander transponiert sind, vgl. auch Test: Präkonditionierung mit "Incomplete Cholesky"). Der oben angegebene allgemeine Fall wird also wie folgt modifiziert:

PraekonditionierungSymm02

Dies kann vorab realisiert werden, wobei eine anschließende Rücktransformation entsprechend

RuecktransformationSymm

ausgeführt werden muss. Man kann jedoch die oben angegebenen Beziehungen auch direkt in den Algorithmus der Methode der konjugierten Gradienten einbauen. Dabei zeigt sich, dass das Verfahren nur das Produkt

PraekonditioniererP

benötigt, und man erhält folgenden

Algorithmus des präkonditionierten Konjugierte-Gradienten-Verfahrens:

PraeKonjGradAnfWerte

KonjGradSchritti02

     PraeKonjGradVorbSchrittiPlus1          

Dieser Algorithmus ist in dem Matlab-Script PKG.m realisiert, wobei der Präkonditionierer P in einer gesonderten Function PraeKond (am Ende des Scripts) erzeugt wird. In der zum Download bereitgestellten Version findet man dafür einen "Skalierer" (Diagonalmatrix der reziproken Diagonalelemente von A), also eine besonders einfache Variante, bei Bedarf zu ersetzen durch einen anspruchsvolleren Präkonditionierer.

Auf der Seite "Testrechnungen mit präkonditioniertem KG-Verfahren" wird deutlich, dass selbst die im Matlab-Script PKG.m realisierte besonders einfache Präkonditionierung (Skalierung) gerade bei den Gleichungssystemen, die sich bei Verzicht auf Präkonditionierung der Konvergenz besonders hartnäckig widersetzten (vgl. "Testrechnungen mit iterativen Verfahren (1)" und "Testrechnungen mit iterativen Verfahren (2)"), mit gutem Konvergenzverhalten gelöst werden können. Diese Aussage wird (zumindest für einen Teil der angebotenen iterativen Verfahren) mit den "Testrechnungen mit Präkonditionierung mit Matlab" bestätigt.