Past exam of the mathematics course of the University of Cambridge / 2006 / ii / Paper 3 / 38C (Numerical Analysis)

Insert a smooth exact function into the multistep method and expand its residual about $t_n$. DefineThe residual is ${\sum }_{k\ge 0}{h}^k{c}_k{y}^{(k)}(t_n)/k!$. Therefore order at least $p$ is equivalent to $c_0=\cdots =c_p=0$. Applying the residual to the monomials $(t-t_n{)}^k$, $k\le p$, gives exactly those conditions. Linearity then makes them equivalent to exactness on every polynomial of degree at most $p$, as asserted. For exact rather than at-least order $p$, the next coefficient must not vanish.

If an $s$-step formula were exact for degree $2s+1$, use Hermite interpolation to choose $Q$ with $Q(t_{n+i})=0$ for $i<s$, $Q(t_{n+s})=1$, and $Q^{\prime }(t_{n+i})=0$ for every $i$. Its degree is at most $2s+1$. The purported identity would then read ${\rho }_s=0$, contradicting ${\rho }_s=1$. No $s$-step method has order $2s+1$ or higher.

The Dahlquist equivalence theorem states that a linear multistep method is convergent for well-posed sufficiently smooth initial-value problems, with consistent starting values, if and only if it is consistent and zero-stable. Zero-stability means that every root of its first characteristic polynomial lies in the closed unit disk, with roots on the unit circle simple.

Here the characteristic polynomials areConsistency holds because $\rho (1)=0$ and ${\rho }^{\prime }(1)=\sigma (1)=2a$. The two remaining roots have product one. For $0<a<2$ they are distinct conjugate unit roots, and neither equals one. At $a=0$, the root one is triple; at $a=2$, the root minus one is double. Outside $[0,2]$, the remaining roots are real reciprocal roots and one has modulus greater than one. ThusThe order conditions give $c_2=0$ and $c_3=6-a$, which is nonzero throughout the convergent range. Therefore the order of convergence is exactly two, for starting approximations of matching accuracy.