Derivation of the conjugate gradient method

In <a href="/facts/Numerical_linear_algebra/jnS6Tteb">numerical linear algebra</a>, the <a href="/facts/Conjugate_gradient_method/AFwzBS4U">conjugate gradient method</a> is an <a href="/facts/Iterative_method/uKMAJhEh">iterative method</a> for numerically solving the <a href="/facts/System_of_linear_equations/fk9CFdgp">linear system</a>

A
          x
        
        =
        
          b
        
      
    
    {\displaystyle {\boldsymbol {Ax}}={\boldsymbol {b}}}

where 
 
 
 
 
 A
 
 
 
 {\displaystyle {\boldsymbol {A}}}
 
 is <a href="/facts/Symmetric_matrix/08CGwjNl">symmetric</a> <a href="/facts/Positive-definite_matrix/Hbr6AuPS">positive-definite</a>, without computing 
 
 
 
 
 
 A
 
 
 −
 1
 
 
 
 
 {\displaystyle {\boldsymbol {A}}^{-1}}
 
 explicitly. The conjugate gradient method can be derived from several different perspectives, including specialization of the conjugate direction method for <a href="/facts/Optimization_(mathematics)/oRn8Iv5I">optimization</a>, and variation of the <a href="/facts/Arnoldi_iteration/7bnLdCgy">Arnoldi</a>/<a href="/facts/Lanczos_iteration/t3n5RYKr">Lanczos</a> iteration for <a href="/facts/Eigenvalue/8TjEoT8u">eigenvalue</a> problems.
The intent of this article is to document the important steps in these derivations.

Derivation of the conjugate gradient method open-in-new

Derivation of the conjugate gradient method