Past exam of the mathematics course of the University of Cambridge / 2001 / ia / Paper 1 / 11D / ii / Solution

The intermediate value theorem gives a root $r\in (a,b)$, unique because $f^{\prime }>0$ makes $f$ strictly increasing. We show that Newton root-finding iteration, started at $b$, always stays to the right of $r$. If $x>r$, the mean value theorem gives $f(x)=f^{\prime }(\xi )(x-r)$ for some $\xi \in (r,x)$. Since $f^{\prime \prime }>0$, $f^{\prime }$ is strictly increasing, so $0<f^{\prime }(\xi )<f^{\prime }(x)$. It follows thatInduction gives $r<x_{n+1}<x_n\le b$, so the bounded monotone sequence theorem supplies a limit $\alpha \ge r$. The continuous positive $f^{\prime }$ is bounded away from zero on $[a,b]$, making $F$ continuous. Passing to the limit in $x_{n+1}=F(x_n)$ gives $\alpha =F(\alpha )$ and hence $f(\alpha )=0$. Uniqueness implies $\boxed{\alpha =r}$.

For the rate, apply the Taylor theorem with Lagrange remainder to $f$ between $r$ and $x_n$:With $e_n=x_n-r>0$, rearrangement givesThus the monotone Newton convergence for a strictly convex function has quadratic convergence. More concretely, if $K={\max }_{[a,b]}{f}^{\prime \prime }/[2{\min }_{[a,b]}{f}^{\prime }]$, then $e_{n+1}\le K{e}_n^2$. Once $K{e}_N<1$, induction gives $e_{N+j}\le K^{-1}(K{e}_N{)}^{2^j}$, exhibiting the repeated squaring of small errors.