Das Verfahren der konjugierten Residuen (auch CR-Verfahren von ) ist in der numerischen Mathematik ein Krylow-Unterraum-Verfahren zur iterativen Lösung symmetrischer linearer Gleichungssysteme.
Im Gegensatz zum CG-Verfahren minimiert CR das Residuum und nicht die -Norm. Weiter verlangt CR nur Invertierbarkeit der Systemmatrix und CG benötigt positiv definite Systeme. Dafür hat CR aber pro Iteration etwas höheren Aufwand.
Für indefinite symmetrische Probleme verwendet man in der Praxis meist den Lanczos-Verwandten MINRES.
Grundprinzip
Ziel ist es, ein lineares Gleichungssystem mit einer symmetrischen und invertierbaren Matrix und einer rechten Seite zu lösen.
Ausgehend von einem Startwert und dem Anfangsresiduum sucht es die Näherung
,
in einem affinen Krylowraum .
Die Iterierte wird so berechnet, dass die euklidische Norm des Residuums in diesem Raum minimal wird, d. h. .
Bei CR sind die Suchrichtungen -orthogonal und die Residuen sind -orthogonal. Bei CG hingegen sind die Suchrichtungen -orthogonal und die Residuen sind euklidisch orthogonal.
Wie bei CG genügt auch bei CR eine kurze Lanczos-Rekursion, d. h. nur die letzten zwei Iterierten sind nötig, um die nächste zu erhalten. Daher müssen weder alle früheren Lanczos-Vektoren noch die vollständige tridiagonale Lanczos-Matrix gespeichert werden.
Algorithmische Form
Zunächst wählt man eine Startnäherung und setzt Anfangsresiduum und Suchrichtung: , , .
Für berechnet man zunächst .
Damit der Ausdruck definiert ist, muss gelten; dies ist durch die Regularität von abgesichert.
Dann werden Näherung und Residuum aktualisiert: , .
Falls kleiner als eine vorgegebene Toleranz ist, wird der Algorithmus mit der Näherung beendet.
Andernfalls berechnet man ,
und anschließend .
Die neue Suchrichtung wird durch
gebildet. Das zugehörige Matrixbild kann inkrementell berechnet werden: .
Dadurch muss nicht separat mit einer (teuren) Matrixmultiplikation berechnet werden.
CR ist algorithmisch eng mit CG verwandt, benötigt jedoch zusätzliche Hilfsvektoren und ist deshalb pro Iteration etwas aufwendiger.
Obwohl -Orthogonalität auftritt, wird nicht als Systemmatrix verwendet; insbesondere ergibt sich nicht die Konditionsverschlechterung auf wie bei CG auf .
Vorkonditionierung
Wie beim CG-Verfahren kann auch das Verfahren der konjugierten Residuen vorkonditioniert werden. Sei dazu ein Vorkonditionierer, wobei bzw. symmetrisch positiv definit ist.
Gegenüber der unvervorkonditionierten Form ersetzt man das Residuum durch das vorkonditionierte Residuum .
Die Initialisierung wird entsprechend zu , , .
Im Algorithmus übernimmt die Rolle von . Außerdem wird der Nenner in der Schrittweite angepasst: .
Nach der Aktualisierung von berechnet man das neue vorkonditionierte Residuum durch ,
oder äquivalent inkrementell durch .
Die Formeln für , , und bleiben formal gleich, wobei überall durch ersetzt wird.
Literatur
Kategorie:Numerische lineare Algebra