Conjugate residual method explained

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

A x = 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. It involves more numerical operations and requires more storage.

Given an (arbitrary) initial estimate of the solution

x _{0} , the method is outlined below:\begin{align} & x _{0} : = Someinitialguess \\ & r _{0} : = b - Ax _{0} \\ & p _{0} : = r _{0} \\ & Iterate,with k startingat 0 :\\ & \alpha _{k} : = (r ^{T} _{k} Ar _{k})/(( Ap ^{T} _{k)} Ap _{k}) \\ & x _{k+1} : = x _{k} + \alpha _{k} p _{k} \\ & r _{k+1} : = r _{k} - \alpha _{k} Ap _{k} \\ & \beta _{k} : = (r ^{T} _{k +1} Ar _{k+1})/(r ^{T} _{k} Ar _{k}) \\ & p _{k+1} : = r _{k+1} + \beta _{k} p _{k} \\ & Ap _{k} : = Ar _{k+1} + \beta _{k} Ap _{k} \\ & k : = k + 1 \end{align}

the iteration may be stopped once

x _{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 Ap _{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{align} & x _{0} : = Someinitialguess \\ & r _{0} : = M ^{-1} ( b - Ax _{0)} \\ & p _{0} : = r _{0} \\ & Iterate,with k startingat 0 : \\ & \alpha _{k} : = (r ^{T} _{k} A r _{k})/(( Ap ^{T} _{k)} M ^{-1} Ap _{k}) \\ & x _{k+1} : = x _{k} + \alpha _{k} p _{k} \\ & r _{k+1} : = r _{k} - \alpha _{k} M ^{-1} Ap _{k} \\ & \beta _{k} : = (r ^{T} _{k +1} A r _{k})/(r ^{T} _{k} A r _{k}) \\ & p _{k+1} : = r _{k+1} + \beta _{k} p _{k} \\ & Ap _{k} : = A r _{k+1} + \beta _{k} Ap _{k} \\ & k : = k + 1 \\ \end{align} M ^{-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. .