 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2024/ii/paper-3/40a/b/iii/solution

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

f (x_{k + 1}) - f (x_{k}) = - \frac{1}{2} \frac{( r _{k}^{T} r _{k} ) ^{2}}{r _{k}^{T} A r _{k}} .

Using

f (x_{k}) - f (x^{*}) = \frac{1}{2} r_{k}^{T} A^{- 1} r_{k}

produces the stated ratio formula. If

l

and

L

are the extreme eigenvalues,

r_{k}^{T} A r_{k} \leq L r_{k}^{T} r_{k}, r_{k}^{T} A^{- 1} r_{k} \leq l^{- 1} r_{k}^{T} r_{k} .

Hence the fraction in the ratio is at least

l / L

, and iteration yields

f (x_{k}) - f (x^{*}) \leq (1 - l / L)^{k} {f (x_{0}) - f (x^{*})} .

When

n = 1

l = L

, so the right side is zero after one iteration: exact line search reaches the solution in a single step.

 New to topics? Read the docs here!