Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Conjugate residual method
open-in-new
<p>The conjugate residual method is an iterative <a href="/facts/Numeric_method/QT9cYa9z">numeric method</a> used for solving <a href="/facts/Systems_of_linear_equations/fk9CFdgp">systems of linear equations</a>. It's a <a href="/facts/Krylov_subspace_method/uKMAJhEh">Krylov subspace method</a> very similar to the much more popular <a href="/facts/Conjugate_gradient_method/AFwzBS4U">conjugate gradient method</a>, with similar construction and convergence properties. </p><p>This method is used to solve linear equations of the form </p> A x = b {\displaystyle \mathbf {A} \mathbf {x} =\mathbf {b} } <p>where A is an invertible and <a href="/facts/Hermitian_matrix/qArPblYo">Hermitian matrix</a>, and b is nonzero. </p><p>The conjugate residual method differs from the closely related <a href="/facts/Conjugate_gradient_method/AFwzBS4U">conjugate gradient method</a>. It involves more numerical operations and requires more storage. </p><p>Given an (arbitrary) initial estimate of the solution x 0 {\displaystyle \mathbf {x} _{0}} , the method is outlined below: </p> x 0 := Some initial guess r 0 := b − A x 0 p 0 := r 0 Iterate, with k starting at 0 : α k := r k T A r k ( A p k ) T A p k x k + 1 := x k + α k p k r k + 1 := r k − α k A p k β k := r k + 1 T A r k + 1 r k T A r k p k + 1 := r k + 1 + β k p k A p k + 1 := A r k + 1 + β k A p k k := k + 1 {\displaystyle {\begin{aligned}&\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:\\&\qquad \alpha _{k}:={\frac {\mathbf {r} _{k}^{\mathrm {T} }\mathbf {Ar} _{k}}{(\mathbf {Ap} _{k})^{\mathrm {T} }\mathbf {Ap} _{k}}}\\&\qquad \mathbf {x} _{k+1}:=\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k}\\&\qquad \mathbf {r} _{k+1}:=\mathbf {r} _{k}-\alpha _{k}\mathbf {Ap} _{k}\\&\qquad \beta _{k}:={\frac {\mathbf {r} _{k+1}^{\mathrm {T} }\mathbf {Ar} _{k+1}}{\mathbf {r} _{k}^{\mathrm {T} }\mathbf {Ar} _{k}}}\\&\qquad \mathbf {p} _{k+1}:=\mathbf {r} _{k+1}+\beta _{k}\mathbf {p} _{k}\\&\qquad \mathbf {Ap} _{k+1}:=\mathbf {Ar} _{k+1}+\beta _{k}\mathbf {Ap} _{k}\\&\qquad k:=k+1\end{aligned}}} <p>the iteration may be stopped once x k {\displaystyle \mathbf {x} _{k}} has been deemed converged. The only difference between this and the conjugate gradient method is the calculation of α k {\displaystyle \alpha _{k}} and β k {\displaystyle \beta _{k}} (plus the optional incremental calculation of A p k {\displaystyle \mathbf {Ap} _{k}} at the end). </p><p>Note: the above algorithm can be transformed so to make only one symmetric matrix-vector multiplication in each iteration. </p>