Multistep method

A linear multistep method approximates an ODE using several previous solution and derivative values.

A multiderivative multistep method uses higher time derivatives as well as values and first derivatives from several time levels. For an autonomous ordinary differential equation $y^{\prime }=f(y)$, the second time derivative is $y^{\prime \prime }=f^{\prime }(y)f(y)$ by the chain rule. Its local truncation error must include the higher-derivative terms. Consequently the usual second-order barrier for A-stable linear multistep methods, which only use first derivatives, does not apply.

For a fixed-step multiderivative multistep method, the ordinary zero-stability root condition still controls propagation of the starting errors when all derivative evaluation maps are uniformly Lipschitz continuous on the relevant bounded region. A local defect $O(h^{p+1})$ then yields global error $O(h^p)$ over a fixed time interval, provided the starting errors are $O(h^p)$ and the implicit updates use the nearby solution branch.

For example, writing the numerical error equation as $\rho (E)e_n=h{F}_h(e_{n+s})+d_n$, with $F_h$ uniformly Lipschitz continuous, a bounded impulse response for the root condition for a multistep method givesAbsorbing the last current-step term for small $h$ and applying the discrete Gronwall inequality gives the stated order. The higher derivatives enter through $F_h$, whose bound stays uniform as $h\to 0$.

Zero-stability requires the roots of the first characteristic polynomial to lie in the closed unit disc, with unit-modulus roots simple.

The root condition is the polynomial criterion equivalent to zero-stability for a linear multistep method.

The polynomial $\rho (w)=(w-1)(w^2+w+a)$ satisfies the root condition for a multistep method exactly for $0\le a\le 1$. For $a<0$ a root is below $-1$; for $a>1$ the quadratic root product forces a root outside the unit disc. The endpoints have simple unit-modulus roots, and the repeated root at $a=1/4$ is strictly inside. A consistent method with this polynomial is convergent throughout the closed interval.

A consistent linear multistep method is convergent exactly when it is zero-stable.

For a linear multistep method, convergence for every set of consistent starting values requires the root condition for a multistep method. Apply the recurrence to $y^{\prime }=0$ over $N$ steps. A root $\xi$ with $|\xi |>1$ gives the error mode $e_n=|\xi {|}^{-N}{\xi }^n$: its fixed-index starting errors vanish as $N\to \infty$, but $|e_N|=1$. A unit-modulus root of multiplicity $m\ge 2$ instead gives $e_n=N^{-(m-1)}{n}^{m-1}{\xi }^n$, with the same failure. Repeated roots inside the unit disk are harmless because their polynomial growth is dominated by exponential decay.

For ${\sum }_{j=0}^s{\alpha }_j{y}_{n+j}=h{\sum }_{j=0}^s{\beta }_j{f}_{n+j}$, the characteristic polynomials are $\rho (\zeta )={\sum }_j{\alpha }_j{\zeta }^j$ and $\sigma (\zeta )={\sum }_j{\beta }_j{\zeta }^j$. Applied to $y^{\prime }=\lambda y$, the amplification roots solve $\rho (\zeta )-h\lambda \sigma (\zeta )=0$.

Applying a linear multistep method to the Dahlquist test equation with $z=h\lambda$ produces a constant-coefficient recurrence whose modes satisfy $P_z(w)=0$. Absolute stability requires the resulting roots of a polynomial to lie in the unit disk, with unit-modulus roots simple. Thus multistep stability depends on every recurrence mode, rather than a single one-step stability function.

A linear multistep method has order $p$ exactly whenfor $0\le q\le p$, with the right side interpreted as zero for $q=0$, and the identity first fails at $q=p+1$.

The Taylor expansion of the exact-solution residual for a linear multistep method has the same coefficient sequence asVanishing through degree $p$ is therefore equivalent to order at least $p$. Exact order $p$ additionally requires a nonzero coefficient at degree $p+1$. This symbol conveniently collects all polynomial consistency and order conditions.

An Adams–Moulton method is an implicit linear multistep method obtained by integrating an interpolation polynomial for the vector field that includes the new time level.

An irreducible A-stable linear multistep method has order at most two.