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

$𝐀𝐱=𝐛$

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

The conjugate residual method differs from the closely related conjugate gradient method. It involves more numerical operations and requires more storage.

Given an (arbitrary) initial estimate of the solution ${𝐱}_0$, the method is outlined below:

$\begin{array}{cc}& {𝐱}_0:=\text{Some initial guess}\\ & {𝐫}_0:=𝐛-{𝐀𝐱}_0\\ & {𝐩}_0:={𝐫}_0\\ & \text{Iterate, with }k\text{ starting at }0:\\ & {\alpha }_k:=\frac{{𝐫}_k^{\mathrm{T}}{𝐀𝐫}_k}{({𝐀𝐩}_k{)}^{\mathrm{T}}{𝐀𝐩}_k}\\ & {𝐱}_{k+1}:={𝐱}_k+{\alpha }_k{𝐩}_k\\ & {𝐫}_{k+1}:={𝐫}_k-{\alpha }_k{𝐀𝐩}_k\\ & {\beta }_k:=\frac{{𝐫}_{k+1}^{\mathrm{T}}{𝐀𝐫}_{k+1}}{{𝐫}_k^{\mathrm{T}}{𝐀𝐫}_k}\\ & {𝐩}_{k+1}:={𝐫}_{k+1}+{\beta }_k{𝐩}_k\\ & {𝐀𝐩}_{k+1}:={𝐀𝐫}_{k+1}+{\beta }_k{𝐀𝐩}_k\\ & k:=k+1\end{array}$

the iteration may be stopped once ${𝐱}_k$ has been deemed converged. The only difference between this and the conjugate gradient method is the calculation of ${\alpha }_k$ and ${\beta }_k$ (plus the optional incremental calculation of ${𝐀𝐩}_k$ at the end).

Note: the above algorithm can be transformed so to make only one symmetric matrix-vector multiplication in each iteration.

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:

$\begin{array}{cc}& {𝐱}_0:=\text{Some initial guess}\\ & {𝐫}_0:={𝐌}^{-1}(𝐛-{𝐀𝐱}_0)\\ & {𝐩}_0:={𝐫}_0\\ & \text{Iterate, with }k\text{ starting at }0:\\ & {\alpha }_k:=\frac{{𝐫}_k^{\mathrm{T}}𝐀{𝐫}_k}{({𝐀𝐩}_k{)}^{\mathrm{T}}{𝐌}^{-1}{𝐀𝐩}_k}\\ & {𝐱}_{k+1}:={𝐱}_k+{\alpha }_k{𝐩}_k\\ & {𝐫}_{k+1}:={𝐫}_k-{\alpha }_k{𝐌}^{-1}{𝐀𝐩}_k\\ & {\beta }_k:=\frac{{𝐫}_{k+1}^{\mathrm{T}}𝐀{𝐫}_{k+1}}{{𝐫}_k^{\mathrm{T}}𝐀{𝐫}_k}\\ & {𝐩}_{k+1}:={𝐫}_{k+1}+{\beta }_k{𝐩}_k\\ & {𝐀𝐩}_{k+1}:=𝐀{𝐫}_{k+1}+{\beta }_k{𝐀𝐩}_k\\ & k:=k+1\\ \end{array}$

The preconditioner ${𝐌}^{-1}$ must be symmetric positive definite. 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.), page 194, SIAM. Template:ISBN.