The conjugate gradient method (CG) is an iterative algorithm for solving a system of linear equations when is a real symmetric positive-definite matrix, or, in the complex case, a Hermitian positive-definite matrix. It is especially important in numerical linear algebra because it requires matrix–vector products rather than an explicit matrix factorization and stores only a small number of vectors. Equivalently, CG minimizes a strictly convex quadratic function by moving along directions that are mutually conjugate with respect to .
Mathematical formulation
Consider
where
These assumptions guarantee a unique solution .
The same solution is the unique minimizer of the quadratic objective function
Its gradient is
Thus the residual
is the negative gradient. The positive definiteness of makes this a problem in convex optimization.
The matrix defines an inner product and an associated energy norm:
The objective error satisfies
Consequently, minimizing the quadratic is equivalent to minimizing the error in the energy norm.
Conjugate directions
Two nonzero directions and are -conjugate if
They need not be perpendicular in the ordinary Euclidean sense. Instead, they are orthogonal in the geometry defined by .
Suppose an iterate is updated along a direction :
Exact minimization along that line gives
When the directions are mutually -conjugate, a later update does not undo the minimization already achieved along an earlier direction. A set of nonzero mutually conjugate directions is linearly independent, so these directions can determine the solution in at most steps in exact arithmetic.
Unlike steepest descent, which always follows the current negative gradient, CG combines the residual with the preceding search direction. This avoids the repeated zigzagging that steepest descent can exhibit on elongated quadratic level sets.
Standard algorithm
Choose an initial approximation , and set
If , the initial approximation already solves the system. Otherwise, for , compute
After checking for convergence, form
In exact arithmetic, as long as convergence has not occurred, the denominator is positive. The recurrence generates
and
Thus the residuals are mutually orthogonal in the Euclidean inner product, whereas the search directions are mutually -conjugate. These are distinct properties.
For complex Hermitian positive-definite systems, the formulas use the conjugate transpose in place of the ordinary transpose.
Krylov-subspace interpretation
CG belongs to the family of Krylov subspace methods. Starting from , define
The -th iterate satisfies
and is characterized by
Equivalently,
This is a projection condition: the residual is orthogonal to the subspace in which the correction is sought.
CG therefore finds the best energy-norm approximation available in an expanding sequence of spaces, rather than making only a locally optimal choice along the latest gradient. The spaces are nested, so the energy-norm error decreases monotonically in exact arithmetic. The Euclidean norm of the residual, however, need not decrease at every iteration.
CG is closely related to the Lanczos algorithm, which constructs an orthogonal basis of a Krylov subspace and reduces a symmetric matrix to tridiagonal form. This relationship explains how CG can achieve its projection property using short recurrences rather than retaining every previous direction.
Convergence and spectral behavior
Let
be the spectral condition number of the positive-definite matrix. In exact arithmetic, the standard bound is
For , this bound gives a worst-case iteration estimate proportional to
for reducing the relative energy-norm error to a prescribed tolerance .
The bound can be pessimistic because it uses only the largest and smallest eigenvalues. Actual convergence depends on the whole spectrum and on the components of the initial error in the corresponding eigenspaces.
To see this, write . The error has the form
where is a polynomial of degree at most satisfying . CG implicitly selects an error polynomial that minimizes the energy norm. Eigenvalue clusters can permit effective polynomials of relatively low degree, producing convergence much faster than the condition-number estimate suggests.
In exact arithmetic, CG terminates after no more than the number of distinct eigenvalues represented in the initial error, and therefore after at most iterations. Finite precision generally prevents this finite-termination statement from serving as a practical iteration limit.
Preconditioning
A preconditioner changes the system's effective geometry to improve convergence. For standard preconditioned CG (PCG), a fixed symmetric positive-definite matrix is chosen so that solving
is inexpensive and the transformed system is better conditioned.
The symmetric transformed problem is
An implementation does not normally construct the square root. Instead, it applies through solves or an equivalent operator.
With , initialize and use
followed by the usual iterate and residual updates. Then compute
Typical choices include diagonal scaling, incomplete Cholesky factorization, domain-decomposition methods, and suitable symmetric multigrid cycles. Their value depends on total computational cost, not iteration count alone: a more accurate preconditioner can be too expensive to construct or apply.
Although generally is not symmetric in the Euclidean inner product, PCG is not simply ordinary CG applied naively to that matrix. Its justification comes from the symmetric transformed problem, or equivalently from an appropriate weighted inner product. Variable or nonsymmetric preconditioning requires additional care and may call for different algorithms.
Computational cost and implementation
A standard iteration requires one matrix–vector product, a few vector updates, and a small number of inner products. For a sparse matrix with stored nonzero entries, the matrix–vector product typically costs , with vector work costing . Working-vector storage is , in addition to storage for the matrix and preconditioner.
CG is also suitable for matrix-free computation: only a routine that evaluates is needed. The entries of need not be explicitly assembled.
These features make CG attractive when direct factorization would require excessive memory because of fill-in. Direct methods may nevertheless be preferable for smaller systems, difficult conditioning, or many right-hand sides when factorization costs can be amortized.
In parallel computing, matrix–vector products and vector updates can often be distributed effectively. Inner products require global reductions, whose communication latency can become a bottleneck. Pipelined and communication-reducing variants seek to address this cost, but their altered recurrences can also affect numerical behavior.
Finite precision and stopping criteria
Under floating-point arithmetic, residual orthogonality and direction conjugacy gradually deteriorate. The recursively updated residual can differ from the true residual:
This residual gap can limit attainable accuracy or cause a stopping test based only on the recursive residual to be misleading. Explicit residual checks and carefully designed residual-replacement strategies can help monitor this behavior.
A common stopping criterion is
where the two tolerances specify absolute and relative residual thresholds.
A small residual does not necessarily imply a comparably small forward error. For ,
Ill-conditioning can therefore amplify the relationship between residual and solution error. Questions of attainable accuracy and numerical stability must be distinguished from the exact-arithmetic convergence theory.
Applications and limitations
CG is widely used for systems arising from discretizations of partial differential equations, including suitable formulations of the Poisson equation and elliptic boundary-value problems. The finite element method often produces symmetric positive-definite systems when the underlying problem and boundary conditions have the required properties.
Other applications include quadratic optimization, computational mechanics, and inner linear solves in Newton-type methods. It also appears in inverse problems, where early termination can act as a form of regularization by limiting the influence of poorly determined spectral components.
Standard CG is not a general solver for arbitrary matrices:
- Symmetric indefinite systems: positive-definite energy minimization no longer applies, and denominators can vanish or become negative. Methods such as MINRES are designed for this setting.
- Nonsymmetric systems: methods such as GMRES or BiCGSTAB are generally more appropriate.
- Positive-semidefinite systems: compatible systems can sometimes be handled within the relevant subspace, but uniqueness and the standard positive-definite guarantees require modification.
- Least-squares problems: CG can be applied to when has full column rank, but the normal matrix has . Specialized methods such as CGLS and LSQR avoid explicitly forming that matrix, although they do not remove the underlying conditioning difficulty.
Nonlinear conjugate gradient methods
Nonlinear conjugate gradient methods extend the short-recurrence idea to general smooth optimization. They use directions such as
and select step lengths through a line search.
Different formulas for define methods including Fletcher–Reeves and Polak–Ribière. For a positive-definite quadratic with exact line searches, standard versions reduce to linear CG. For general nonlinear objectives, exact conjugacy and finite termination are lost; convergence depends on the update formula, line-search conditions, and possible restarts.
Historical development
Magnus Hestenes and Eduard Stiefel introduced the classical method in their 1952 paper Methods of Conjugate Gradients for Solving Linear Systems. Its exact-arithmetic finite-termination property initially connected it with elimination-style approaches, but its lasting importance developed through its use as an iterative method for large sparse systems.
The growth of scientific computing, sparse matrix techniques, and effective preconditioners made preconditioned conjugate gradients a central method for large-scale numerical simulation.