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

Use Simpson's rule: the cubic exactness of Simpson's rule includes every quadratic integrand, so three function evaluations already give the exact answer. Thus the error is zero. For a general smooth integrand the corresponding composite Simpson's rule has error $O(N^{-4})$ in big O notation, but that bound is unnecessarily weak here.

Use composite Simpson's rule on this smooth, bounded one-dimensional interval. Its fourth derivative is bounded on the interval, so the error bound for composite Simpson's rule gives $O(N^{-4})$ in big O notation as the number of function evaluations increases.

Use tensor-product quadrature with composite Simpson's rule in each coordinate. If there are $m$ subintervals in each direction, then $N=(m+1{)}^2$ and the quadrature rule error is $O(m^{-4})$: apply the one-dimensional error bound for composite Simpson's rule successively, using bounded fourth partial derivatives. Hence the error is $O(N^{-2})$ in big O notation. The rectangular domain makes the product grid convenient.

A convenient choice for this irregular region is Monte Carlo integration. The region is contained in $[-1,1{]}^2$. For independent uniform points $U_j$ in that square, letThe indicator random variable incorporates the curved boundary directly. This estimator is unbiased; the integrand is bounded on the square, so its variance is finite. The variance of a sum of independent terms gives root mean square error $O(N^{-1/2})$ in big O notation. This is a stochastic error rate. Applying a rectangular Simpson's rule to the indicator-weighted integrand would lose the smoothness required for its fourth-order error bound.

For a generic integrand in 20 dimensions, Monte Carlo integration gives root mean square error $O(N^{-1/2})$, whereas tensor-product quadrature with composite Simpson's rule gives only $O(N^{-4/20})=O(N^{-1/5})$. One can sample uniformly in the Euclidean unit ball, for example by an independent uniform direction and radius $U^{1/20}$ with $U$ uniform on $[0,1]$.

For this particular integrand, the most efficient elementary choice uses radial integration over a ball first. The area of the unit 19-sphere is $2{\pi }^{10}/9!$, as follows from the volume of an n-ball. HenceThe reduced integrand is smooth. Apply composite Simpson's rule to obtain $O(N^{-4})$ deterministic error in big O notation, with one original radial integrand evaluation per node. If the selection is restricted to direct multidimensional methods, Monte Carlo integration with $O(N^{-1/2})$ root mean square error is the appropriate choice.

By Taylor's theorem with Lagrange remainder, for an increment $t$,where ${\xi }_t$ lies between $x$ and $x+t$. The given third derivative bound implies $|R_x(t)|\le |t{|}^3/6$.

Apply the preceding Taylor's theorem at $t=h$ and $t=-h$, with $h>0$. The even-order terms cancel in the central finite difference, givingBoth Lagrange remainders have magnitude at most $h^3/6$, so the triangle inequality gives the sharp central-secant derivative error

Write the computed function values as $f(x\pm h)+e_{\pm }$, where $|e_{\pm }|\le \delta$. The computed central finite difference $\tilde{d}$ satisfiesThe two contributions are respectively evaluation absolute error and truncation error. For $\delta >0$, step-size choice for a noisy central derivative minimizes their sum: its derivative is $h/3-\delta /h^2$, negative before and positive afterIf $\delta =0$, the bound tends to zero as $h\downarrow 0$ and has no positive minimizing step.