= Solution
A constant-step <linear multistep method> has the form
$$
\sum_{j=0}^k\alpha_jY_{n+j}=h\sum_{j=0}^k\beta_jf(t_{n+j},Y_{n+j}),\qquad\rho(\zeta)=\sum_{j=0}^k\alpha_j\zeta^j,\quad\sigma(\zeta)=\sum_{j=0}^k\beta_j\zeta^j,
$$
with $\alpha_k\ne0$. The <characteristic polynomials of a linear multistep method> encode both accuracy and error propagation. The method has <order of a numerical method> $p$ when insertion of a sufficiently smooth exact solution leaves an unnormalized <local truncation error> $O(h^{p+1})$. The <exponential-symbol order criterion for a multistep method> expresses this as $\rho(e^z)-z\sigma(e^z)=O(z^{p+1})$. In particular, first-order <consistency of a numerical method> requires $\rho(1)=0$ and $\rho'(1)=\sigma(1)$.
Accuracy alone is insufficient. For $f=0$, perturbations obey the recurrence $\rho(E)e_n=0$. The <root condition for a multistep method> requires every <root of a polynomial> $\rho$ to lie in the closed <unit disk>, with each <unit-circle root> simple. This is <zero-stability>. A root outside the <unit disk> causes geometric amplification as $n\sim T/h$ increases; a repeated <unit-circle root> permits polynomial growth in $n$. Either can destroy convergence even for starting perturbations tending to zero.
The <Dahlquist equivalence theorem> states that, for a fixed-coefficient method and a well-posed <ordinary differential equation> with a suitably <Lipschitz continuous> right-hand side, <consistency of a numerical method> and <zero-stability> are equivalent to convergence for all convergent starting data. If the starting errors are $O(h^p)$ and the exact solution is sufficiently smooth, the global error is $O(h^p)$ on a fixed time interval. A stability estimate bounds the propagated sum of $O(h^{p+1})$ local defects over $O(1/h)$ steps; the <discrete Gronwall inequality> controls the dependence of $f$ on the accumulated error. Implicit methods also require the locally consistent, uniquely solvable update branch for sufficiently small $h$.
For example, the <explicit Euler method> has order one and $\rho(\zeta)=\zeta-1$, satisfying the <root condition for a multistep method>. The two-step <Adams-Bashforth method> has order two and $\rho(\zeta)=\zeta(\zeta-1)$, again satisfying it. The <trapezoidal rule> has order two with one step. The two-step <Simpson multistep method>, $Y_{n+2}-Y_n=h(f_{n+2}+4f_{n+1}+f_n)/3$, has order four and the simple roots $1,-1$: it is <zero-stable>, although its <parasitic amplification root> can spoil long-time decay. These examples distinguish finite-time <numerical convergence> from <absolute stability>.
The <first Dahlquist barrier> gives the maximum possible order of a convergent ordinary real $k$-step method:
$$
\boxed{p\le\begin{cases}k+1,&k\text{ odd},\\k+2,&k\text{ even},\end{cases}\qquad p\le k\text{ for an explicit method}.}
$$
These bounds assume only first-derivative evaluations, fixed coefficients and <zero-stability>; the sixth-order <multiderivative multistep method> in <5/a/solution> is outside that class.
To obtain arbitrarily high convergent order within the ordinary class, increase the number of steps. The <Adams-Bashforth method> integrates a <polynomial interpolation> of $k$ past derivative values and has order $k$. The <Adams–Moulton method> includes the new endpoint and has order $k+1$ for $k$ steps. In both families $\rho(\zeta)=\zeta^{k-1}(\zeta-1)$, so the <root condition for a multistep method> holds for every fixed $k$. Starting values can be generated by a <Runge-Kutta method> of sufficient accuracy. The <backward differentiation formula> instead differentiates an interpolating <polynomial>; its order-$k$ members are <zero-stable> only for $1\le k\le6$.
Finally, high order and favorable stiff stability are separate design goals. By the <Second Dahlquist barrier>, an ordinary <A-stable> <linear multistep method> has order at most two. One may accept a smaller <linear stability domain>, use suitable <backward differentiation formula> members for stiff problems, or switch to high-order implicit <Runge Kutta methods> or <multiderivative multistep methods>. A convergent high-order formula still needs time steps appropriate to its stability properties and the problem's <eigenvalues>.
Back to article page