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
existiert
, 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:
Vorkonditionierer
Vorkonditionieres
