BiCG-Verfahren

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

Das BiCG-Verfahren ist ein iteratives numerisches Verfahren zur approximativen Lösung eines linearen Gleichungssystemes. 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 unstabil und anfällig für Rundungsfehler ist. Er ist unbestritten theoretisch interessant, denn er stellt den Ausgangspunkt der Entwicklung der LTPM dar, der Lanczos-type product methods (Lanczos-artigen Produkt-Methoden). 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 Daumenregel 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 $A x = 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 Gleichungsystemes 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 $r j$ und $\hat{r}_j$ ein Paar bikonjugierte Richtungen $p j$ und $\hat{p}_j$ zur Residuenminimierung.

[Bearbeiten] BiOmin (BiCG in der Orthomin-Variante)

Setze $r_0\leftarrow b-Ax_0$ , $p_0\leftarrow r_0$
Setze $\hat{r}_0\leftarrow \hat{b}-A^H\hat{x}_0$ , $\hat{p}_0\leftarrow \hat{r}_0$
for $k\in\mathbb{N}$ do
$\alpha_k\leftarrow \langle\hat{r}_k,r_k\rangle/\langle\hat{p}_k,Ap_k\rangle$
$x_{k+1}\leftarrow x_k+\alpha_kp_k$
$\hat{x}_{k+1}\leftarrow \hat{x}_k+\overline{\alpha_k}\hat{p}_k$
$r_{k+1}\leftarrow r_k-\alpha_kAp_k$
$\hat{r}_{k+1}\leftarrow \hat{r}_k-\overline{\alpha_k}A^H\hat{p}_k$
$\beta_k\leftarrow \langle\hat{r}_{k+1},r_{k+1}\rangle/\langle\hat{r}_k,r_k\rangle$
$p_{k+1}\leftarrow r_{k+1}+\beta_kp_k$
$\hat{p}_{k+1}\leftarrow \hat{r}_{k+1}+\overline{\beta_k}\hat{p}_k$
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.

Von „http://de.wikipedia.org../../../b/i/c/BiCG-Verfahren_edc2.html“

Kategorie: Numerische lineare Algebra

BiCG-Verfahren

aus Wikipedia, der freien Enzyklopädie

[Bearbeiten] BiOmin (BiCG in der Orthomin-Variante)

Views

Navigation

Mitmachen

Suche

Andere Sprachen