Conjugate Gradient Method

Updated 01 Oct 2026

•
What it is
- •
  solves a real symmetric positive-definite system using search directions conjugate with respect to $A$
•
Interpretation
- •
  minimizes $q(x)=\frac12x^TAx-b^Tx$
•
Iteration
- •
  initialize $r_0=b-Ax_0$ and $p_0=r_0$ .
- •
  $\alpha_k=(r_k^Tr_k)/(p_k^TAp_k)$ .
- •
  $x_{k+1}=x_k+\alpha_kp_k$ and $r_{k+1}=r_k-\alpha_kAp_k$ .
- •
  $\beta_k=(r_{k+1}^Tr_{k+1})/(r_k^Tr_k)$ and $p_{k+1}=r_{k+1}+\beta_kp_k$ .
•
Limitations
- •
  the at-most- $n$ -steps statement assumes exact arithmetic; floating-point behavior differs
- •
  standard CG is not general solver for arbitrary nonsymmetric or indefinite matrices
•
Related
- •
  Preconditioning
- •
  Sparse Matrix

Linked references 5