BiCG-Verfahren

Das BiCG-Verfahren ist ein iteratives numerisches Verfahren zur approximativen Lösung eines linearen Gleichungssystems ${\displaystyle Ax=b}$ , ${\displaystyle 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.

Das BiCG-Verfahren w​urde 1974 d​urch Roger Fletcher eingeführt.

Der Algorithmus w​ird in d​er Praxis selten verwendet, d​a er ziemlich instabil u​nd anfällig für Rundungsfehler ist. Er i​st unbestritten theoretisch interessant, d​enn er stellt d​en Ausgangspunkt d​er Entwicklung d​er LTPM, d​er Lanczos-type product methods (Lanczos-artigen Produkt-Methoden) dar. Dazu zählen d​as (noch stärker instabile) CGS-Verfahren u​nd als Versuch d​er Stabilisierung d​es CGS-Verfahrens d​as (ebenfalls ziemlich instabile) BiCGSTAB-Verfahren v​on Henk v​an der Vorst. Unter d​en Experten g​ibt es z​wei Lager. Die e​inen glauben, d​ass eine bessere Fehleranalyse d​er Verfahren Gründe für d​ie Instabilitäten aufzeigen würde u​nd damit zumindest für Spezialfälle z​u stabilen Verfahren führen würde, d​ie anderen glauben, d​ass diese Verfahren niemals stabil s​ein können, u​nd verwenden d​aher eher GMRES m​it Verfeinerungen. Als Faustregel lässt s​ich festhalten: Anwender u​nd kommerzielle Softwarepakete verwenden angepasste direkte Methoden, v​iele Forscher u​nd Universitäten arbeiten m​it den LTPM i​n allerlei Varianten.

Es hilft beim Verständnis des Algorithmus, von zwei zu lösenden Gleichungssystemen der Gestalt ${\displaystyle Ax=b}$ und ${\displaystyle A^{H}{\hat {x}}={\hat {b}}}$ auszugehen, wobei ${\displaystyle A\in \mathbb {C} ^{n\times n}}$ eine (im Allgemeinen nicht-hermitesche) quadratische Matrix und ${\displaystyle b\in \mathbb {C} ^{n}}$ und ${\displaystyle {\hat {b}}\in \mathbb {C} ^{n}}$ 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 ${\displaystyle x_{0}\in \mathbb {C} ^{n}}$ und ${\displaystyle {\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 ${\displaystyle r_{j}}$ und ${\displaystyle {\hat {r}}_{j}}$ ein Paar bikonjugierte Richtungen ${\displaystyle p_{j}}$ und ${\displaystyle {\hat {p}}_{j}}$ zur Residuenminimierung.

BiOmin (BiCG in der Orthomin-Variante)

1. Setze ${\displaystyle r_{0}\leftarrow b-Ax_{0}}$ , ${\displaystyle p_{0}\leftarrow r_{0}}$
2. Setze ${\displaystyle {\hat {r}}_{0}\leftarrow {\hat {b}}-A^{H}{\hat {x}}_{0}}$ , ${\displaystyle {\hat {p}}_{0}\leftarrow {\hat {r}}_{0}}$
3. for ${\displaystyle k\in \mathbb {N} }$ do
4. ${\displaystyle \alpha _{k}\leftarrow \langle {\hat {r}}_{k},r_{k}\rangle /\langle {\hat {p}}_{k},Ap_{k}\rangle }$
5. ${\displaystyle x_{k+1}\leftarrow x_{k}+\alpha _{k}p_{k}}$
6. ${\displaystyle {\hat {x}}_{k+1}\leftarrow {\hat {x}}_{k}+{\overline {\alpha _{k}}}{\hat {p}}_{k}}$
7. ${\displaystyle r_{k+1}\leftarrow r_{k}-\alpha _{k}Ap_{k}}$
8. ${\displaystyle {\hat {r}}_{k+1}\leftarrow {\hat {r}}_{k}-{\overline {\alpha _{k}}}A^{H}{\hat {p}}_{k}}$
9. ${\displaystyle \beta _{k}\leftarrow \langle {\hat {r}}_{k+1},r_{k+1}\rangle /\langle {\hat {r}}_{k},r_{k}\rangle }$
10. ${\displaystyle p_{k+1}\leftarrow r_{k+1}+\beta _{k}p_{k}}$
11. ${\displaystyle {\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 Gleichungssystems interessiert sind. Die Wahl des zweiten Gleichungssystems, i. e., die Wahl von ${\displaystyle {\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