Conjugate gradients and preconditioning

Let A be real symmetric positive definite. The quadratic q(x)=xᵀAx/2−bᵀx has gradient Ax−b and a unique minimizer xstar satisfying Axstar=b. Its excess value is one half the squared A-norm of the error, where the A-norm of e is the square root of eᵀAe. Conjugate gradients chooses the kth iterate from the initial guess plus its kth residual Krylov space to minimize that energy error in exact arithmetic. It does not generally minimize the ordinary Euclidean residual norm at every step.

The search directions are A-conjugate: distinct directions have zero cross product pᵢᵀApⱼ. Residuals are mutually Euclidean-orthogonal under exact arithmetic until termination. These are different orthogonality statements and explain the short update formulas. Positive definiteness makes pᵀAp positive for nonzero p, so the step denominator has the required sign. Symmetry alone is insufficient; an indefinite matrix can break that argument. Specialized algorithms exist for other structures, but the standard CG guarantee should not be transferred to them without modification.

In exact arithmetic, the error admits a polynomial representation whose polynomial equals one at zero. Bounding that polynomial over the positive eigenvalue interval gives the familiar condition-number convergence estimate. The square root of κ₂ appears, making the bound stronger than the corresponding simple fixed-step gradient iteration estimate. The factor depends only on the extreme eigenvalues, so it ignores clustering and the starting error's spectral components. A system can converge much faster than this interval-based worst-case statement predicts.

CG terminates in at most n steps in exact arithmetic for an n-dimensional positive definite problem, and potentially earlier when the effective spectral support is smaller. Finite precision destroys exact orthogonality and can lead to more than n useful steps. Recursively updated residuals can drift from explicitly recomputed residuals, so a trustworthy implementation checks a scaled true residual when needed. No single raw tolerance suits every unit system or right-hand-side magnitude. An energy-error bound, a residual threshold, and a task-level accuracy requirement are related but distinct stopping criteria.

For a symmetric positive definite preconditioner M, the conceptual symmetric transformed matrix is M to the negative one-half times A times M to the negative one-half. It remains positive definite. Preconditioned CG can implement the equivalent process using solves with M, without explicitly forming a square root or an inverse. The relevant condition number for the standard bound is that of the symmetric transformed matrix. The generally nonsymmetric-looking product M inverse A should not be handed to ordinary Euclidean CG without accounting for the corresponding metric.

A good preconditioner reduces iteration cost overall, not merely the number of iterations. Choosing M=A makes the transformed matrix the identity, but applying M inverse already solves the original problem and may defeat the purpose. Diagonal scaling is cheap and can remove simple scale disparity, while incomplete factorizations or multilevel methods may capture more structure at greater setup cost. Variable or nonsymmetric preconditioners require appropriate algorithm variants. Report setup, application, communication, and convergence together when deciding whether preconditioning actually improves a solve.