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

v2 · 2026-08-30 · History

Domain-specific #

1540

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\).^[1]

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.^[2] In floating-point arithmetic it is used as an iterative method stopped by a residual/error criterion; finite termination and exact orthogonality are theoretical reference properties, not implementation guarantees.

Structural Signature

Recognition roles:

• SPD operator: \(A=A^T\) and \(v^TAv>0\) for all nonzero \(v\).
• Initial iterate: \(x_0\) sets the affine Krylov search space.
• Residual: \(r_k=b-Ax_k\), the negative quadratic gradient.
• Conjugate direction: \(p_k\) is constructed to be \(A\)-orthogonal to preceding directions in exact arithmetic.
• Exact line step: \(\alpha_k\) minimizes the quadratic along \(p_k\).
• Short recurrence: \(r_{k+1}\) and \(p_{k+1}\) use current vectors without storing the full Krylov basis.
• Stopping/preconditioning discipline: practical use monitors convergence and may transform the system with an SPD preconditioner.

A recognition test asks whether the method targets an SPD linear system/quadratic and uses a residual-driven short recurrence that preserves \(A\)-conjugacy in exact arithmetic. A generic gradient optimizer, nonsymmetric Krylov solver, or nonlinear conjugate-gradient heuristic does not pass unchanged.

What It Is Not

CG is not steepest descent. Both use residual/gradient information, but steepest descent repeatedly follows the current gradient and can zigzag, whereas CG constructs directions conjugate under the \(A\)-inner product. It is not the Jacobi method, which is a stationary splitting iteration. It is not GMRES, which handles general nonsymmetric matrices and explicitly minimizes residual norm over a stored/orthogonalized Krylov basis.

It is not automatically applicable to symmetric indefinite systems; MINRES or other methods address that setting. Nonlinear conjugate gradient borrows recurrence ideas for nonlinear objectives but loses the exact linear-quadratic conjugacy and finite-step theory. LOBPCG is an eigensolver, not a synonym for solving \(Ax=b\). Finally, preconditioned CG is a governed variant whose preconditioner must preserve an appropriate SPD formulation.

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.^[2]

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. Preconditioning is often decisive: a practical preconditioner approximates difficult spectral structure while remaining inexpensive to apply.^[2]

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.

Clarity also requires separating residual from error. If \(e_k=x_*-x_k\), then \(r_k=Ae_k\). A small residual implies a small error only after conditioning/norm relationships are considered. A method log showing monotone residual decline may still be misleading when the system is badly conditioned or the stopping tolerance is poorly scaled.

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.^[3]

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. Finite precision erodes residual orthogonality and direction conjugacy, so recomputation or robust stopping logic may be needed. The abstraction manages algebraic complexity but does not make numerical diagnostics optional.

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.^[3]

The classical error bound in the \(A\)-norm is

\[ \|e_k\|_A\le 2\left(\frac{\sqrt\kappa-1}{\sqrt\kappa+1}\right)^k\|e_0\|_A, \]

where \(\kappa=\lambda_{\max}/\lambda_{\min}\) for SPD \(A\).^[2] It is a worst-case bound; eigenvalue clustering can produce better behavior.

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. Calling any repeated correction “conjugate gradient” is metaphorical unless the SPD quadratic and recurrence are present. The parent Optimization transfers broadly; the named method remains numerical-linear-algebra specific.

Examples

Two-dimensional solve. Let

\[ A=\begin{pmatrix}4&1\\1&3\end{pmatrix},\quad b=\begin{pmatrix}1\\2\end{pmatrix},\quad x_0=0. \]

Then \(r_0=p_0=b\), \(r_0^Tr_0=5\), and \(p_0^TAp_0=20\), so \(\alpha_0=1/4\). Thus \(x_1=(1/4,1/2)^T\), \(r_1=(-1/2,1/4)^T\), and \(\beta_1=(5/16)/5=1/16\). The next direction is \(p_1=(-7/16,3/8)^T\). A second exact-arithmetic step reaches \(x_*=(1/11,7/11)^T\), consistent with the at-most-two-step result.

Sparse PDE system. A conforming discretization of a coercive elliptic problem often produces an SPD stiffness matrix. CG can apply that matrix without forming a dense factorization. A suitable SPD preconditioner reduces effective conditioning; the PDE origin does not itself guarantee any chosen preconditioner works.

Negative case. For \(A=\begin{pmatrix}0&1\\1&0\end{pmatrix}\), symmetry holds but positive definiteness fails: with \(v=(1,-1)^T\), one obtains \(v^TAv=-2<0\). Denominators can lose positivity, so standard CG’s guarantees do not apply.

Structural Tensions

• Finite-step theory versus floating-point practice. Exact arithmetic terminates in finite dimension, while rounding loses invariants. Diagnostic: monitor true residuals and compare recurrence residuals periodically.
• Cheap iterations versus conditioning. Sparse matrix-vector products are inexpensive, but many steps may be needed. Diagnostic: estimate spectral conditioning and measure preconditioned iteration counts.
• Residual tolerance versus solution error. A small residual can coexist with larger error under poor conditioning. Diagnostic: scale tolerances and relate residual norm to an error estimate.
• Autonomy versus reduction. Krylov Subspace + Gradient + Orthogonality are ingredients, but only CG fixes SPD quadratic minimization and its short conjugacy recurrence. Diagnostic: verify the complete recurrence and invariants.

Structural–Framed Character

CG is strongly structural: its identity survives coordinate changes that preserve the SPD inner-product geometry and equivalent operator formulations. Its practical framing comes from finite precision, sparse storage, communication cost, preconditioner engineering, and stopping policy. “Fast” is workload-dependent and not part of the definition.

The method has no institutional or moral content. Numerical conventions—left versus split preconditioning, complex inner products, residual replacement—must be stated when they affect formulas. The mathematical core is stable while implementation judgment remains contextual.

Structural Core vs. Domain Accent

The portable skeleton is iteratively correct a state using mutually noninterfering directions chosen from accumulated information. The indispensable accent is an SPD linear operator, quadratic objective, Krylov subspace, inner products, residual polynomials, and floating-point numerical analysis.

Without that accent, the name becomes generic iterative improvement. CG therefore does not clear the prime bar, despite applications in many sciences. It is an autonomous domain method with exact recognition tests and failure modes.

Instantiates / Related Primes

CG directly instantiates Optimization because each iterate minimizes a convex quadratic over an expanding affine Krylov subspace. It also realizes refinement and iteration, but those broader descriptions are not needed as graph parents. The accepted LOBPCG and Jacobi Method nodes are relatives/siblings, not genera.

The minimal proposal uses prime:optimization. It captures the exact quadratic minimization interpretation while avoiding over-parenting with generic numerical operations.

Relationships to Other Abstractions

Current abstraction Conjugate Gradient Method Domain-specific

Parents (1) — more general patterns this builds on

• 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 → 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 — Applied Linear & Special Functions (18 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-09-08

Not to Be Confused With

• Steepest descent: repeated gradient directions, not conjugate directions.
• Jacobi method: stationary matrix splitting rather than Krylov minimization.
• GMRES: nonsymmetric-capable residual minimization with a different recurrence/storage profile.
• MINRES: designed for symmetric indefinite as well as definite systems.
• Nonlinear conjugate gradient: a nonlinear-optimization family with altered coefficients and guarantees.
• LOBPCG: a block preconditioned eigensolver.
• Conjugate residual method: related but uses different orthogonality/minimization properties.

References

[1] Magnus R. Hestenes and Eduard Stiefel, “Methods of Conjugate Gradients for Solving Linear Systems,” Journal of Research of the National Bureau of Standards 49 (1952), 409–436, doi:10.6028/jres.049.044. registry ↩

[2] Yousef Saad, Iterative Methods for Sparse Linear Systems, 2^nd ed. (SIAM, 2003), doi:10.1137/1.9780898718003. registry ↩a ↩b ↩c ↩d

[3] Jonathan Richard Shewchuk, “An Introduction to the Conjugate Gradient Method Without the Agonizing Pain,” technical report, Carnegie Mellon University (1994), official PDF. registry ↩a ↩b