Das SYMMLQ-Verfahren, oder auch symmetrisches LQ-Verfahren, ist ein Krylow-Unterraum-Verfahren zur iterativen Lösung von symmetrischen linearen Gleichungssystemen. Es wurde 1975 von den Mathematikern Christopher Conway Paige und Michael Alan Saunders zusammen mit dem MINRES-Verfahren vorgeschlagen.

Im Gegensatz zum CG-Verfahren benötigt SYMMLQ (und MINRES) keine positive Definitheit der Matrix. Wie MINRES verwendet SYMMLQ ein projiziertes Lanczos-System. Im Unterschied zu MINRES minimiert es jedoch nicht die Residuumsnorm, sondern baut mittels einer LQ-Zerlegung, der transponierten Variante der QR-Zerlegung, das Residuum orthogonal zum Krylowraum. In der Praxis wird meist MINRES gegenüber SYMMLQ bevorzugt.

Grundprinzip

Ziel ist es ein lineares Gleichungssystem mit symmetrischer Matrix zu lösen. Ausgehend von einem Startwert und dem Anfangsresiduum sucht es die Näherung in einem affinen Krylowraum

,

mit .

Die Grundlage ist das Lanczos-Verfahren. Für die orthonormale Lanczos-Basis des Krylowraums gilt für

wobei eine kleine symmetrische tridiagonale Matrix ist. Mit

wird die Näherung durch einen Koeffizientenvektor im Krylowraum beschrieben.

SYMMLQ wählt so, dass das Residuum

orthogonal zum Krylowraum ist, also

Nun kann nachgewiesen werden, dass diese Galerkin-Bedingung auf das quadratische projizierte Lanczos-System

führt. Damit unterscheidet sich SYMMLQ von MINRES: MINRES minimiert die euklidische Residuumsnorm über ein überbestimmtes kleines Lanczos-System, während SYMMLQ das quadratische projizierte System verwendet.

Das kleine symmetrische tridiagonale System wird im SYMMLQ-Verfahren nicht direkt invertiert, sondern mithilfe einer LQ-Zerlegung behandelt. Dadurch lässt sich das Verfahren auch für symmetrische indefinite Matrizen verwenden.

Algorithmische Form

Zu lösen ist ein reelles symmetrisches lineares Gleichungssystem .

Zunächst wählt man beliebig und berechnet

.

Falls kleiner als eine vorgegebene Toleranz ist, ist bereits eine gewünschte Lösung. Andernfalls setzt man

.

Dann iteriert man für die folgenden Schritte:

Führe einen Lanczos-Schritt aus:

.

Falls , setze . Falls , endet die Lanczos-Rekursion, da kein neuer Basisvektor erzeugt werden kann.

Damit entsteht nach Schritten die tridiagonale Matrix

Die Lanczos-Relation kann in der Form

geschrieben werden, wobei

und

gilt.

In einer idealisierten Galerkin-Darstellung würde man das kleine projizierte Gleichungssystem

lösen. Dies entspricht der Orthogonalitätsbedingung .

Das eigentliche SYMMLQ-Verfahren verwendet jedoch eine LQ-Zerlegung der kleinen Lanczos-Matrix und aktualisiert diese rekursiv. Dadurch muss nicht direkt invertiert werden. Die Näherung wird so bestimmt, dass die zugehörige Residuenbedingung in der Lanczos-Basis erfüllt wird.

Formal erhält man eine Näherung der Form .

Das zugehörige Residuum ist .

Gilt in der idealisierten Galerkin-Darstellung , so folgt aus der Lanczos-Relation

und damit .

Falls kleiner als eine vorgegebene Toleranz ist, bricht man den Algorithmus mit der Näherungslösung ab.

In praktischen Implementierungen werden die Matrizen , und nicht vollständig gespeichert. Stattdessen werden die Lanczos-Dreiglied-Rekursion, die LQ-Zerlegung und die Näherungslösung schrittweise aktualisiert. Dadurch benötigt SYMMLQ nur wenige zusätzliche Vektoren pro Iterationsschritt.

Literatur

Kategorie:Numerische lineare Algebra