iteratives Krylow-Raum-Verfahren zur Lösung eines linearen Gleichungs-systems Ax = b, wobei A ∈ ℝ^n×n eine beliebige (insbesondere unsymmetrische) Matrix sei. Da im Laufe der Berechnungen lediglich Matrix-Vektor Multiplikationen benötigt werden, ist das Verfahren besonders für große sparse Matrizen A geeignet.

Das BiCG-Verfahren ist eine Verallgemeinerung des konjugierten Gradienten-Verfahrens für Gleichungssysteme mit symmetrisch positiv definiten Koeffizientenmatrizen.

Es wird dabei, ausgehend von einem (beliebigen) Startvektor x⁽⁰⁾, eine Folge von Näherungsvektoren x^(k) an die gesuchte Lösung x gebildet. Dabei wird der Vektor x^(k) so gewählt, daß

\begin{eqnarray}{x}^{(k)}\in \{{x}^{(0)}+{{\mathscr{K}}}_{k}(A,{r}^{(0)})\end{eqnarray}

für

\begin{eqnarray}{r}^{(0)}=b-A{x}^{(0)}\end{eqnarray}

und zusätzlich so, daß

\begin{eqnarray}{r}^{(k)}=b-A{x}^{(k)}\perp {{\mathscr{K}}}_{k}(A,{s}^{(0)})\end{eqnarray}

für ein s₍₀₎ ∈ ℝ_n.

Dabei bezeichnet \({{\mathscr{K}}}_{k}(A,x)\) den Krylow-Raum

\begin{eqnarray}{{\mathscr{K}}}_{k}(A,\text{}x)=\{x,Ax,{A}^{2}x,\ldots ,{A}^{k-1}x\}.\end{eqnarray}

Man verwendet das unsymmetrische Lanczos-Verfahren zur Berechnung einer Basis dieser Krylow-Räume, da sich dann kurze Rekursionsformeln für die Berechnung des nächsten Vektors x^(k) ergeben. Zur Berechnung von x^(k) wird so lediglich der Vektor x^{(k − 1)} und der (k − 1)-te Spaltenvektor von Q_k benötigt.

Nach k Schritten des Lanczos-Verfahrens erhält man

\begin{eqnarray}A{Q}_{k} & = & {Q}_{k}{T}_{k}+{r}_{k}{e}_{k}^{T},\\ {A}^{T}{P}_{k} & = & {P}_{k}{T}_{k}^{T}+{s}_{k}^{T}{e}_{k},\\ {P}_{k}^{T}{Q}_{k} & = & I\end{eqnarray}

mit

\begin{eqnarray}{T}_{k}=({\alpha }_{1} & {\beta }_{1} & & & \\ {\beta }_{1} & {\alpha }_{1} & {\beta }_{2} & & \\ & \ddots & \ddots & \ddots & \\ & & \ddots & \ddots & {\beta }_{k-1}\\ & & & {\beta }_{k-1} & {\alpha }_{k})\in {{\mathbb{R}}}^{k\times k}.\end{eqnarray}

y^(k) ist als die Lösung des linearen Ausgleichsproblems

\begin{eqnarray}\mathop{\min }\limits_{y\in {{\mathbb{R}}}^{k}}{\Vert \frac{{e}_{1}}{{\Vert {r}^{(0)}\Vert }_{2}}-{T}_{k}y\Vert }_{2}\end{eqnarray}

zu wählen, wobei \({e}_{1}={[1,0,\ldots ,0]}^{T}\in {{\mathbb{R}}}^{k}\). Das Ausgleichsproblem kann effizient mittels der Methode der kleinsten Quadrate gelöst werden.

Aufgrund des zugrundeliegenden Lanczos-Verfahrens kann das BiCG-Verfahren vorzeitig zusammenbrechen, ohne eine Lösung des Problems zu berechnen. Mithilfe von sogenannten look-ahead Techniken ist es möglich, diese Probleme zu umgehen.