BiCG-Verfahren

Das BiCG-Verfahren ist ein iteratives numerisches Verfahren zur approximativen Lösung eines linearen Gleichungssystemes Ax = b, A \in \mathbb{R}^{n \times n}. Es wird eingesetzt, wenn die Matrix zu groß für die Verwendung von direkten Methoden ist. BiCG steht dabei für bikonjugierte Gradienten (im Englischen biconjugate gradients). Das Verfahren basiert auf der Dreitermrekursion des unsymmetrischen Lanczos-Verfahrens.

Der Algorithmus wird in der Praxis selten verwendet, da er ziemlich instabil und anfällig für Rundungsfehler ist. Er ist unbestritten theoretisch interessant, denn er stellt den Ausgangspunkt der Entwicklung der LTPM, der Lanczos-type product methods (Lanczos-artigen Produkt-Methoden) dar. Dazu zählen das (noch stärker instabile) CGS-Verfahren und als Versuch der Stabilisierung des CGS-Verfahrens das (ebenfalls ziemlich instabile) BiCGSTAB-Verfahren. Unter den Experten gibt es zwei Lager. Die einen glauben, dass eine bessere Fehleranalyse der Verfahren Gründe für die Instabilitäten aufzeigen würde und damit zumindest für Spezialfälle zu stabilen Verfahren führen würde, die anderen glauben, dass diese Verfahren niemals stabil sein können und verwenden daher eher GMRES mit Verfeinerungen. Als Faustregel lässt sich festhalten: Anwender und kommerzielle Softwarepakete verwenden angepasste direkte Methoden, viele Forscher und Universitäten arbeiten mit den LTPM in allerlei Varianten.

Es hilft beim Verständnis des Algorithmus, von zwei zu lösenden Gleichungssystemen der Gestalt Ax = b und A^H\hat{x}=\hat{b} auszugehen, wobei A\in\mathbb{C}^{n\times n} eine (im Allgemeinen nicht-hermitesche) quadratische Matrix und b\in\mathbb{C}^n und \hat{b}\in\mathbb{C}^n gegebene rechte Seiten sind. Eigentlich ist man meist nur an der Lösung des ersten genannten Gleichungssystemes interessiert. Gegeben seien ferner zwei Näherungslösungen x_0\in\mathbb{C}^n und \hat{x}_0\in\mathbb{C}^n.

Das Verfahren kommt in vielen verschiedenen Varianten daher, namentlich genannt seien BiOres, BiOmin und BiOdir. Diese Varianten resultieren aus den unterschiedlichen Ansätzen für Krylow-Unterraum-Verfahren und sind mit den Varianten Ores, Omin und Odir des CG-Verfahrens verwandt. Die bekannteste Variante ist BiOmin und verwendet neben den rechten und linken Residuen rj und \hat{r}_j ein Paar bikonjugierte Richtungen pj und \hat{p}_j zur Residuenminimierung.

BiOmin (BiCG in der Orthomin-Variante)

  1. Setze r_0\leftarrow b-Ax_0, p_0\leftarrow r_0
  2. Setze \hat{r}_0\leftarrow \hat{b}-A^H\hat{x}_0, \hat{p}_0\leftarrow \hat{r}_0
  3. for k\in\mathbb{N} do
  4. \alpha_k\leftarrow   \langle\hat{r}_k,r_k\rangle/\langle\hat{p}_k,Ap_k\rangle
  5. x_{k+1}\leftarrow x_k+\alpha_kp_k
  6. \hat{x}_{k+1}\leftarrow \hat{x}_k+\overline{\alpha_k}\hat{p}_k
  7. r_{k+1}\leftarrow r_k-\alpha_kAp_k
  8. \hat{r}_{k+1}\leftarrow \hat{r}_k-\overline{\alpha_k}A^H\hat{p}_k
  9. \beta_k\leftarrow \langle\hat{r}_{k+1},r_{k+1}\rangle/\langle\hat{r}_k,r_k\rangle
  10. p_{k+1}\leftarrow r_{k+1}+\beta_kp_k
  11. \hat{p}_{k+1}\leftarrow \hat{r}_{k+1}+\overline{\beta_k}\hat{p}_k
  12. end for

Dabei kann Zeile 6 entfallen, falls wir nur an der Lösung des ersten Gleichungssystemes interessiert sind. Die Wahl des zweiten Gleichungssystemes, i.e., die Wahl von \hat{b} ist nicht trivial und beeinflusst stark die Stabilität und das Konvergenzverhalten des Algorithmus.

Literatur

  • Andreas Meister: Numerik linearer Gleichungssysteme, 2. Auflage, Vieweg, Wiesbaden 2005, ISBN 3-528-13135-7
  • Yousef Saad: Iterative Methods for Sparse Linear Systems, 2nd edition, SIAM Society for Industrial & Applied Mathematics 2003, ISBN 0-89871-534-2

Wikimedia Foundation.

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

  • Krylov-Unterraum-Verfahren — Krylow Unterraum Verfahren sind iterative Verfahren zum Lösen großer, dünnbesetzter linearer Gleichungssysteme, wie sie bei der Diskretisierung von partiellen Differentialgleichungen entstehen oder von Eigenwertproblemen. Sie sind benannt nach… …   Deutsch Wikipedia

  • CGS-Verfahren — Das CGS Verfahren ist ein iteratives numerisches Verfahren zur approximativen Lösung großer, dünnbesetzter linearer Gleichungssystem Ax = b mit einer reellen Matrix A. CGS ist aus der Klasse der Krylow Unterraum Verfahren und ist insbesondere… …   Deutsch Wikipedia

  • Lanczos-Verfahren — 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

  • 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… …   Deutsch Wikipedia

  • GMRES-Verfahren — 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

  • Krylow-Unterraum-Verfahren — sind iterative Verfahren zum Lösen großer, dünnbesetzter linearer Gleichungssysteme, wie sie bei der Diskretisierung von partiellen Differentialgleichungen entstehen oder von Eigenwertproblemen. Sie sind benannt nach dem russischen… …   Deutsch Wikipedia

  • Krylov-Unterraumverfahren — Krylow Unterraum Verfahren sind iterative Verfahren zum Lösen großer, dünnbesetzter linearer Gleichungssysteme, wie sie bei der Diskretisierung von partiellen Differentialgleichungen entstehen oder von Eigenwertproblemen. Sie sind benannt nach… …   Deutsch Wikipedia

  • 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

  • LTPM — Dieser Artikel oder Abschnitt ist nicht hinreichend mit Belegen (Literatur, Webseiten oder Einzelnachweisen) versehen. Die fraglichen Angaben werden daher möglicherweise demnächst gelöscht. Hilf Wikipedia, indem du die Angaben recherchierst und… …   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”