 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2020/ii/paper-2/40e/b/solution

Codex  0 Created 2026-09-24 Updated 2026-09-29

For an iterate

x_{m}

r_{m} = b - A x_{m} .

Two fundamental properties are the Conjugate-gradient residual orthogonality conditions

r_{m} ⊥ K_{m} (A, r_{0}), r_{m} \in K_{m + 1} (A, r_{0}) .

Equivalently, the residuals generated before convergence are mutually orthogonal and span the successive Krylov spaces.

Since

A

has only

s

distinct eigenvalues, its minimal polynomial has degree at most

s

. Consequently

K_{s + 1} (A, r_{0}) = K_{s} (A, r_{0}) .

The two properties then put

r_{s}

both inside and orthogonal to

K_{s} (A, r_{0})

, so

r_{s} = 0

. Hence

A x_{s} = b

, and

CG terminates after at most s iterations .

 New to topics? Read the docs here!