A linear multistep method approximates an ordinary differential equation using values retained from several time levels. On a uniform grid , its constant-coefficient form isThe linearity is in the way values and derivatives are combined; the vector field itself can be nonlinear. The method is explicit when and implicit when the new value appears inside through . An implicit update requires a suitable algebraic solve, in addition to a formal recurrence.[ref]
A special stability problem for linear multistep methods by Germund Dahlquist. §1, equation 1.2 and explicit/implicit distinction, printed p. 27
The two-step Adams-Bashforth method, for example, uses . It reuses the preceding derivative rather than calculating several new Runge-Kutta stages within one step. A -step recurrence needs starting values, often supplied by a Runge-Kutta method of compatible accuracy.
Consistency controls the defect on a smooth exact solution; zero-stability controls the amplification of starting and local errors. Both are required by the Dahlquist equivalence theorem for convergence under its regularity assumptions. Changing the step sizes generally requires changing the coefficients and revisiting stability; uniform-grid coefficients cannot simply be reused at arbitrary time spacings.
For an ordinary differential equation , this linear multistep method uses a centered derivative across the two-step interval , evaluated at its midpoint . It requires two starting values, and . For a sufficiently smooth exact solution, Taylor's theorem givesThe unscaled local residual is therefore and the method has order two. Its first characteristic polynomial is , with the simple roots , so it satisfies the root condition for a multistep method; the second root is a parasitic amplification root. This two-step method differs from the one-step midpoint method and the implicit midpoint rule.
For the special equation and , an even number of steps gives , independently of the odd-index starting value. It is the composite midpoint quadrature rule on intervals of width . An odd final index depends on , which must be specified separately.
Take . The root condition for a multistep method holds exactly for . Since , these and only these parameters give a convergent method. Its exponential-symbol order criterion for a multistep method has defect , giving formal order three except at , where the first defect is . None of the convergent family is A-stable: for a parasitic root , perturbation of gives . A small negative real therefore moves it outside the unit disk. At , cancellation would remove a double unit root, but the original recurrence retains that unstable parasitic behavior; it is not legitimately replaced by the reduced Backward Euler recurrence for arbitrary starting values.
Integrating a quadratic interpolant of the derivative over two steps gives this linear multistep method, which has order four. Its local truncation error is and its zero-stability polynomial is , with simple roots . The Dahlquist equivalence theorem therefore gives fourth-order convergence with sufficiently accurate starts. This attains the even two-step first Dahlquist barrier. Its undamped parasitic zero-step mode need not have favorable long-time absolute stability; finite-time convergence and stiff damping are separate requirements.
For a consistent zero-stable real linear -step method with constant coefficients and only first-derivative evaluations, the attainable order is at most for odd and for even . For an explicit method the bound is . These are order barriers under the root condition for a multistep method, not bounds on multiderivative methods or on arbitrary variable-step formulations. The Second Dahlquist barrier adds the stronger bound of order two for irreducible A-stable methods.
Using Newton-Cotes closed quadrature for the integrated derivative yields the displayed linear multistep method. Its first characteristic polynomial is , whose unit-circle roots are all simple, proving zero-stability. Quadrature exactness gives order for odd and at least for even . The first Dahlquist barrier gives equality, while the Dahlquist equivalence theorem gives convergence with consistent starts. These are finite-time convergence statements, not claims of A-stability.
For a real consistent zero-stable linear multistep method, transform its first characteristic polynomial by to . The root condition for a multistep method puts all finite roots of in the closed left half-plane; real linear factors and conjugate quadratic factors consequently give nonnegative coefficients, after choosing . The order criterion requires a polynomial of degree at most to agree through degree with . The latter quotient has strictly negative nonconstant even coefficients. Its first even coefficient beyond degree includes a strictly negative multiple of and cannot vanish. This gives the stated bound.
Write . Pairing and after differentiating twice givesThe power series of has strictly positive even coefficients, and the other factor has nonnegative even coefficients. Thus every even coefficient of is negative. Since is even with , the displayed sign pattern follows. This supplies a short positivity argument for the first Dahlquist barrier.
The exponential-symbol order criterion for a multistep method gives leading defect , so the family has order two except at , where it has order three. The root condition for a multistep method holds exactly for , and the convergent A-stable members are exactly . At it reduces to the trapezoidal rule after removal of a zero root. At a repeated root one destroys convergence of a numerical method of the original recurrence despite a common polynomial factor and a formally vanishing second-order residual.
An explicit linear multistep method that integrates a polynomial extrapolation of the past derivative values. The displayed two-step member is second order in time: the linear interpolant through , integrated over the next step, gives coefficients . For a spatially discretized partial differential equation, the spatial error must also be included in the total local defect.
For centered-space diffusion, a Fourier mode gives , with . For the roots have opposite signs, the positive root lies in , and the negative root lies in exactly when . At the unit-modulus roots are simple. Hence the root condition for a multistep method holds for every Fourier frequency exactly when . Under fixed , the unscaled one-step defect is ; dividing by the step changes its order to .
Canceling a common factor of the characteristic polynomials changes the allowed starting relations and can remove a parasitic mode rather than prove stability of the original recurrence. For example and fail zero-stability. On , the original recurrence admits ; starting perturbations vanish but give divergent error at fixed positive time. The canceled one-step recurrence excludes these data, so its stability cannot be assigned to the original scheme.
This real-parameter linear multistep method has formal order two except at the degenerate value , where its local symbol vanishes to fourth degree. The zero-stability roots are and , so it is convergent exactly for . Every convergent member is A-stable: the boundary-locus test for multistep A-stability gives nonnegative real part , with no unit-circle denominator zero for . At the two interlaced sequences obey a trapezoidal step of length . At it is the BDF2 method. The endpoint two fails the root condition for a multistep method even though canceling a common polynomial factor resembles the trapezoidal rule.
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 , the second time derivative is 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 and , inserting a smooth exact solution into the displayed recurrence gives defect . This follows by expanding . The terms through vanish and the coefficient is nonzero. Its zero-step polynomial is , whose roots are simple and of unit modulus. Thus it is zero-stable and has order six, provided starting values and derivative evaluations have corresponding accuracy.
For the multiderivative multistep method , with , centered expansion gives defect coefficients , , and at powers . Their simultaneous vanishing gives the displayed parameters. The next coefficient is at , so the formal order is six. Reflection symmetry removes every even defect power. The method satisfies fifth-order conditions but cannot have exact order five.
For the symmetric two-step two-derivative formula, the closed-disk root condition for a multistep method fails off the imaginary axis. Positive real part makes the product of root moduli exceed one; negative real part fails the complex quadratic Schur criterion, as in the empty strict decay domain of the symmetric two-derivative formula proof. On , write and set . The amplification polynomial becomes . Its two roots are distinct and on the unit circle exactly when , or . Thus the bounded-root set consists of the imaginary intervals and , including and excluding the double-root endpoints. In particular, the set is unbounded. Unit-modulus oscillations are bounded but do not tend to zero.
On the Dahlquist test equation, write the amplification polynomial as , where and . The identity shows that both roots of a polynomial can lie inside the open unit disk only if . But the complex quadratic Schur criterion would then require , which is impossible. Thus the strict linear stability domain is empty. This concerns robust damping of all modes, rather than convergence on fixed time intervals or the bounded-root stability set of the symmetric two-derivative formula.
On the Dahlquist test equation, the symmetric two-step two-derivative formula has amplification polynomial . For every real , its leading coefficient is positive and , whereas as . The intermediate value theorem therefore gives a real root below minus one. Thus the method is not A-stable, without any appeal to a multistep order barrier.
The endpoint expansion of this multiderivative multistep method has unscaled defect and zero-stability roots , giving third-order convergence with suitably accurate starting values. On the Dahlquist test equation its amplification roots obey . The complex quadratic Schur criterion puts both roots in the open unit disk for , and only the simple root one reaches the boundary at . Thus it is A-stable; its higher derivative places it outside the hypotheses of the Second Dahlquist barrier.
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 then yields global error over a fixed time interval, provided the starting errors are and the implicit updates use the nearby solution branch.
For example, writing the numerical error equation as , with uniformly Lipschitz continuous, a bounded impulse response for the root condition for a multistep method givesAbsorbing the last current-step term for small and applying the discrete Gronwall inequality gives the stated order. The higher derivatives enter through , whose bound stays uniform as .
Zero-stability controls whether small perturbations are amplified uniformly as a fixed time interval is covered by more and more steps. For a constant-coefficient linear multistep method, the zero-step recurrence isZero-stability requires a bound , with independent of small and the starting perturbation. The root condition for a multistep method characterizes this uniform boundedness.[ref]
Fundamentals of Numerical Computation by Tobin A. Driscoll and others. Zero-stability of multistep methods, Theorem 74, root condition and recurrence-mode proof
For , every solution is , so perturbations remain bounded even though the alternating component does not decay. For , the mode grows like at fixed positive time and violates zero-stability. This is distinct from absolute stability, which tests nonzero and can constrain a particular step size.
The root condition for a multistep method says that every root of a polynomial of its first characteristic polynomial satisfies , and each root with is simple. For constant coefficients this is equivalent to zero-stability.
A root of multiplicity produces recurrence modes for . If , the exponential decay dominates every such polynomial factor, so repeated interior roots are allowed. At , any nonconstant polynomial factor grows, explaining the simplicity requirement. A root outside the unit disk gives exponential growth even when simple. Thus satisfies the condition, while does not.
An amplification root of a multistep method is parasitic when it represents an additional numerical mode rather than the principal mode approximating the exact differential-equation flow. For a consistent method the principal root starts at one as the step tends to zero, while other roots can start elsewhere. A simple parasitic root on the unit circle is compatible with zero-stability, but its motion outside the circle for a negative test parameter can destroy absolute stability. Fixed-time convergence and all-time damping must be distinguished.
Replacing the derivative in by a central finite difference gives . Its principal root is , while the parasitic amplification root is . On a fixed time interval, converges uniformly to exactly when and . A fixed nonzero parasitic amplitude alternates between two incompatible limits, but a vanishing starting error can converge despite the root's modulus exceeding one. This distinguishes fixed-time numerical convergence from long-time absolute stability.
The polynomial satisfies the root condition for a multistep method exactly for . For a root is below ; for the quadratic root product forces a root outside the unit disc. The endpoints have simple unit-modulus roots, and the repeated root at is strictly inside. A consistent method with this polynomial is convergent throughout the closed interval.
For a fixed-coefficient linear multistep method applied to a well-posed initial value problem with a continuous right-hand side uniformly Lipschitz continuous in the solution argument on the relevant region, consistency of a numerical method and zero-stability are equivalent to numerical convergence for arbitrary starting values whose errors tend to zero. The time interval is fixed while the step size tends to zero; an implicit numerical method must use its well-defined nearby solution branch for sufficiently small steps.
The quantitative statement is that a zero-stable method with consistency error and starting errors has global error , provided the exact solution is sufficiently smooth for that residual bound. A bounded response to step defects follows from the root condition for a multistep method, and the discrete Gronwall inequality controls the nonlinear error terms. Mere continuity of the right-hand side does not by itself supply these hypotheses or uniqueness of the exact solution.
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 over steps. A root with gives the error mode : its fixed-index starting errors vanish as , but . A unit-modulus root of multiplicity instead gives , with the same failure. Repeated roots inside the unit disk are harmless because their polynomial growth is dominated by exponential decay.
Applying a linear multistep method to the Dahlquist test equation with produces a constant-coefficient recurrence whose modes satisfy . 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.
An amplification root is a root of a polynomial governing a geometric mode of a numerical recurrence on the Dahlquist test equation. Its modulus measures damping or growth per step. A repeated root produces additional modes such as ; therefore a unit-circle root can be permitted by a bounded-root condition only when it is simple. The principal root approximates near zero, while additional roots can describe parasitic amplification roots.
If the derivative characteristic polynomial of a linear multistep method has a simple root outside the unit disk and keeps its degree in the limit, then its absolute stability region is bounded. Otherwise a stable sequence with would give amplification polynomials tending coefficientwise to . A root near the exterior root would persist by continuity, contradicting the root condition for a multistep method. This argument excludes stability at every sufficiently large complex , not only along the negative real axis.
A linear multistep method has order exactly whenfor , with the right side interpreted as zero for , and the identity first fails at .
The Taylor expansion of the exact-solution residual for a linear multistep method has the same coefficient sequence asVanishing through degree is therefore equivalent to order at least . Exact order additionally requires a nonzero coefficient at degree . This symbol conveniently collects all polynomial consistency and order conditions.
An Adams–Moulton method is an implicit linear multistep method obtained by interpolating derivative values including the new time level and integrating that interpolation polynomial over the next interval. For uniform step size , linear interpolation through gives the second-order trapezoidal ruleQuadratic interpolation through instead gives the third-order formulaBecause depends on the unknown , a nonlinear vector field generally requires a solve. Substituting a predicted new value only once defines a different composite numerical procedure; it should not automatically inherit the fully implicit method's absolute stability region.
The Second Dahlquist barrier states that an irreducible A-stable linear multistep method with constant real coefficients and only first-derivative evaluations has classical order at most two. Irreducible means that its characteristic polynomials and have no common factor. The theorem concerns the entire recurrence, rather than a formula obtained by canceling unstable starting modes.[ref]
A special stability problem for linear multistep methods by Germund Dahlquist. §§1–2, coprime characteristic polynomials, A-stability and the order bound
The trapezoidal rule and BDF2 method attain order two while remaining A-stable. Increasing the number of retained values cannot produce a third-order method with all of these properties. A multiderivative multistep method lies outside the hypotheses: the A-stable third-order two-step multiderivative method uses second derivatives and therefore provides no contradiction. Likewise, high-order Gauss collocation methods are Runge-Kutta methods, a different class.
Articles by others on the same topic
Linear multistep methods are numerical techniques used to solve ordinary differential equations (ODEs) by approximating the solutions at discrete points. Unlike single-step methods (like the Euler method or Runge-Kutta methods) that only use information from the current time step to compute the next step, linear multistep methods utilize information from multiple previous time steps.