An iterative algorithm for solving large symmetric positive-definite linear systems Ax = b and for minimizing quadratic functions by generating A-conjugate search directions that converge to the exact solution in at most n steps in exact arithmetic.

Principle

Construct search directions that are conjugate with respect to the system matrix A so that corrections along successive directions remove orthogonal components of the error; use short recurrences to update the solution, residual, and direction without storing a full Krylov basis.

Demonstration

Solve a discretized Poisson equation on a grid: represent the Laplace operator as a sparse SPD matrix A and apply conjugate gradient to iteratively reduce the energy norm of the error until tolerances for residual or energy are met, using preconditioning to accelerate convergence.

Misapplication

Applying unmodified conjugate gradient to nonsymmetric or indefinite matrices (without adapting to methods like GMRES or MINRES) or using poor preconditioners, which can cause stagnation, breakdown, or slow convergence.

Consequence

For large sparse SPD problems, CG gives memory-efficient iterative solves with rapid convergence when eigenvalues are clustered or when good preconditioners are available; exact arithmetic yields finite-step termination and practical arithmetic yields fast approximation.

Reversal

Direct methods such as Cholesky factorization compute exact solves via matrix decomposition and pivoting, avoiding iteration but at higher memory and factorization cost for very large sparse systems compared to CG.

Boundary

Intended for symmetric positive-definite systems or equivalent quadratic minimization; it excludes nonsymmetric, highly indefinite, or severely ill-conditioned problems unless adapted with preconditioning, reorthogonalization, or switching to more general Krylov methods.

Semantic Tension

Tension exists between CG and other Krylov methods (GMRES, BiCGStab) regarding symmetry and storage: CG is optimal for SPD systems with minimal storage and short recurrences, whereas other methods accept nonsymmetry at the cost of extra storage or complexity.

Synthesis

Conjugate gradient transforms the linear solve into a sequence of one-dimensional minimizations along A-conjugate directions, achieving efficient memory usage and fast convergence for SPD sparse systems; its practical performance depends strongly on spectrum properties and preconditioning.