Past exam of the mathematics course of the University of Cambridge / 2016 / ib / Paper 1 / 18D (Numerical Analysis)

Convergence of a numerical method on a fixed interval $[0,T]$ means that, as the step size tends to zero and the starting approximations tend to the exact initial values,For a vector-valued ordinary differential equation, replace the absolute value by a norm. The interval remains fixed as $h\to 0$; a small error at only one step is insufficient.

The order of a numerical method is measured by its defect on a smooth exact solution. With the unscaled residual convention for a linear multistep method, order at least $p$ means local residual $O(h^{p+1})$; equivalently, the residual divided by $h$ is $O(h^p)$. Order exactly $p$ means the next coefficient does not vanish in general. For a zero-stable method, under the usual smoothness and Lipschitz continuity assumptions and with starting errors $O(h^p)$, this yields global error $O(h^p)$ on the fixed interval. Local order by itself does not imply convergence without stability.

Insert an exact solution into the linear multistep method and use $f(t,y(t))=y^{\prime }(t)$. Its local residual isExpanding both terms by Taylor theorem givesConsequently $C_0=\cdots =C_p=0$ is sufficient for order at least $p$. It is also necessary: test the residual on the polynomials $y(t)=1,t,\dots ,t^p$, evaluating at $t=0$. For $y(t)=t^k$, it equals $h^k{C}_k$ (and equals $C_0$ for the constant), which can be $O(h^{p+1})$ only if $C_k=0$. These functions can be realized as exact solutions of suitable smooth ordinary differential equations, so this is a genuine necessity test. Thus the order conditions areThis is a statement about local order; zero-stability is the separate condition that turns it into convergent approximation.

The Dahlquist equivalence theorem states that a linear multistep method has convergence of a numerical method if and only if it is consistent and zero-stable, under the standard assumptions for the initial value problem and convergent starting values. Consistency of a numerical method means order at least one, orThe root condition for a multistep method expresses zero-stability: every root of $\rho$ has modulus at most one, and every root with modulus one is simple. Usual hypotheses include a well-posed ordinary differential equation with $f$ continuous in time and Lipschitz continuous in the solution variable, a valid step equation, and starting approximations converging to the exact values.

With ${\rho }_0=a$, ${\rho }_1=\theta$, ${\rho }_2=1$, the constant order condition gives $a=-1-\theta$. The next three order conditions for a linear multistep method giveSolving this linear system yields the unique coefficients of order at least three:The characteristic polynomial controlling zero-stability factors asThe other root is $-1-\theta$. Requiring its modulus to be at most one gives $-2\le \theta \le 0$, but $\theta =-2$ produces a repeated root at one and violates the root condition for a multistep method. At $\theta =0$, the roots $1,-1$ are both simple, so that endpoint is allowed. By the Dahlquist equivalence theorem, the method converges precisely forThe fourth defect coefficient is $C_4=\theta$, so the method has order exactly three for nonzero $\theta$. At $\theta =0$ it is the two-step Simpson method, of order four; thus the extra-order endpoint has correctly remained in the answer.