Unsymmetrisches Lanczos-Verfahren

Unsymmetrisches Lanczos-Verfahren

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.

Inhaltsverzeichnis

Die Projektion auf Tridiagonalgestalt

Der Algorithmus erzeugt mittels einer kurzen Rekursion Matrizen Q_k=\left(q_1,q_2,\ldots,q_k\right) und \hat{Q}_k=\left(\hat{q}_1,\hat{q}_2,\ldots,\hat{q}_k\right), deren Spalten zueinander biorthogonale Basen der Krylowräume \mathcal{K}=\mathcal{K}(A,r_0) und \hat{\mathcal{K}}=\mathcal{K}(A^H,\hat{r}_0) bilden.

Sei eine quadratische Matrix A\in\mathbb{C}^{n\times n} gegeben. Nun werden noch zwei (unnormalisierte) Startvektoren r_0\in\mathbb{C}^n und \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 q_0\leftarrow0, \hat{q}_0\leftarrow0
  2. for k\in\mathbb{N} do
  3. \beta_{k-1}\gamma_{k-1} \leftarrow \langle\hat{r}_{k-1},r_{k-1}\rangle
  4. q_k\leftarrow r_{k-1}/\beta_{k-1}
  5. \hat{q}_k\leftarrow r_{k-1}/\overline{\gamma_{k-1}}
  6. r_k\leftarrow Aq_k
  7. \hat{r}_k\leftarrow A^H\hat{q}_k
  8. \alpha_k\leftarrow \langle\hat{q}_k,r_k\rangle=\langle\hat{r}_k,q_k\rangle
  9. r_k\leftarrow r_k-\alpha_kq_k-\gamma_{k-1}q_{k-1}
  10. \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 Q_k^TA\hat{Q}_k der Matrix A\in\mathbb{C}^{n\times n} ist eine Tridiagonalmatrix T_k\in\mathbb{C}^{k\times k} gebildet aus den Skalaren αjjj,

  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 βk und γk, da in Zeile drei nur das Produkt der beiden Größen eingeht. Häufige Wahlen sind

  • \beta_k=\|r_k\| und \gamma_k=\frac{\hat{r}_k^Hr_k}{\beta_k}
  • \beta_k=\sqrt{|\hat{r}_k^Hr_k|} und \gamma_k=\frac{\hat{r}_k^Hr_k}{\beta_k}.

Beide Optionen haben ihre Vor- und Nachteile.

Eigenwertnäherungen

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

Verfeinerungen und Erweiterungen

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

Näherungsweise Lösung von Gleichungssystemen

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

QOR

Die prolongierte Lösung zk des tridiagonalen Systemes T_kz_k=\|r_0\|e_1, wobei e1 den ersten Einheitsvektor der Länge k bezeichne, wird als Näherungslösung xk = Qkzk 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 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.

LTPM

Die Multiplikation mit A und AH im ursprünglichen Algorithmus ist, insbesondere wenn 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 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 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.

Literatur

  • A. Meister: Numerik linearer Gleichungssysteme, 2. Auflage, Vieweg 2005, ISBN 3528131357

Wikimedia Foundation.

Игры ⚽ Поможем решить контрольную работу

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Lanczos-Prozess — Das Lanczos Verfahren[1] (nach Cornelius Lanczos) ist sowohl ein iterativer Algorithmus zur Bestimmung einiger Eigenwerte und eventuell der zugehörigen Eigenvektoren einer Matrix, als auch ein iterativer Algorithmus zur approximativen Lösung… …   Deutsch Wikipedia

  • GMRES — Das GMRES Verfahren (für Generalized minimal residual method) ist ein iteratives numerisches Verfahren zur Lösung großer, dünnbesetzter linearer Gleichungssysteme. Das Verfahren ist aus der Klasse der Krylow Unterraum Verfahren und insbesondere… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”