Conjugate residual method

The conjugate residual method is an iterative numeric method used for solving systems of linear equations. It's a Krylov subspace method very similar to the much more popular conjugate gradient method, with similar construction and convergence properties.

This method is used to solve linear equations of the form

$\mathbf {A} \mathbf {x} =\mathbf {b}$

where A is an invertible and Hermitian matrix, and b is nonzero.

The conjugate residual method differs from the closely related conjugate gradient method primarily in that it involves somewhat more computation but is applicable to problems that aren't positive definite; in fact the only requirement (besides the obvious invertible A and nonzero b) is that A be Hermitian (or, with real numbers, symmetric). This makes the conjugate residual method applicable to problems which intuitively require finding saddle points instead of minima, such as numeric optimization with Lagrange multiplier constraints.

Given an (arbitrary) initial estimate of the solution $\mathbf {x} _{0}$, the method is outlined below:

$\mathbf {x} _{0}={\text{Some initial guess}}\,$

$\mathbf {r} _{0}=\mathbf {b} -\mathbf {Ax} _{0}\,$

$\mathbf {p} _{0}=\mathbf {r} _{0}\,$

${\text{Iterate, with }}k{\text{ starting at }}0:$

$\alpha _{k}={\frac {\mathbf {r} _{k}^{\mathrm {T} }\mathbf {Ar} _{k}}{(\mathbf {Ap} _{k})^{\mathrm {T} }\mathbf {Ap} _{k}}}\,$

$\mathbf {x} _{k+1}=\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k}\,$

$\mathbf {r} _{k+1}=\mathbf {r} _{k}-\alpha _{k}\mathbf {Ap} _{k}\,$

$\beta _{k}={\frac {\mathbf {r} _{k+1}^{\mathrm {T} }\mathbf {Ar} _{k+1}}{\mathbf {r} _{k}^{\mathrm {T} }\mathbf {Ar} _{k}}}\,$

$\mathbf {p} _{k+1}=\mathbf {r} _{k+1}+\beta _{k}\mathbf {p} _{k}\,$

$\mathbf {Ap} _{k+1}=\mathbf {Ar} _{k+1}+\beta _{k}\mathbf {Ap} _{k}\,$

$k:=k+1\,$

the iteration may be stopped once $\mathbf {x} _{k}$ has been deemed converged. Note that the only difference between this and the conjugate gradient method is the calculation of $\alpha _{k}$ and $\beta _{k}$ (plus the optional recursive calculation of $\mathbf {Ap} _{k}$ at the end).

Preconditioning

By making a few substitutions and variable changes, a preconditioned conjugate residual method may be derived in the same way as done for the conjugate gradient method:

$\mathbf {x} _{0}={\text{Some initial guess}}\,$

$\mathbf {r} _{0}=\mathbf {M} ^{-1}(\mathbf {b} -\mathbf {Ax} _{0})\,$

$\mathbf {p} _{0}=\mathbf {r} _{0}\,$

${\text{Iterate, with }}k{\text{ starting at }}0:$

$\alpha _{k}={\frac {\mathbf {r} _{k}^{\mathrm {T} }\mathbf {A} \mathbf {r} _{k}}{(\mathbf {Ap} _{k})^{\mathrm {T} }\mathbf {M} ^{-1}\mathbf {Ap} _{k}}}\,$

$\mathbf {x} _{k+1}=\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k}\,$

$\mathbf {r} _{k+1}=\mathbf {r} _{k}-\alpha _{k}\mathbf {M} ^{-1}\mathbf {Ap} _{k}\,$

$\beta _{k}={\frac {\mathbf {r} _{k+1}^{\mathrm {T} }\mathbf {A} \mathbf {r} _{k+1}}{\mathbf {r} _{k}^{\mathrm {T} }\mathbf {A} \mathbf {r} _{k}}}\,$

$\mathbf {p} _{k+1}=\mathbf {r} _{k+1}+\beta _{k}\mathbf {p} _{k}\,$

$\mathbf {Ap} _{k+1}=\mathbf {A} \mathbf {r} _{k+1}+\beta _{k}\mathbf {Ap} _{k}\,$

$k:=k+1\,$

The preconditioner $\mathbf {M} ^{-1}$ must be symmetric. Note that the residual vector here is different from the residual vector without preconditioning.

References

• Yousef Saad, Iterative methods for sparse linear systems (2nd ed.), pages 181–182, SIAM. ISBN 978-0898715347.
• Jonathan Richard Shewchuck, An Introduction to the Conjugate Gradient Method Without the Agonizing Pain (edition $1{\tfrac {1}{4}}$), pages 39–40.