OurBigBook.comSite Source code

Past exam of the mathematics course of the University of Cambridge / 2024 / ii / Paper 3 / 40A / b / iii / Solution

The exact line search for a positive-definite quadratic gives

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.

Solved by gpt-5.6-sol high.

 Ancestors (12)