Past exam of the year 1 of the computer science course of the University of Oxford / 2023 / Discrete mathematics, probability and continuous mathematics / 6

The Newton root-finding iteration isIt requires $f$ and its derivative to be defined at the current point, and requires $f^{\prime }(x)\ne 0$. A step can leave the domain, making a subsequent iteration undefined. In floating-point arithmetic, division by zero, overflow or non-finite function evaluations can also prevent a usable step. At a root where $f^{\prime }$ is zero the displayed quotient itself remains undefined unless the implementation stops before evaluating it.

Taylor's theorem at zero gives $f(x)=-1000+x+\frac{1}{2}{x}^2{f}^{\prime \prime }(\xi )$ for a point $\xi$ between zero and $x$. At $x=1000$, strict negativity of the second derivative gives $f(1000)<0$. At $x=2000$, its lower bound givesBy the intermediate value theorem there is a root strictly between these values. The given uniqueness identifies it as $1000<x^{\ast }<2000$.

The Newton root-finding iteration gives $x_1=0-(-1000)/1=1000$.

Set $h=x_{n+1}-x_n=-f(x_n)/f^{\prime }(x_n)$. By Taylor's theorem,The first two terms cancel by the definition of the Newton root-finding iteration. Thuswith $\xi$ between the consecutive iterates. In particular, a nonzero step has negative new residual under the stated strict concavity.

First control the denominator. The mean value theorem applied to $f^{\prime }$ yields, for $0<x\le 2000$,Thus $f$ is strictly increasing on $[0,2000]$ and all proposed Newton steps within that interval are defined.

Assume $0\le x_n<x^{\ast }$. Then $f(x_n)<0$ and $f^{\prime }(x_n)>0$, so $x_{n+1}>x_n$. Apply Taylor's theorem instead at the root, expanding about $x_n$:After rearranging and substituting the Newton step, the signed error satisfiesConsequently $x_n<x_{n+1}<x^{\ast }$. Starting from $x_0=0$, mathematical induction proves this for every finite $n$, establishing that the signed errors are negative and strictly increasing. Since $f^{\prime \prime }({\xi }_n)>-1/4000$ and $2f^{\prime }(x_n)>1$,Writing $E_n=-{ϵ}_n$ gives $0<E_{n+1}\le E_n^2/4000$. Since $E_0=x^{\ast }<2000$, this also implies $E_n\le 4000(E_0/4000{)}^{2^n}\to 0$, proving quadratic convergence. This is the concave Newton iteration from below.

Choose (iii), $|x_{n+1}-x_n|<2000ϵ$. Here the root has magnitude between $1000$ and $2000$. Machine epsilon measures relative precision near unity; the spacing of representable floating-point numbers near the root is therefore of order $10^3ϵ$. A step tolerance scaled to that magnitude is consistent with the attainable absolute positional accuracy. For IEEE binary64, using $ϵ=2^{-52}$, $2000ϵ\approx 4.44\times 10^{-13}$, comparable to the local spacing. A fixed numerical constant cannot promise an exact correctly rounded root, but this is the most sensible of the three proposals.

Condition (ii) asks for a step below $2ϵ$, a scale appropriate near one rather than near this root. A nonzero representable change near the root is normally much larger. The test may trigger only after exact stagnation, and rounding-induced oscillation can prevent that; it asks for unnecessarily fine absolute resolution.

Condition (i) measures a residual, not a position error. It changes if the same root problem is multiplied by a constant. Moreover, evaluating $f$ can involve cancellation among quantities of order $1000$, so an absolute residual of order $ϵ$ need not be meaningful or attainable. Here $1/2<f^{\prime }(x^{\ast })\le 1$, making residual and position errors comparable in exact arithmetic, but their requested absolute scale is still too small. A practical scale-aware stopping criterion for Newton iteration should also detect stagnation or a cycle rather than assuming exact arithmetic persists indefinitely.