Linear multistep methods are used for the numerical solution of ordinary differential equations. Conceptually, a numerical method starts from an initial point and then takes a short step forward in time to find the next solution point. The process continues with subsequent steps to map out the solution. Single-step methods (such as Euler's method) refer to only one previous point and its derivative to determine the current value. Methods such as Runge–Kutta take some intermediate steps (for example, a half-step) to obtain a higher order method, but then discard all previous information before taking a second step. Multistep methods attempt to gain efficiency by keeping and using the information from previous steps rather than discarding it. Consequently, multistep methods refer to several previous points and derivative values. In the case of linear multistep methods, a linear combination of the previous points and derivative values is used.
Contents
Definitions
Numerical methods for ordinary differential equations approximate solutions to initial value problems of the form
The result is approximations for the value of
where
Multistep methods use information from the previous
The coefficients
One can distinguish between explicit and implicit methods. If
Sometimes an explicit multistep method is used to "predict" the value of
Examples
Consider for an example the problem
The exact solution is
One-step Euler
A simple numerical method is Euler's method:
Euler's method can be viewed as an explicit multistep method for the degenerate case of one step.
This method, applied with step size
Two-step Adams–Bashforth
Euler's method is a one-step method. A simple multistep method is the two-step Adams–Bashforth method
This method needs two values,
The exact solution at
Families of multistep methods
Three families of linear multistep methods are commonly used: Adams–Bashforth methods, Adams–Moulton methods, and the backward differentiation formulas (BDFs).
Adams–Bashforth methods
The Adams–Bashforth methods are explicit methods. The coefficients are
The Adams–Bashforth methods with s = 1, 2, 3, 4, 5 are (Hairer, Nørsett & Wanner 1993, §III.1; Butcher 2003, p. 103):
The coefficients
The Lagrange formula for polynomial interpolation yields
The polynomial p is locally a good approximation of the right-hand side of the differential equation
The Adams–Bashforth method arises when the formula for p is substituted. The coefficients
Replacing
The Adams–Bashforth methods were designed by John Couch Adams to solve a differential equation modelling capillary action due to Francis Bashforth. Bashforth (1883) published his theory and Adams' numerical method (Goldstine 1977).
Adams–Moulton methods
The Adams–Moulton methods are similar to the Adams–Bashforth methods in that they also have
The Adams–Moulton methods with s = 0, 1, 2, 3, 4 are (Hairer, Nørsett & Wanner 1993, §III.1; Quarteroni, Sacco & Saleri 2000):
The derivation of the Adams–Moulton methods is similar to that of the Adams–Bashforth method; however, the interpolating polynomial uses not only the points
The Adams–Moulton methods are solely due to John Couch Adams, like the Adams–Bashforth methods. The name of Forest Ray Moulton became associated with these methods because he realized that they could be used in tandem with the Adams–Bashforth methods as a predictor-corrector pair (Moulton 1926); Milne (1926) had the same idea. Adams used Newton's method to solve the implicit equation (Hairer, Nørsett & Wanner 1993, §III.1).
The BDF methods are implicit methods with
Analysis
The central concepts in the analysis of linear multistep methods, and indeed any numerical method for differential equations, are convergence, order, and stability.
Consistency and order
The first question is whether the method is consistent: is the difference equation
a good approximation of the differential equation
All the methods mentioned above are consistent (Hairer, Nørsett & Wanner 1993, §III.2).
If the method is consistent, then the next question is how well the difference equation defining the numerical method approximates the differential equation. A multistep method is said to have order p if the local error is of order
The s-step Adams–Bashforth method has order s, while the s-step Adams–Moulton method has order
These conditions are often formulated using the characteristic polynomials
In terms of these polynomials, the above condition for the method to have order p becomes
In particular, the method is consistent if it has order one, which is the case if
Stability and convergence
The numerical solution of a one-step method depends on the initial condition
If the roots of the characteristic polynomial ρ all have modulus less than or equal to 1 and the roots of modulus 1 are of multiplicity 1, we say that the root condition is satisfied. A linear multistep method is zero-stable if and only if the root condition is satisfied (Süli & Mayers 2003, p. 335).
Now suppose that a consistent linear multistep method is applied to a sufficiently smooth differential equation and that the starting values
Furthermore, if the method is convergent, the method is said to be strongly stable if
To assess the performance of linear multistep methods on stiff equations, consider the linear test equation y' = λy. A multistep method applied to this differential equation with step size h yields a linear recurrence relation with characteristic polynomial
This polynomial is called the stability polynomial of the multistep method. If all of its roots have modulus less than one then the numerical solution of the multistep method will converge to zero and the multistep method is said to be absolutely stable for that value of hλ. The method is said to A-stable if it is absolutely stable for all hλ with negative real part. The region of absolute stability is the set of all hλ for which the multistep method is absolutely stable (Süli & Mayers 2003, pp. 347 & 348). For more details, see the section on stiff equations and multistep methods.
Example
Consider the Adams–Bashforth three-step method
One characteristic polynomial is thus
which has roots
The other characteristic polynomial is
First and second Dahlquist barriers
These two results were proved by Germund Dahlquist and represent an important bound for the order of convergence and for the A-stability of a linear multistep method. The first Dahlquist barrier was proved in Dahlquist (1956) and the second in Dahlquist (1963).
First Dahlquist barrier
A zero-stable and linear q-step multistep method cannot attain an order of convergence greater than q + 1 if q is odd and greater than q + 2 if q is even. If the method is also explicit, then it cannot attain an order greater than q (Hairer, Nørsett & Wanner 1993, Thm III.3.5).
Second Dahlquist barrier
There are no explicit A-stable and linear multistep methods. The implicit ones have order of convergence at most 2. The trapezoidal rule has the smallest error constant amongst the A-stable linear multistep methods of order 2.