Unsymmetrisches Lanczos-Verfahren

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

In der numerischen Mathematik ist das unsymmetrische Lanczos-Verfahren einerseits ein iteratives Verfahren zur näherungsweisen Bestimmung einiger Eigenwerte und evtl. derer Eigenvektoren einer Matrix. Andererseits ist es aber auch die Grundlage für einige Algorithmen zur näherungsweisen Lösung von Gleichungssystemen, namentlich vom Verfahren der bikonjugierten Gradienten, auch kurz BiCG-Verfahren genannt.

Die Projektion auf Tridiagonalgestalt

[Bearbeiten | Quelltext bearbeiten]

Der Algorithmus erzeugt mittels einer kurzen Rekursion Matrizen und , deren Spalten zueinander biorthogonale Basen der Krylowräume und bilden.

Sei eine quadratische Matrix gegeben. Nun werden noch zwei (unnormalisierte) Startvektoren und benötigt, meist existieren aus vorherigen Rechnungen gute Kandidaten oder es werden Zufallsvektoren gewählt.

Der Algorithmus lautet wie folgt:

  1. Setze ,
  2. for do
  3. end for

Die schiefe Projektion der Matrix auf eine Tridiagonalmatrix gebildet aus den Skalaren hat die unsymmetrische Tridiagonal-Struktur

  .

Details der Implementation

[Bearbeiten | Quelltext bearbeiten]

Der obige Algorithmus enthält Freiheit in der Wahl von und , da in Zeile drei nur das Produkt der beiden Größen eingeht. Häufige Wahlen sind

  • und
  • und .

Beide Optionen haben ihre Vor- und Nachteile.

Eigenwertnäherungen

[Bearbeiten | Quelltext bearbeiten]

Die Eigenwerte der Tridiagonalmatrix werden dann als Näherungen für die Eigenwerte von herangezogen. Die Näherungen für Eigenvektoren sind durch die prolongierten Eigenvektoren gegeben. Aufgrund der Verwandtschaft mit einer (schiefen) Galerkin-Projektion werden die Paare auch im nichtsymmetrischen Fall häufig als Ritzpaare bezeichnet.

Verfeinerungen und Erweiterungen

[Bearbeiten | Quelltext bearbeiten]

Dieses ursprüngliche, auf einer Dreitermrekursion beruhende Verfahren bricht zusammen, wenn gilt. Falls (mindestens) einer der beiden Vektoren gleich Null ist, oder , so ist der zugehörige Krylow-Unterraum ein invarianter Unterraum von und alle Eigenwerte von , die Ritz-Werte, sind auch Eigenwerte von . Falls aber und und , kann das Verfahren nicht mehr mittels einer Dreitermrekursion weitergeführt werden.

Näherungsweise Lösung von Gleichungssystemen

[Bearbeiten | Quelltext bearbeiten]

Im Kontext von Gleichungssystemen wird als Startvektor das nullte Residuum genommen.

Die prolongierte Lösung des tridiagonalen Systems , wobei den ersten Einheitsvektor der Länge bezeichne, wird als Näherungslösung genommen. Dieser Ansatz ist als quasi-orthogonaler Residualansatz, kurz QOR, bekannt. Wenn man den QOR Ansatz anwendet, kommt je nach Details eine Variante des bekannten BiCG-Verfahrens heraus.

Ein zweiter Ansatz basiert auf einer erweiterten Tridiagonalmatrix und ist als quasi-minimaler Residualansatz, kurz QMR, bekannt. Wenn man den QMR Ansatz verwendet, kommt das bekannte gleichnamige Verfahren der quasi-minimalen Residuen, kurz QMR heraus.

Die Multiplikation mit und im ursprünglichen Algorithmus ist, insbesondere wenn nur als Black-Box bekannt ist, zu teuer. Sonneveld gab als erster eine Implementation eines Verfahrens basierend auf der Lanczos-Rekursion, welches nur mit Multiplikationen mit auskommt. Die Klasse dieser Verfahren ist im Englischen unter dem von Martin H. Gutknecht geprägten Namen Lanczos-type product methods, kurz LTPM, bekannt.

Das von Sonneveld angegebene Verfahren ist als Verfahren der quadrierten (bi)konjugierten Gradienten, im Englischen conjugate gradient squared, kurz CGS bekannt. Weitere Vertreter dieser Gruppe sind CGS2, shifted CGS, BiCGSTAB, BiCGSTAB(ell), GPBiCG, TFQMR und QMRCGSTAB.

  • Andreas Meister: Numerik linearer Gleichungssysteme. Eine Einführung in moderne Verfahren. 2. Aufl. Vieweg, Wiesbaden 2005, ISBN 3-528-13135-7 (mit MATLAB-Implementierungen von Christoph Vömel).