Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Discrete mathematics, continuous mathematics, and probability resit / 5

The secant method starts from two approximations $x_0,x_1$. Replace the function near its zero of a function by the secant line through $(x_{k-1},f(x_{k-1}))$ and $(x_k,f(x_k))$; the zero of that line is the next approximation:Stop immediately if $f(x_k)=0$; otherwise the denominator must be nonzero. Each further step needs one new function evaluation and no derivative. There is no automatic bracketing or global convergence guarantee.^[ref]

Use $f(x)=x{\log }_{2}x-4$. Then $f(1)=-4$, $f(2)=-2$, and the secant method givesWriting $L={\log }_{2}3$, the next step isThus the requested approximation is $x_3=2.73$ to three significant figures. All intermediate logarithms should be retained at higher precision before this final rounding.

A small difference between successive secant method iterates alone does not certify a small absolute error. Instead use a residual root error bound. On $[2,3]$,and $f(2)<0<f(3)$, so there is a unique root $r\in (2,3)$. For an iterate $x\in [2,3]$, the mean value theorem givesTherefore stop when $x\in [2,3]$ and $|x{\log }_{2}x-4|\le (1+1/\ln 2)10^{-10}$. This guarantees the desired absolute error in exact arithmetic; the evaluated residual of a root equation should include an allowance for its much smaller roundoff error. A safeguarded implementation can retain the bracket $[2,3]$ and use bisection if a proposed secant method step leaves it.

With the gap-at-one convention, machine epsilon is the difference between $1$ and the next larger representable floating-point number. The double-precision floating-point format has 53 significant binary digits, including the implicit leading digit, soA related convention uses unit roundoff, the worst relative rounding scale for round-to-nearest: $u=2^{-53}\approx 1.11\times 10^{-16}$. Stating the convention distinguishes these two common values.^[ref]

Choose equation (1), evaluated by refined composite Simpson's rule. It gives $y$ directly as a one-dimensional definite integral with fixed endpoints and a smooth integrand. It therefore avoids root finding altogether. Before evaluating, use the trigonometric identityThis equivalent integrand is nonnegative throughout $[0,\pi /2]$, avoiding cancellation between the original two terms. Equation (2) instead subtracts two potentially large exponential functions, while equation (3) would ordinarily put a numerical integration inside a root finding loop.

For even $n$, let $h=(\pi /2)/n$, $\varphi (x)=2\sin x\cos ((\pi /4)\cos x)$, and computeThen double $n$. The integrand has bounded derivatives of every fixed order on the integration interval; in the fourth-order error regime, the estimated remaining truncation error in $Y_{2n}$ is $|Y_{2n}-Y_n|/15$. The factor $15$ follows by eliminating the leading term $C{h}^4$ between the two mesh widths.^[ref]

Stop when this estimate is comparable to ${\epsilon }_{\mathrm{mach}}\max (1,|Y_{2n}|)$ and further refinement shows stagnation at the roundoff error scale. Check that the differences previously decreased consistently with fourth-order convergence; differences alone are not a rigorous error certificate if cancellation or roundoff error dominates. Compensated summation helps keep the summation error near the precision limit. Refining indefinitely after this point increases work without reliably adding meaningful digits. This answers the requested choice and termination strategy without requiring an explicit value of $y$.