Conjugate Gradient Method

A Krylov-subspace solver for symmetric positive-definite linear systems that builds mutually A-conjugate directions while minimizing the associated quadratic.

Version

v3 · 2026-09-19 · History

Domain-specific #

1540

Domain group

Formal Sciences

Origin domain

Mathematics

Aliases

Conjugate gradient, CG method

Core Idea

The conjugate gradient method (CG) solves a linear system \(Ax=b\) when \(A\) is symmetric (Hermitian in the complex formulation) and positive definite. Equivalently, it minimizes the strictly convex quadratic

\[ \phi(x)=\tfrac12x^TAx-b^Tx, \]

whose gradient is \(Ax-b\). Starting from \(x_0\), CG builds iterates in expanding Krylov subspaces and chooses search directions that are mutually \(A\)-conjugate: \(p_i^TAp_j=0\) for \(i\ne j\).

The identity is the coordinated recurrence linking the residual, step length, and conjugate direction. In exact arithmetic it reaches the solution in at most \(n\) steps for an \(n\)-dimensional system, and often fewer according to the relevant minimal polynomial/eigenvalue structure.

How would you explain it like I'm…

Never-Undo Steps to the Bottom

Imagine you're in a big smooth bowl, trying to walk to the very bottom. With a clever rule for choosing each direction, every new step keeps all the good progress from your earlier steps instead of undoing it. That clever way of walking downhill is the Conjugate Gradient Method.

Downhill Without Undoing Steps

The conjugate gradient method is a way computers solve big puzzles made of many equations at once, but only a special kind where the equations have a nice balanced, bowl-like shape. Solving the equations is the same as finding the lowest point of that bowl. The method takes steps toward the bottom, and each new direction is picked so it doesn't mess up what the earlier steps already fixed. In perfect math with no rounding, it gets the exact answer in at most as many steps as there are unknowns, often fewer. Real computers round numbers, so in practice it keeps going until the answer is close enough.

Conjugate-Direction Equation Solver

The conjugate gradient method (CG) solves Ax = b when A is symmetric and positive definite. That is equivalent to minimizing phi(x) = (1/2) x^T A x - b^T x, a bowl-shaped function whose gradient is Ax - b, so the bottom of the bowl is where Ax = b. Starting from a guess, CG steps along search directions that are A-conjugate: p_i^T A p_j = 0 for different directions, a weighted form of perpendicularity that ensures a new step doesn't spoil the minimization already done along earlier directions. Each step updates the residual (how far Ax is from b), picks a step length, and builds the next conjugate direction from these. In exact arithmetic it finishes in at most n steps for n unknowns, and often fewer depending on the eigenvalues of A. With rounding error those guarantees weaken, so it is run as an iterative method and stopped when the residual is small enough.

 

The conjugate gradient method solves Ax = b for A symmetric (Hermitian in the complex case) and positive definite, equivalently minimizing the strictly convex quadratic phi(x) = (1/2) x^T A x - b^T x, whose gradient is Ax - b. From an initial x_0, it generates iterates in the expanding Krylov subspaces spanned by the initial residual and its images under powers of A. Its search directions are mutually A-conjugate, p_i^T A p_j = 0 for i != j, so minimizing along a new direction preserves optimality along all previous ones. The method's identity is the coupled recurrence linking the residual, the step length, and the next conjugate direction, each computed from the previous ones. In exact arithmetic it terminates in at most n steps for an n-dimensional system, and often fewer, as governed by the minimal polynomial and eigenvalue structure of A. In floating-point arithmetic, conjugacy and orthogonality degrade, so CG is used as an iterative method with a residual- or error-based stopping criterion; finite termination is a theoretical reference property, not an implementation guarantee.

Scope of Application

CG is central in numerical linear algebra, scientific computing, optimization, finite-element and finite-difference PDE discretizations, graph Laplacian problems after suitable handling of nullspaces, and inner solves in larger algorithms. Its economy is especially valuable for large sparse matrices because each iteration primarily needs a matrix-vector product, vector operations, and a small number of inner products.

The method also extends naturally to self-adjoint positive-definite operators in Hilbert-space formulations, subject to analytic and discretization conditions. Its usefulness depends on conditioning and spectrum, not sparsity alone. Dense SPD systems can use CG, while a sparse but nonsymmetric or indefinite system violates the core assumptions.

Clarity

The abstraction unifies a solver view and an optimization view. The equation residual \(r_k=b-Ax_k\) is the negative gradient of \(\phi\); solving the system and minimizing the quadratic are the same task under SPD assumptions. The \(A\)-inner product explains “conjugate”: directions need not be Euclidean-orthogonal, but their cross terms vanish in the quadratic geometry.

Manages Complexity

CG compresses an expanding optimal subspace method into a three-term recurrence. It avoids storing every prior direction because exact conjugacy makes old correction components remain settled. This gives low memory and exploits sparse matrix-vector products, while retaining a polynomial/Krylov interpretation of convergence.

The compression deliberately leaves the spectrum, conditioning, rounding error, preconditioner, and stopping test explicit. A clustered spectrum can yield rapid convergence; a large condition number can slow it.

Abstract Reasoning

With \(r_0=b-Ax_0\) and \(p_0=r_0\), the standard unpreconditioned recurrence is

\[ \alpha_k=\frac{r_k^Tr_k}{p_k^TAp_k},\quad x_{k+1}=x_k+\alpha_kp_k, \]

\[ r_{k+1}=r_k-\alpha_kAp_k,\quad \beta_{k+1}=\frac{r_{k+1}^Tr_{k+1}}{r_k^Tr_k},\quad p_{k+1}=r_{k+1}+\beta_{k+1}p_k. \]

Under SPD/exact-arithmetic assumptions, \(x_k\) minimizes \(\phi\) over \(x_0+\mathcal K_k(A,r_0)\); residuals are mutually orthogonal and directions mutually \(A\)-conjugate.

Knowledge Transfer

Literal transfer occurs across SPD systems when operator application, inner product, residual, and conjugacy are preserved. A finite-element stiffness solve and a covariance-like quadratic optimization can share the same CG core after mapping their matrices and right-hand sides. Preconditioning knowledge transfers by matching which spectral modes are difficult rather than copying a preconditioner blindly.

Transfer to nonlinear conjugate gradient is partial and explicitly variant-level. Transfer to GMRES, Lanczos eigenvalue methods, and LOBPCG occurs through Krylov concepts, but their objectives and invariants differ.

Relationships to Other Abstractions

Current abstraction Conjugate Gradient Method Domain-specific

Parents (1) — outgoing typed relations

• Conjugate Gradient Method is a kind of Optimization Prime

  CG directly instantiates Optimization because each iterate minimizes a convex quadratic over an expanding affine Krylov subspace.

Hierarchy path (1) — routes to 1 parentless root

• Conjugate Gradient Method → is a kind of Optimization

Neighborhood in Abstraction Space

Conjugate Gradient Method sits in a sparse region of the domain-specific corpus (78^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (2769 abstractions)

Nearest neighbors

• Quadratic Space — 0.83
• Carlyle Circle — 0.82
• Siegel Zero — 0.82
• Dispersion Function — 0.82
• Jacobi Method — 0.82

Computed from structural-signature embeddings · 2026-10-25