imported>Bildungsbürger: -BKL-Link mit AWB

2022-08-13T08:56:29Z

-BKL-Link mit AWB

Neue Seite

Das '''BiCG-Verfahren''' ist ein [[Iteratives Verfahren|iteratives]] [[Numerische Mathematik|numerisches Verfahren]] zur [[Approximation|approximativen]] Lösung eines [[Lineares Gleichungssystem|linearen Gleichungssystems]] <math>Ax=b</math>, <math>A \in \mathbb{R}^{n \times n}</math>. Es wird eingesetzt, wenn die [[Matrix (Mathematik)|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 [[Rekursion|Dreitermrekursion]] des [[Unsymmetrisches Lanczos-Verfahren|unsymmetrischen Lanczos-Verfahrens]].

Das BiCG-Verfahren wurde 1974 durch [[Roger Fletcher (Mathematiker)|Roger Fletcher]] eingeführt.

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]] von [[Henk van der Vorst]]. 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 <math>Ax=b</math> und <math>A^H\hat{x}=\hat{b}</math> auszugehen, wobei <math>A\in\mathbb{C}^{n\times n}</math> eine (im Allgemeinen nicht-[[Hermitesche Matrix|hermitesche]]) quadratische Matrix und <math>b\in\mathbb{C}^n</math> und <math>\hat{b}\in\mathbb{C}^n</math> gegebene rechte Seiten sind. Eigentlich ist man meist nur an der Lösung des ersten genannten Gleichungssystems interessiert. Gegeben seien ferner zwei Näherungslösungen <math>x_0\in\mathbb{C}^n</math> und <math>\hat{x}_0\in\mathbb{C}^n</math>.

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-Verfahren]]s verwandt. Die bekannteste Variante ist BiOmin und verwendet neben den rechten und linken [[Residuum (Numerische Mathematik)|Residuen]] <math>r_j</math> und <math>\hat{r}_j</math> ein Paar bikonjugierte Richtungen <math>p_j</math> und <math>\hat{p}_j</math> zur Residuenminimierung.

== BiOmin (BiCG in der Orthomin-Variante) ==
# Setze <math>r_0\leftarrow b-Ax_0</math>, <math>p_0\leftarrow r_0</math>
# Setze <math>\hat{r}_0\leftarrow \hat{b}-A^H\hat{x}_0</math>, <math>\hat{p}_0\leftarrow \hat{r}_0</math>
# for <math>k\in\mathbb{N}</math> do
# <math>\alpha_k\leftarrow \langle\hat{r}_k,r_k\rangle/\langle\hat{p}_k,Ap_k\rangle</math>
# <math>x_{k+1}\leftarrow x_k+\alpha_kp_k</math>
# <math>\hat{x}_{k+1}\leftarrow \hat{x}_k+\overline{\alpha_k}\hat{p}_k</math>
# <math>r_{k+1}\leftarrow r_k-\alpha_kAp_k</math>
# <math>\hat{r}_{k+1}\leftarrow \hat{r}_k-\overline{\alpha_k}A^H\hat{p}_k</math>
# <math>\beta_k\leftarrow \langle\hat{r}_{k+1},r_{k+1}\rangle/\langle\hat{r}_k,r_k\rangle</math>
# <math>p_{k+1}\leftarrow r_{k+1}+\beta_kp_k</math>
# <math>\hat{p}_{k+1}\leftarrow \hat{r}_{k+1}+\overline{\beta_k}\hat{p}_k</math>
# end for

Dabei kann Zeile 6 entfallen, falls wir nur an der Lösung des ersten Gleichungssystems interessiert sind. Die Wahl des zweiten Gleichungssystems, i. e., die Wahl von <math>\hat{b}</math> ist nicht trivial und beeinflusst stark die [[Stabilität (Numerik)|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

[[Kategorie:Numerische lineare Algebra]]

BiCG-Verfahren - Versionsgeschichte

imported>Bildungsbürger: -BKL-Link mit AWB