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

Under the hypotheses of Taylor's theorem with Lagrange remainder, for example $f\in C^{n+1}$ on an interval containing $x$ and $x+h$, there is a point $\xi$ between them such thatThe Lagrange remainder makes this an exact equality, rather than just a truncated Taylor polynomial. For $h=0$ the equality is immediate.

Set $h=(b-a)/n$ and $x_i=a+ih$. Summing the areas of the $n$ endpoint trapezia gives the composite trapezoidal ruleEvery interior value is shared by two adjacent strips; the two endpoint values occur only once with half weight. Evenness of $n$ is not needed for this rule.

For the same uniform grid and even $n$, the composite Simpson's rule integrates a quadratic interpolant over each successive pair of strips:The weights are $1,4,2,4,\dots ,2,4,1$, which explains the even number of strips.

Two strips give $h=\pi /4$, with cosine values $1,1/\sqrt{2},0$. The trapezoidal rule therefore givesThe exact integral is $1$, so the estimate is low, consistent with the concavity of cosine on this interval. The table can be used as $T_2=\frac{1}{2}(0.7854)+0.5554$ before rounding.

With the same three cosine values, Simpson's rule givesUsing the table's $n=12$ row gives $0.2618+4(0.1851)=1.0022$, with the same final rounding. That table row refers to the prefactor $\pi /12$; it does not change the specified number of strips.

Write the derivative equation as $f^{\prime }(x)=\Phi (x,f(x))$ with initial approximation $y_0$. The forward Euler method uses the slope at the start of the step:If the derivative is a known function of $x$ alone, this is $y_{i+1}=y_i+h{f}^{\prime }(x_i)$.

For $f^{\prime }=\Phi (x,f)$, the Backward Euler method uses the slope at the end of the step:This generally requires solving an implicit equation for $y_{i+1}$. For a derivative depending only on $x$, it reduces to $y_{i+1}=y_i+h{f}^{\prime }(x_{i+1})$.

For $f^{\prime }=\Phi (x,f)$, the standard explicit midpoint method isThe implicit midpoint rule instead uses $y_{i+1}=y_i+h\Phi (x_i+h/2,(y_i+y_{i+1})/2)$. When the derivative depends only on $x$, both give $y_{i+1}=y_i+h{f}^{\prime }(x_i+h/2)$.

The endpoint-only request in (e) suggests another possible convention: averaging the endpoint slopes, $y_{i+1}=y_i+\frac{h}{2}[\Phi (x_i,y_i)+\Phi (x_{i+1},y_{i+1})]$. This is the trapezoidal rule, and generally differs from the implicit midpoint rule. A further use of “midpoint” is the two-step explicit midpoint linear multistep method, $y_{i+1}=y_{i-1}+2h\Phi (x_i,y_i)$, which needs a second starting value. The printed question supplies no convention to distinguish these meanings; (e) spells out the resulting alternatives.

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.