= Solution
The <exact line search for a positive-definite quadratic> gives
$$
f(x_{k+1})-f(x_k)
=-\frac12\frac{(r_k^Tr_k)^2}{r_k^TAr_k}.
$$
Using
$$
f(x_k)-f(x^*)=\frac12r_k^TA^{-1}r_k
$$
produces the stated ratio formula. If $l$ and $L$ are the extreme <eigenvalues>,
$$
r_k^TAr_k\leq Lr_k^Tr_k,
\qquad
r_k^TA^{-1}r_k\leq l^{-1}r_k^Tr_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.
Back to article page
