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

Let $h=(b-a)/n$, $x_j=a+jh$, and $m_j=a+(j+\frac{1}{2})h$. The composite midpoint rule and composite trapezoidal rule areFor composite Simpson's rule with $2n$ strips, the spacing is $h/2$. Its odd-indexed nodes are the $m_j$ and its even interior nodes are the $x_j$. ConsequentlyThis is an identity between the quadrature rules, not an approximation involving an omitted quadrature error.

Four differentiations giveFor $0<x<1$, the fifth derivative is negative, so the fourth derivative is strictly decreasing. Since $f^{(4)}(1)=0$, strict decrease towards that endpoint implies $f^{(4)}(x)>0$ for $x<1$. On the closed interval, $0\le f^{(4)}(x)\le 1$, with the maximum at $0$ and minimum at $1$.

Take $n$ to be a positive even integer, as required by composite Simpson's rule. There are $n/2$ two-strip panels, each of width $2/n$. Applying the supplied panel bound with the global fourth-derivative minimum $0$ and maximum $1$, and summing, givesHere $E_n$ is the nonnegative absolute error. In this example Simpson's rule overestimates the integral, so $E_n=S_n-I$. Each panel has that same sign because its fourth derivative is nonnegative; cancellation is not being assumed.^[ref]

On the panel $[2j/n,2(j+1)/n]$, the maximum fourth derivative is at the left endpoint because it is decreasing. ThusThe geometric series and the sum of consecutive integers giveSubstitution provesFor $n>2$, at least one panel's maximum is smaller than the global maximum $1$, so this bound is strictly tighter than the global bound. For $n=2$, the two bounds coincide.

The global bound requiresSince the strip count must be even, the smallest count certified by this bound is $n=88$.

For the tighter bound, use the bisection method on the continuous extension $B(x)-10^{-10}$ for $x\ge 2$. The initial root bracket $[2,88]$ is valid: $B(2)=1/2880>10^{-10}$, while $B(88)$ is below the global bound and hence below $10^{-10}$. To identify the smallest admissible even count, the monotonicity of $B$ can also be justified.

Put $h=2/x$ andFor $h>0$, differentiation showsThe numerator is nonnegative because $e^h-e^{-h}\ge 2h$: its difference from $2h$ starts at zero and has nonnegative derivative $e^h+e^{-h}-2$, by the arithmetic-geometric mean inequality. Thus $C^{\prime }(h)\ge 1/2$, and $C(0^{+})=e/2-1>0$. Therefore $h^{4}C(h)$ increases with $h$, so $B(x)$ is strictly decreasing with $x$. Bisection locates its unique threshold crossing; then check the neighboring even integers, retaining the strict error inequality.

For example, $B(66)\approx 1.09626\times 10^{-10}$ and $B(68)\approx 9.71694\times 10^{-11}$, so the tighter bound certifies $68$ strips. These are evaluations of the bound, not an assumption that it equals the actual quadrature error.

No: Monte Carlo integration is poorly suited to this smooth one-dimensional problem at such a tight tolerance. A sample-average Monte Carlo estimator has a standard error proportional to $N^{-1/2}$, whereas the deterministic composite Simpson's rule bound decreases as $n^{-4}$ here and already certifies the target with tens of strips. Random sampling would require vastly more function evaluations and supplies a probabilistic error statement rather than the displayed deterministic guarantee.