Linear Multistep Methods

Linear multistep methods compute each new solution value from a linear combination of several previous solution values and derivatives, reusing past work to achieve high order at low cost per step.

Definition

A linear multistep method is a method for ordinary differential equations that determines the next solution value through a fixed linear relation among a number of previous solution values and right-hand-side evaluations.

Scope

This topic covers the Adams-Bashforth (explicit) and Adams-Moulton (implicit) families, the backward differentiation formulas for stiff problems, predictor-corrector implementation, the characteristic polynomials and root condition that define zero-stability, and Dahlquist's order barriers that limit what such methods can achieve.

Core questions

• How do multistep methods reuse past values to reach high order with one new function evaluation per step?
• What is zero-stability, and how does the root condition on the characteristic polynomial express it?
• How do predictor-corrector pairs combine explicit and implicit formulas in practice?
• What do Dahlquist's order barriers say about the limits of multistep accuracy and stability?

Key theories

Zero-stability and the root condition

A multistep method is zero-stable, and hence convergent when consistent, exactly when the roots of its first characteristic polynomial lie in the closed unit disk with only simple roots on the boundary; this root condition is the multistep analogue of stability.

Dahlquist barriers

Dahlquist's first barrier caps the order of a zero-stable k-step method, and his second barrier shows that no A-stable linear multistep method can have order greater than two, which is why high-order stiff solvers rely on the BDF compromise of relative rather than absolute stability.

Mechanisms

Adams methods integrate an interpolating polynomial through past derivative values: Adams-Bashforth uses only known values (explicit), Adams-Moulton includes the unknown new value (implicit) for greater accuracy and stability. In practice the two are paired as a predictor-corrector: the explicit formula predicts, the implicit one corrects, typically in one or two iterations. Backward differentiation formulas instead difference past solution values to approximate the derivative at the new point, giving the stiff-stable methods at the heart of stiff ODE codes. Because multistep methods need several starting values, they are bootstrapped by a one-step method.

Clinical relevance

Linear multistep methods, particularly backward differentiation formulas, power the production stiff-ODE solvers used in chemical kinetics, electronic circuit simulation, and large differential-algebraic systems, where evaluating the right-hand side is expensive and reusing past evaluations through multistep formulas yields major efficiency gains.

History

Adams and Bashforth introduced multistep formulas in the nineteenth century, with Moulton adding implicit variants; Dahlquist's 1950s-60s analysis established the stability theory and order barriers that govern the field, and C. William Gear's work in the 1970s made backward-differentiation-formula codes the standard for stiff problems.

Key figures

• John Couch Adams
• Francis Bashforth
• Forest Ray Moulton
• Germund Dahlquist
• C. William Gear

Seminal works

• hairer1993
• iserles2008

Frequently asked questions

How do multistep methods differ from Runge-Kutta methods?

Runge-Kutta methods take several fresh derivative evaluations within each step but discard them afterward, while multistep methods reuse derivative values from previous steps. Multistep methods are therefore cheaper per step but need extra starting values and special handling of step-size changes.

What is the root condition?

It is the requirement that the roots of the method's first characteristic polynomial lie inside or on the unit circle, with boundary roots simple. It guarantees that small errors are not amplified as steps accumulate, ensuring the method is zero-stable and thus convergent.