GMRES solves any non-symmetric system by minimising the residual over a growing Krylov subspace, but with no guarantee on how fast that minimisation converges. Conjugate gradients (CG) is what happens when the matrix is restricted to the symmetric positive definite (SPD) case already familiar from Cholesky factorisation: the extra structure buys both a cheaper iteration (no need to store the whole growing basis) and a genuine, provable convergence-rate bound — closing the loop this unit opened in Topic 5 between the direct SPD method (Cholesky, exact in a fixed number of steps but ) and an iterative SPD method that scales to problems Cholesky cannot touch.
Learning objectives. By the end of this note you should be able to:
- state the SPD-specific minimisation problem CG solves;
- explain why the Krylov basis for CG needs no explicit orthonormalisation storage, unlike Arnoldi;
- state CG's convergence-rate bound in terms of the condition number;
- connect CG to Cholesky as the iterative-versus-direct pair for SPD systems.
In this lesson
- The SPD case: Lanczos instead of Arnoldi
- The conjugate gradients method
- Convergence rate
- Cholesky versus CG: the direct/iterative pair
Before you start
The full lesson, with worked examples and exercise solutions, is for members.
Read the full lessonNew to SelfMadeQuant.com? See membership options or browse the Linear Algebra, Optimisation and Numerical Methods syllabus.