conjugate gradient method

The conjugate gradient method, CG for short, is the Krylov solver for symmetric positive-definite systems Ax = b. There is a beautiful reinterpretation behind it: solving Ax = b is equivalent to minimizing the quadratic energy phi(x) = (1/2) x^T A x - b^T x, whose unique minimum is the solution. CG walks downhill on this bowl-shaped surface, but cleverly so.

Naive steepest descent zig-zags badly in a stretched bowl. CG fixes this by choosing search directions that are A-conjugate: directions p_i, p_j with p_i^T A p_j = 0 for i not equal to j. Conjugate directions never undo each other's progress. The result is that, in exact arithmetic, CG reaches the exact solution of an n-by-n system in at most n steps — it is technically a direct method, though we always use it iteratively.

What makes CG practical is its astonishing economy: it needs only one matrix-vector product, a couple of inner products, and a handful of vector updates per step, storing just a few vectors regardless of n. It builds the same Krylov subspace as everyone else but, thanks to symmetry, finds the energy-minimizing point with a short three-term recurrence rather than storing the whole basis.

Convergence is tied to the condition number kappa = lambda_max / lambda_min. The classic bound says the A-norm error after k steps shrinks like ((sqrt(kappa) - 1) / (sqrt(kappa) + 1))^k. A well-conditioned or eigenvalue-clustered matrix converges in a handful of steps; an ill-conditioned one crawls — which is why CG is almost always run with a preconditioner.