Past exam of the mathematics course of the University of Cambridge / 2009 / iii / Paper 72 / 2

For this two-step family with a third-order member, use the exponential-symbol order criterion for a multistep method. Expanding the exact-solution residual symbol givesThe constant, linear and quadratic coefficients vanish for every parameter. ThusAt the exceptional value the fourth-degree coefficient is $-1/30$, so there is no further increase. This means an unscaled exact-solution residual of order $h^{p+1}$, or a residual divided by the step of order $h^p$.

The first characteristic polynomial factors as $\rho (w)=(w-1)(w-a)$. The root condition for a multistep method requires every root to have modulus at most one and each unit-modulus root to be simple. The root $a=-1$ is allowed because it is distinct from the simple root one; $a=1$ is not, since it makes one a double root. Hence zero-stability holds exactly forOn this interval, $\rho (1)=0$ and ${\rho }^{\prime }(1)=\sigma (1)=1-a\ne 0$ establish consistency of a numerical method. The Dahlquist equivalence theorem, for a fixed-step consistent linear multistep method applied to an ordinary differential equation with a Lipschitz continuous right-hand side with convergent starting values and well-defined small-step updates, says that convergence of a numerical method is equivalent to zero-stability. Therefore the same interval is exactly the convergence of a numerical method range. With sufficiently accurate starting values the convergent members have the orders just computed.

At $a=1$ the Taylor expansion still gives a formal order-two residual, but ${\rho }^{\prime }(1)=\sigma (1)=0$ and the double root prevents a convergent method. Canceling the common factor $w-1$ produces the common-factor cancellation defect in a multistep recurrence and changes the starting relations and cannot repair convergence of a numerical method of the original recurrence. At $a=0$, cancellation of a zero root instead reveals the ordinary trapezoidal rule; it is consistent with the order-two result.

Apply the method to the Dahlquist test equation, put $z=h\lambda$, and retain every root of its amplification polynomial of a multistep method:An A-stable convergent method must satisfy the root condition for a multistep method for every $\mathrm{Re}z\le 0$.

First take $-1<a<0$. As negative real $z$ tends to minus infinity, one root tends to the nonzero root of $\sigma$,It follows by root continuity that some sufficiently negative finite $z$ is unstable. At $a=-1$, the recurrence has polynomial $w^2-2zw-1$; for any negative real $z$, its root $z-\sqrt{z^2+1}$ is below $-1$. Thus all negative convergent parameters are excluded.

For $0\le a<1$, use the boundary-locus test for multistep A-stability. A unit root $w=e^{i\theta }$ with $\sigma (w)\ne 0$ would require $z=\rho (w)/\sigma (w)$. Direct multiplication by the conjugate denominator givesThere is therefore no unit-root crossing in the open left half-plane. The leading coefficient of $P_z$ never vanishes there, since its only zero is the positive real value $2/(1+a)$. For a small negative real $z$, the simple root initially at one moves to $1+z+O(z^2)$, inside the disk, and the other root is close to $a$, also inside. Continuity of polynomial roots and connectedness of the open left half-plane then keep both roots strictly inside throughout that half-plane. Possible zeros of $\sigma$ cause no omitted crossing: for $a>0$ its other root lies strictly inside the unit disk, while at $a=0$ its unit-circle zero $w=-1$ has $\rho (-1)\ne 0$.

On the imaginary axis, if $a>0$ the displayed real part vanishes only at $w=1$, which corresponds to $z=0$ and is simple. Other imaginary-axis parameters retain strictly interior roots. If $a=0$, the two roots are zero and the stability function $(1+z/2)/(1-z/2)$, whose modulus is one on that axis; the unit root is simple. Thus the required boundary root condition for a multistep method holds as well.

Combining necessity and sufficiency givesIn particular, the third-order member $a=-1/5$ is convergent but not A-stable, in agreement with the Second Dahlquist barrier.