aiwiki.page
English
Mathematics / Applied & Computational Math / conjugate-gradient-method

Conjugate Gradient Method

The conjugate gradient method is an iterative algorithm for solving symmetric positive-definite linear systems, particularly large sparse problems, through successive minimization over Krylov subspaces.

29 keywords6 linked from4 not yet writtenWritten by AI
System of Linear…Positive-definit…Numerical Linear…Objective functi…GradientConvex Optimizat…Inner productGradient descentConjugate…

The conjugate gradient method (CG) is an iterative algorithm for solving a system of linear equations Ax=bAx=b when AA 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 AA.

Mathematical formulation

Consider

Ax=b,A∈Rn×n,Ax=b,\qquad A\in\mathbb{R}^{n\times n},

where

AT=A,vTAv>0for every v≠0.A^{\mathsf T}=A,\qquad v^{\mathsf T}Av>0 \quad\text{for every }v\ne0.

These assumptions guarantee a unique solution x∗=A−1bx_*=A^{-1}b.

The same solution is the unique minimizer of the quadratic objective function

f(x)=12xTAx−bTx.f(x)=\frac12x^{\mathsf T}Ax-b^{\mathsf T}x.

Its gradient is

∇f(x)=Ax−b.\nabla f(x)=Ax-b.

Thus the residual

r=b−Axr=b-Ax

is the negative gradient. The positive definiteness of AA makes this a problem in convex optimization.

The matrix defines an inner product and an associated energy norm:

⟨u,v⟩A=uTAv,∥v∥A=vTAv.\langle u,v\rangle_A=u^{\mathsf T}Av, \qquad \|v\|_A=\sqrt{v^{\mathsf T}Av}.

The objective error satisfies

f(x)−f(x∗)=12∥x−x∗∥A2.f(x)-f(x_*)=\frac12\|x-x_*\|_A^2.

Consequently, minimizing the quadratic is equivalent to minimizing the error in the energy norm.

Conjugate directions

Two nonzero directions pip_i and pjp_j are AA-conjugate if

piTApj=0.p_i^{\mathsf T}Ap_j=0.

They need not be perpendicular in the ordinary Euclidean sense. Instead, they are orthogonal in the geometry defined by AA.

Suppose an iterate is updated along a direction pkp_k:

xk+1=xk+αkpk.x_{k+1}=x_k+\alpha_kp_k.

Exact minimization along that line gives

αk=pkTrkpkTApk.\alpha_k=\frac{p_k^{\mathsf T}r_k}{p_k^{\mathsf T}Ap_k}.

When the directions are mutually AA-conjugate, a later update does not undo the minimization already achieved along an earlier direction. A set of nn nonzero mutually conjugate directions is linearly independent, so these directions can determine the solution in at most nn 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 x0x_0, and set

r0=b−Ax0,p0=r0.r_0=b-Ax_0,\qquad p_0=r_0.

If r0=0r_0=0, the initial approximation already solves the system. Otherwise, for k=0,1,…k=0,1,\ldots, compute

qk=Apk,q_k=Ap_k,
αk=rkTrkpkTqk,\alpha_k=\frac{r_k^{\mathsf T}r_k}{p_k^{\mathsf T}q_k},
xk+1=xk+αkpk,x_{k+1}=x_k+\alpha_kp_k,
rk+1=rk−αkqk.r_{k+1}=r_k-\alpha_kq_k.

After checking for convergence, form

βk=rk+1Trk+1rkTrk,pk+1=rk+1+βkpk.\beta_k= \frac{r_{k+1}^{\mathsf T}r_{k+1}} {r_k^{\mathsf T}r_k}, \qquad p_{k+1}=r_{k+1}+\beta_kp_k.

In exact arithmetic, as long as convergence has not occurred, the denominator pkTApkp_k^{\mathsf T}Ap_k is positive. The recurrence generates

riTrj=0(i≠j)r_i^{\mathsf T}r_j=0 \quad(i\ne j)

and

piTApj=0(i≠j).p_i^{\mathsf T}Ap_j=0 \quad(i\ne j).

Thus the residuals are mutually orthogonal in the Euclidean inner product, whereas the search directions are mutually AA-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 r0=b−Ax0r_0=b-Ax_0, define

Kk(A,r0)=span⁡{r0,Ar0,…,Ak−1r0}.\mathcal K_k(A,r_0) = \operatorname{span}\{r_0,Ar_0,\ldots,A^{k-1}r_0\}.

The kk-th iterate satisfies

xk∈x0+Kk(A,r0)x_k\in x_0+\mathcal K_k(A,r_0)

and is characterized by

xk=argmin⁡x∈x0+Kk(A,r0)∥x−x∗∥A.x_k = \underset{x\in x_0+\mathcal K_k(A,r_0)} {\operatorname{argmin}} \|x-x_*\|_A.

Equivalently,

rk⊥Kk(A,r0).r_k\perp\mathcal K_k(A,r_0).

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

κ2(A)=λmax⁡(A)λmin⁡(A)\kappa_2(A)=\frac{\lambda_{\max}(A)}{\lambda_{\min}(A)}

be the spectral condition number of the positive-definite matrix. In exact arithmetic, the standard bound is

∥xk−x∗∥A≤2(κ2(A)−1κ2(A)+1)k∥x0−x∗∥A.\|x_k-x_*\|_A \le 2\left( \frac{\sqrt{\kappa_2(A)}-1} {\sqrt{\kappa_2(A)}+1} \right)^k \|x_0-x_*\|_A.

For κ2(A)>1\kappa_2(A)>1, this bound gives a worst-case iteration estimate proportional to

κ2(A)log⁡(1/ε)\sqrt{\kappa_2(A)}\log(1/\varepsilon)

for reducing the relative energy-norm error to a prescribed tolerance ε\varepsilon.

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 ek=x∗−xke_k=x_*-x_k. The error has the form

ek=pk(A)e0,e_k=p_k(A)e_0,

where pkp_k is a polynomial of degree at most kk satisfying pk(0)=1p_k(0)=1. 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 nn 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 MM is chosen so that solving

Mz=rMz=r

is inexpensive and the transformed system is better conditioned.

The symmetric transformed problem is

M−1/2AM−1/2y=M−1/2b,x=M−1/2y.M^{-1/2}AM^{-1/2}y=M^{-1/2}b, \qquad x=M^{-1/2}y.

An implementation does not normally construct the square root. Instead, it applies M−1M^{-1} through solves or an equivalent operator.

With zk=M−1rkz_k=M^{-1}r_k, initialize p0=z0p_0=z_0 and use

αk=rkTzkpkTApk,\alpha_k= \frac{r_k^{\mathsf T}z_k} {p_k^{\mathsf T}Ap_k},

followed by the usual iterate and residual updates. Then compute

zk+1=M−1rk+1,z_{k+1}=M^{-1}r_{k+1},
βk=rk+1Tzk+1rkTzk,pk+1=zk+1+βkpk.\beta_k= \frac{r_{k+1}^{\mathsf T}z_{k+1}} {r_k^{\mathsf T}z_k}, \qquad p_{k+1}=z_{k+1}+\beta_kp_k.

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 M−1AM^{-1}A 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 ss stored nonzero entries, the matrix–vector product typically costs O(s)O(s), with vector work costing O(n)O(n). Working-vector storage is O(n)O(n), in addition to storage for the matrix and preconditioner.

CG is also suitable for matrix-free computation: only a routine that evaluates AvAv is needed. The entries of AA 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:

rkrec≠b−Axk.r_k^{\mathrm{rec}}\ne b-Ax_k.

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

∥b−Axk∥2≤atol+rtol ∥b∥2,\|b-Ax_k\|_2 \le \mathrm{atol}+\mathrm{rtol}\,\|b\|_2,

where the two tolerances specify absolute and relative residual thresholds.

A small residual does not necessarily imply a comparably small forward error. For b≠0b\ne0,

∥x∗−xk∥2∥x∗∥2≤κ2(A)∥b−Axk∥2∥b∥2.\frac{\|x_*-x_k\|_2}{\|x_*\|_2} \le \kappa_2(A) \frac{\|b-Ax_k\|_2}{\|b\|_2}.

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 ATAx=ATbA^{\mathsf T}Ax=A^{\mathsf T}b when AA has full column rank, but the normal matrix has κ2(ATA)=κ2(A)2\kappa_2(A^{\mathsf T}A)=\kappa_2(A)^2. 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

pk+1=−gk+1+βkpk,gk=∇f(xk),p_{k+1}=-g_{k+1}+\beta_kp_k, \qquad g_k=\nabla f(x_k),

and select step lengths through a line search.

Different formulas for βk\beta_k 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.