Past exam of the mathematics course of the University of Cambridge / 2001 / ia / Paper 1 / 11D (Analysis I)

By continuity of $g^{\prime \prime }$ at $\alpha$, for any $ϵ>0$ choose $\delta (ϵ)>0$ such that $|g^{\prime \prime }(s)|\le |g^{\prime \prime }(\alpha )|+ϵ=:M$ whenever $|s-\alpha |<\delta (ϵ)$. Twice using the fundamental theorem of calculus gives the remainder asThe inner difference is ${\int }_{\alpha }^s{g}^{\prime \prime }(r)dr$ and has modulus at most $M|s-\alpha |$. Integrating this bound over the interval between $\alpha$ and $t$ proves, for either sign of $t-\alpha$,This is the local quadratic Taylor remainder estimate. The given $ϵ$ may enter the bound on the second derivative; no stronger differentiability assumption is needed.

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.