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

Put $h=(b-a)/n$, $g_i=g(x_i)$, and $z_0=0$. Under the endpoint-slope convention suggested by the requested connection, the recurrence is $z_{i+1}=z_i+\frac{h}{2}(g_i+g_{i+1})$. Summing telescopes, soSince $G(b)={\int }_a^{b}g(x)dx$ by the fundamental theorem of calculus, this recurrence gives exactly the composite trapezoidal rule. It replaces the average derivative over each strip by the arithmetic mean of its endpoint derivatives.

For the standard midpoint method, the literal endpoint-only request is not valid for general $g$. Both the explicit and implicit one-step midpoint formulas here give insteadthe composite midpoint quadrature rule. It requires half-grid samples. These samples cannot be recovered exactly from $g_0,\dots ,g_n$ for arbitrary smooth $g$: the zero function and $g(x)={\prod }_{j=0}^n(x-x_j{)}^2$ have identical grid values but different midpoint sums. For a smooth $g$, replacing each half-grid sample by $(g_i+g_{i+1})/2$ is an additional approximation, giving $T_n$ with an $O(h^2)$ total difference, rather than an identity. A precise useful relation, obtained by splitting the finer trapezoidal sum into old nodes and midpoints, isHere $T_{2n}$ uses the finer half-grid, so it does not eliminate the missing data.

If “Mid-Point Method” means the two-step explicit midpoint linear multistep method, the recurrence is $z_{i+1}=z_{i-1}+2h{g}_i$. It gives $z_{2r}=2h{\sum }_{j=1}^r{g}_{2j-1}$ and $z_{2r+1}=z_1+2h{\sum }_{j=1}^r{g}_{2j}$, so an odd final index additionally needs a starting value $z_1$. For even $n=2r$, the result is the midpoint quadrature on $r$ double-width strips; equivalently $z_n=2T_n-T_{n/2}$. The question specifies neither even $n$ nor a starter. Thus the trapezoidal expression above is the natural endpoint-average interpretation, while the other common midpoint meanings require the qualifications just given. The ambiguity is present in the original PDF.