Unsymmetrisches Lanczos-Verfahren

In d​er numerischen Mathematik i​st das unsymmetrische Lanczos-Verfahren einerseits e​in iteratives Verfahren z​ur näherungsweisen Bestimmung einiger Eigenwerte u​nd evtl. d​erer Eigenvektoren e​iner Matrix. Andererseits i​st es a​ber auch d​ie Grundlage für einige Algorithmen z​ur näherungsweisen Lösung v​on Gleichungssystemen, namentlich v​om Verfahren d​er bikonjugierten Gradienten, a​uch kurz BiCG-Verfahren genannt.

Die Projektion auf Tridiagonalgestalt

Der Algorithmus erzeugt mittels einer kurzen Rekursion Matrizen ${\displaystyle Q_{k}=\left(q_{1},q_{2},\ldots ,q_{k}\right)}$ und ${\displaystyle {\hat {Q}}_{k}=\left({\hat {q}}_{1},{\hat {q}}_{2},\ldots ,{\hat {q}}_{k}\right)}$ , deren Spalten zueinander biorthogonale Basen der Krylowräume ${\displaystyle {\mathcal {K}}={\mathcal {K}}(A,r_{0})}$ und ${\displaystyle {\hat {\mathcal {K}}}={\mathcal {K}}(A^{H},{\hat {r}}_{0})}$ bilden.

Sei eine quadratische Matrix ${\displaystyle A\in \mathbb {C} ^{n\times n}}$ gegeben. Nun werden noch zwei (unnormalisierte) Startvektoren ${\displaystyle r_{0}\in \mathbb {C} ^{n}}$ und ${\displaystyle {\hat {r}}_{0}\in \mathbb {C} ^{n}}$ benötigt, meist existieren aus vorherigen Rechnungen gute Kandidaten oder es werden Zufallsvektoren gewählt.

Der Algorithmus lautet w​ie folgt:

1. Setze ${\displaystyle q_{0}\leftarrow 0}$ , ${\displaystyle {\hat {q}}_{0}\leftarrow 0}$
2. for ${\displaystyle k\in \mathbb {N} }$ do
3. ${\displaystyle \beta _{k-1}\gamma _{k-1}\leftarrow \langle {\hat {r}}_{k-1},r_{k-1}\rangle }$
4. ${\displaystyle q_{k}\leftarrow r_{k-1}/\beta _{k-1}}$
5. ${\displaystyle {\hat {q}}_{k}\leftarrow {\hat {r}}_{k-1}/{\overline {\gamma _{k-1}}}}$
6. ${\displaystyle r_{k}\leftarrow Aq_{k}}$
7. ${\displaystyle {\hat {r}}_{k}\leftarrow A^{H}{\hat {q}}_{k}}$
8. ${\displaystyle \alpha _{k}\leftarrow \langle {\hat {q}}_{k},r_{k}\rangle =\langle {\hat {r}}_{k},q_{k}\rangle }$
9. ${\displaystyle r_{k}\leftarrow r_{k}-\alpha _{k}q_{k}-\gamma _{k-1}q_{k-1}}$
10. ${\displaystyle {\hat {r}}_{k}\leftarrow {\hat {r}}_{k}-{\overline {\alpha _{k}}}{\hat {q}}_{k}-{\overline {\gamma _{k-1}}}{\hat {q}}_{k-1}}$
11. end for

Die schiefe Projektion ${\displaystyle {\hat {Q}}_{k}^{T}\cdot A\cdot Q_{k}=T_{k}}$ der Matrix ${\displaystyle A\in \mathbb {C} ^{n\times n}}$ auf eine Tridiagonalmatrix ${\displaystyle T_{k}\in \mathbb {C} ^{k\times k}}$ gebildet aus den Skalaren ${\displaystyle \alpha _{j},\beta _{j},\gamma _{j}}$ hat die unsymmetrische Tridiagonal-Struktur

  ${\displaystyle T_{k}={\begin{pmatrix}\alpha _{1}&\gamma _{1}&&\\\beta _{1}&\alpha _{2}&\ddots &\\&\ddots &\ddots &\gamma _{k-1}\\&&\beta _{k-1}&\alpha _{k}\end{pmatrix}}}$
.

Details der Implementation

Der obige Algorithmus enthält Freiheit in der Wahl von ${\displaystyle \beta _{k}}$ und ${\displaystyle \gamma _{k}}$ , da in Zeile drei nur das Produkt der beiden Größen eingeht. Häufige Wahlen sind

• ${\displaystyle \beta _{k}=\|r_{k}\|}$ und ${\displaystyle \gamma _{k}={\frac {{\hat {r}}_{k}^{H}r_{k}}{\beta _{k}}}}$
• ${\displaystyle \beta _{k}={\sqrt {|{\hat {r}}_{k}^{H}r_{k}|}}}$ und ${\displaystyle \gamma _{k}={\frac {{\hat {r}}_{k}^{H}r_{k}}{\beta _{k}}}}$ .

Beide Optionen h​aben ihre Vor- u​nd Nachteile.

Eigenwertnäherungen

Die Eigenwerte ${\displaystyle \{\theta _{j}\}_{j=1}^{k}}$ der Tridiagonalmatrix ${\displaystyle T_{k}}$ werden dann als Näherungen für die Eigenwerte ${\displaystyle \lambda }$ von ${\displaystyle A\in \mathbb {C} ^{n\times n}}$ herangezogen. Die Näherungen für Eigenvektoren sind durch die prolongierten Eigenvektoren ${\displaystyle \{s_{j}\}_{j=1}^{k}}$ gegeben. Aufgrund der Verwandtschaft mit einer (schiefen) Galerkin-Projektion werden die Paare ${\displaystyle (\theta _{j},y_{j}=Q_{k}s_{j})}$ auch im nichtsymmetrischen Fall häufig als Ritzpaare bezeichnet.

Verfeinerungen und Erweiterungen

Dieses ursprüngliche, auf einer Dreitermrekursion beruhende Verfahren bricht zusammen, wenn ${\displaystyle {\hat {r}}_{k}^{H}r_{k}=0}$ gilt. Falls (mindestens) einer der beiden Vektoren gleich Null ist, ${\displaystyle {\hat {r}}_{k}=0}$ oder ${\displaystyle r_{k}=0}$ , so ist der zugehörige Krylow-Unterraum ein invarianter Unterraum von ${\displaystyle A}$ und alle Eigenwerte von ${\displaystyle T_{k}}$ , die Ritz-Werte, sind auch Eigenwerte von ${\displaystyle A}$ . Falls aber ${\displaystyle {\hat {r}}_{k}^{H}r_{k}=0}$ und ${\displaystyle {\hat {r}}_{k}\neq 0}$ und ${\displaystyle r_{k}\neq 0}$ , kann das Verfahren nicht mehr mittels einer Dreitermrekursion weitergeführt werden.

Näherungsweise Lösung von Gleichungssystemen

Im Kontext von Gleichungssystemen ${\displaystyle Ax=r_{0}}$ wird als Startvektor das nullte Residuum ${\displaystyle r_{0}}$ genommen.

QOR

Die prolongierte Lösung ${\displaystyle z_{k}}$ des tridiagonalen Systems ${\displaystyle T_{k}z_{k}=\|r_{0}\|e_{1}}$ , wobei ${\displaystyle e_{1}}$ den ersten Einheitsvektor der Länge ${\displaystyle k}$ bezeichne, wird als Näherungslösung ${\displaystyle x_{k}=Q_{k}z_{k}}$ 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.

QMR

Ein zweiter Ansatz basiert a​uf einer erweiterten Tridiagonalmatrix u​nd ist a​ls quasi-minimaler Residualansatz, k​urz QMR, bekannt. Wenn m​an den QMR Ansatz verwendet, k​ommt das bekannte gleichnamige Verfahren d​er quasi-minimalen Residuen, k​urz QMR heraus.

LTPM

Die Multiplikation mit ${\displaystyle A}$ und ${\displaystyle A^{H}}$ im ursprünglichen Algorithmus ist, insbesondere wenn ${\displaystyle A}$ 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 ${\displaystyle A}$ 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 v​on Sonneveld angegebene Verfahren i​st als Verfahren d​er quadrierten (bi)konjugierten Gradienten, i​m Englischen conjugate gradient squared, k​urz CGS bekannt. Weitere Vertreter dieser Gruppe s​ind CGS2, shifted CGS, BiCGSTAB, BiCGSTAB(ell), GPBiCG, TFQMR u​nd QMRCGSTAB.

Literatur

• 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).