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

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 wie 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 haben ihre Vor- und 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.

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