4.5.4 Vorkonditionierung



next up previous contents
Next: 4.5.4.1 Der Vorkonditionierer Up: 4.5 Gradientenverfahren Previous: 4.5.3.2 CG-Methode

4.5.4 Vorkonditionierung

Vorkonditionierung ist bei iterativen Methoden eine Technik, um die Konvergenz zu beschleunigen oder sie auch erst zu ermöglichen. Die Vorkonditionierungsmatrix soll hier symmetrisch und positiv definit sein. Die Matrix soll möglichst gut approximieren, aber auch leichter als zu invertieren sein. Es ist also möglich,

indirekt über

zu lösen. Wenn gilt, oder wenn die Eigenwerte gehäufter auftreten, so wird das neue System iterativ schneller zu lösen sein als das alte Problem. Zu bemerken ist, daß im allgemeinen nicht symmetrisch oder definit ist, obwohl und es sind [She94].

Da für jede symmetrische und positiv definite M-Matrix eine Faktorisierung existiertgif, kann durch links- und rechtsseitige Multiplikation mit auf das Problem gelöst werden.

Die Matrizen und haben die gleichen Eigenwerte und daher auch die gleiche Konditionszahl .

Ist nämlich ein Eigenvektor mit dem Eigenwert von , dann ist auch ein Eigenvektor von mit dem Eigenwert .

Das Problem kann in das Problem

transformiert werden.

Die Idee der Vorkonditionierung bei Anwendung auf CG-Lösern liegt aber nicht in der Methode, die aufwendigen Matrix-Matrix-Multiplikationen auszuführen und nach der Iteration durch eine Rücksubstitution zu gewinnen, sondern die Vorkonditionierungsmatrix wird in den Iterationsprozeß miteinbezogen.

  Der gezeigte CG-Algorithmus (4.45) kann folgendermaßen in den sogenannten transformierten vorkonditionierten CG-Löser gebracht werden [She94][Gol89]:

 

Die angegebene Form hat die ungewünschte Eigenschaft, daß berechnet werden muß. Durch einige Substitutionen in der Art und mit läßt sich eine Form angegeben, deren Vektoren nicht transformiert sind:

 

Die Inverse wird bei einer Implementierung aus Laufzeitgründen und notwendigen Speicherplatz nie berechnet, sondern es wird durch Lösen von berechnet. Ist die Faktorisierung von bekannt, so kann die Lösung durch Vorwärtselimination und Rücksubstitution, wie in Abschnitt 4.4 erklärt wird, mit aktzeptablem Aufwand gewonnen werden.

 

Die Matrix scheint in der neuen Version nicht mehr auf. Nach dem gleichen Prinzip kann auch die Methode des steilsten Abstiegs vorkonditioniert werden.

Nun sollen die Erfordernisse an die Vorkonditionierungsmatrix genauer untersucht werden. Es besteht das Problem, einen Vorkonditionierer zu finden, der genügend genau approximiert und gleichzeitig den Aufwand zur Lösung von in Grenzen hält.

Baut man einen perfekten Vorkonditionierer, so ist und die quadratische Form sphärisch. Der CG-Löser benötigt zur Lösung dieses Systems nur eine Iteration. Es ist jedoch nicht sinnvoll, das Problem auf diese Art zu lösen.

Die einfachste Form eines Vorkonditionierers ist die diagonale Skalierung in der die Symmetrie erhaltenden Form:





next up previous contents
Next: 4.5.4.1 Der Vorkonditionierer Up: 4.5 Gradientenverfahren Previous: 4.5.3.2 CG-Methode



Martin Stiftinger
Fri Nov 25 16:50:24 MET 1994