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

Use the standard spacing convention for machine epsilon: the next representable floating-point number above $1$ is $1+2^{-40}$. In a normalized binary representation this corresponds to $41$ significant binary digits, including the leading digit. The spacing throughout $[1,2)$ is therefore $2^{-40}$.

With rounding to nearest, the associated unit roundoff is half that spacing, $u=2^{-41}$; for a normal result the relative round-off error is bounded by $u$. Some texts instead call $u$ machine epsilon. Here $2^{-40}$ denotes the spacing scale, and the iteration counts below use that convention. It describes representation precision, not a guarantee that an arbitrarily evaluated function has a relative error this small.

The second-order remainder form of Taylor's theorem gives, for a point ${\xi }_x$ between $0$ and $x$,For $x\ne 0$, the given curvature bounds implyIn particular $f(1)<-1/2<0$ and $f(2)\ge 5>0$. Differentiability implies continuity, so the intermediate value theorem gives a root in $(1,2)$.

The mean value theorem applied to $f^{\prime }$ gives $f^{\prime }(x)=3+x{f}^{\prime \prime }({\eta }_x)\ge 3+2x>0$ for $x\in (1,2)$. Thus $f$ is strictly increasing there, and it cannot have two roots. There is exactly one root in $(1,2)$.

At a root of size between $1$ and $2$, the spacing of floating-point numbers is $ϵ=2^{-40}$. With ordinary stable function evaluations, a sensible generic absolute position tolerance has scale $2^{-40}\approx 9.09\times 10^{-13}$; sub-spacing progress cannot generally be represented. This is a resolution estimate, not a lower bound excluding an accidentally exactly representable root.

Define one bisection method step as replacing the current bracket by the half retaining the sign change. Starting from $[1,2]$, the width after $N$ such updates is $2^{-N}$. ThereforeThe midpoint of a bracket has an exact-arithmetic error bound of half its width. If tolerance is defined instead as that midpoint error bound, $39$ updates suffice to make it at most $2^{-40}$. Stating the convention avoids an off-by-one difference; once the endpoints are adjacent floating-point numbers, their exact midpoint need not itself be representable.

Apply the mean value theorem, the first-order case of Taylor's theorem, to $f^{\prime }$ between $0$ and $x>1$. It yieldsAlso $f(3/2)\ge -5+9/2+9/4=7/4>0$, so the initial point is to the right of the root $x^{\ast }$. For an increasing strictly convex function, its tangent at a point to the right of a root meets the axis between that root and the point. Hence the exact Newton root-finding iteration remains in $[x^{\ast },3/2]$ and decreases towards $x^{\ast }$.

On every relevant interval, $|f^{\prime \prime }|<3$ and $f^{\prime }>5$, so the stated quadratic convergence bound gives, with $e_n=|x_n-x^{\ast }|$,Iterating the bound givesThus four Newton corrections suffice to reduce the exact-iteration error bound below the floating-point spacing scale. The quadratic convergence doubles the approximate number of correct digits at each late step. Beyond this point further corrections cannot reliably improve a generic floating-point answer. This is a bound on useful accuracy under the usual stable-evaluation model, not a claim that the data specify the exact iteration at which every implementation must stagnate.

For negative $x$, the mean value theorem gives $f^{\prime }(x)=3+x{f}^{\prime \prime }({\xi }_x)$. In particular,Since $f^{\prime }$ is continuous and strictly increasing, it vanishes at exactly one point $x_m\in (-2,-1)$. The positive second derivative makes $f$ a strictly convex function on the entire real line. Its derivative changes from negative to positive at $x_m$, so $x_m$ is the unique global minimum. One may also use $f(x)\ge x^2+3x-5\to \infty$ to verify coercivity.

In the endpoint-bracketing form of golden-section search, begin with $[-2,-1]$, a width-one interval known to contain this unique minimum, and place the two standard interior probes. The attainable position accuracy is different from that for a simple root. Around $x_m$, Taylor's theorem givesHere the minimum value is nonzero and of order one: the lower quadratic bound gives $f(x_m)\ge -29/4$, while $f(x_m)\le f(-1)<-13/2$. Ordinary relative round-off error in these function values therefore hides changes of order $ϵ$, once $h^2$ has that size. The function-value resolution near a nondegenerate minimum is consequently of orderEach golden-section search contraction multiplies the bracket width by $\rho =(\sqrt{5}-1)/2$. Using $2^{-20}$ as the nominal target width givesUnknown evaluation-error constants can change the actual stopping point; $29$ is the standard scale-based count. Requiring $2^{-40}$ position accuracy from these function-value comparisons would disregard the quadratic flatness of the minimum. The same precision effect is documented for one-dimensional numerical minimization.^[ref]