In mathematics, more specifically in numerical linear algebra, the biconjugate gradient method is an algorithm to solve systems of linear equations
Contents
Unlike the conjugate gradient method, this algorithm does not require the matrix
The algorithm
- Choose initial guess
x 0 , two other vectors x 0 ∗ b ∗ and a preconditioner M -
r 0 ← b − A x 0 -
r 0 ∗ ← b ∗ − x 0 ∗ A T -
p 0 ← M − 1 r 0 -
p 0 ∗ ← r 0 ∗ M − 1 - for
k = 0 , 1 , … do-
α k ← r k ∗ M − 1 r k p k ∗ A p k -
x k + 1 ← x k + α k ⋅ p k -
x k + 1 ∗ ← x k ∗ + α k ¯ ⋅ p k ∗ -
r k + 1 ← r k − α k ⋅ A p k -
r k + 1 ∗ ← r k ∗ − α k ¯ ⋅ p k ∗ A -
β k ← r k + 1 ∗ M − 1 r k + 1 r k ∗ M − 1 r k -
p k + 1 ← M − 1 r k + 1 + β k ⋅ p k -
p k + 1 ∗ ← r k + 1 ∗ M − 1 + β k ¯ ⋅ p k ∗
-
In the above formulation, the computed
and thus are the respective residuals corresponding to
Unpreconditioned version of the algorithm
- Choose initial guess
x 0 , -
r 0 ← b − A x 0 -
r ^ 0 ← b ^ − x ^ 0 A T -
p 0 ← r 0 -
p ^ 0 ← r ^ 0 - for
k = 0 , 1 , … do-
α k ← r ^ k r k p ^ k A p k -
x k + 1 ← x k + α k ⋅ p k -
x ^ k + 1 ← x ^ k + α k ⋅ p ^ k -
r k + 1 ← r k − α k ⋅ A p k -
r ^ k + 1 ← r ^ k − α k ⋅ p ^ k A T -
β k ← r ^ k + 1 r k + 1 r ^ k r k -
p k + 1 ← r k + 1 + β k ⋅ p k -
p ^ k + 1 ← r ^ k + 1 + β k ⋅ p ^ k
-
Discussion
The biconjugate gradient method is numerically unstable (compare to the biconjugate gradient stabilized method), but very important from a theoretical point of view. Define the iteration steps by
where
with
These related projections may be iterated themselves as
A relation to Quasi-Newton methods is given by
The new directions
are then orthogonal to the residuals:
which themselves satisfy
where
The biconjugate gradient method now makes a special choice and uses the setting
With this particular choice, explicit evaluations of