Conjugate gradient method Created 2026-09-24 Updated 2026-11-05
The conjugate gradient method solves for a real symmetric positive-definite matrix by minimizing over expanding affine Krylov subspaces. Its successive nonzero search directions are A-conjugate directions, so a new line minimization preserves the optimality already obtained along earlier directions.
Start with and stop if it is zero; otherwise put . The recurrence isStop when the new residual is zero, before attempting another division. Each step uses a matrix-vector product, a few inner products and vector updates; a sparse or implicit linear operator can therefore be used without forming its inverse.[ref]
https://netlib.org/templates/templates.html. Templates for the Solution of Linear Systems, §2.3.1, conjugate gradients and symmetric positive-definite assumptions
For , and , the first step has , and . The next conjugate direction is and its step size is , giving the exact solution . Finite termination of the conjugate gradient method is an exact-arithmetic statement; floating-point loss of orthogonality changes the practical stopping analysis.
Past exam of the mathematics course of the University of Cambridge 2023 ii Paper 3 40C a Solution Created 2026-09-24 Updated 2026-10-31
Forthe gradient is . The steepest descent method with exact line search for a positive-definite quadratic therefore uses
For and , the minimizer is . PutStarting from , direct substitution gives and, inductively,The Euclidean norm is unchanged by the alternating sign, soFor a positive-definite matrix, the spectral condition number of a positive-definite matrix isHere , and hence
The conjugate gradient method starts with and updatesBy finite termination of the conjugate gradient method, it reaches the exact solution in at most the number of distinct eigenvalues. This matrix has two, so at mostare required in exact arithmetic.
Past exam of the numerical linear algebra course of the University of Oxford 2025 3 b iv Solution 2026-10-25
Under the permitted singular value bounds, givesFor the symmetric positive-definite matrix in part (iii), its eigenvalues are the squared singular values of , soApply the supplied conjugate gradient convergence bound to . For and nonzero , the function increases with , givingThus the error in this weighted norm contracts at a guaranteed exponential factor of at most per iteration, up to the prefactor . Here . The Pythagorean identity in part (iii) also identifies with the excess squared linear least-squares problem objective, which consequently decreases by a bound proportional to . For the Euclidean norm, the same eigenvalue bounds give .
For relative accuracy in the -weighted norm, it is sufficient to takeCompute once in operations. Each iteration applies with two dense matrix multiplications and uses further arithmetic operations; when this costs . Hence the total cost isUsing finite termination of the conjugate gradient method in exact arithmetic refines this to . Explicitly constructing first would add setup work and is unnecessary. These accuracy estimates concern relative error; an absolute tolerance replaces by when . If , the initial guess already solves the problem.
As in part 2(b)(v), the Gaussian assumption alone does not make the printed singular value interval a certainty. For example, the event that every entry of has absolute value below a sufficiently small positive number has positive probability and forces , contradicting the asserted lower endpoint. The displayed rate is therefore conditional on the singular-value bounds authorized by the paper. The cost and convergence derivation are exact under that condition; an unconditional probabilistic statement would need an additional failure-probability estimate.