Linear multistep method

"Adams method" redirects here. For the electoral apportionment method, see Method of smallest divisors.

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.

Definitions

Numerical methods for ordinary differential equations approximate solutions to initial value problems of the form

${\displaystyle y'=f(t,y),\quad y(t_{0})=y_{0}.}$ 

The result is approximations for the value of ${\displaystyle y(t)}$  at discrete times ${\displaystyle t_{i}}$ :

${\displaystyle t_{i}=t_{0}+ih}$ 

${\displaystyle y_{i}=y(t_{i})=y(t_{0}+ih)}$ 

${\displaystyle f_{i}=f(t_{i},y_{i})}$ 

where h is the time step (sometimes referred to as ${\displaystyle \Delta t}$ ).

A linear multistep method uses a linear combination of ${\displaystyle y_{i}}$  and ${\displaystyle y_{i}'}$  to calculate the value of y for the desired current step.

Multistep method will use the previous s steps to calculate the next value. Consequently, the desired value at the current processing stage is ${\displaystyle y_{n+s}}$ .

A linear multistep method is a method of the form

${\displaystyle {\begin{aligned}&y_{n+s}+a_{s-1}y_{n+s-1}+a_{s-2}y_{n+s-2}+\cdots +a_{0}y_{n}\\&\qquad {}=h{\bigl (}b_{s}f(t_{n+s},y_{n+s})+b_{s-1}f(t_{n+s-1},y_{n+s-1})+\cdots +b_{0}f(t_{n},y_{n}){\bigr )},\end{aligned}}}$ 

where h denotes the step size and f the right-hand side of the differential equation. The coefficents ${\displaystyle a_{0},\ldots ,a_{s-1}}$  and ${\displaystyle b_{0},\ldots ,b_{s}}$  determine the method. The designer of the method chooses the coefficients; often, many coefficients are zero. Typically, the designer chooses the coefficients so they will exactly interpolate ${\displaystyle y(t)}$  when it is an nth order polynomial.

If the value of ${\displaystyle b_{s}}$  is nonzero, then the value of ${\displaystyle y_{n+s}}$  depends on the value of ${\displaystyle f(t_{n+s},y_{n+s})}$ . Consequently, the method is explicit if ${\displaystyle b_{s}=0}$ . In that case, the formula can directly compute ${\displaystyle y_{n+s}}$ . If ${\displaystyle b_{s}\neq 0}$  then the method is implicit and the equation for ${\displaystyle y_{n+s}}$  must be solved. Iterative methods such as Newton's method are often used to solve the implicit formula.

Sometimes an explicit multistep method is used to "predict" the value of ${\displaystyle y_{n+s}}$ . That value is then used in an implicit formula to "correct" the value. The result is a Predictor-corrector method.

Examples

Consider for an example the problem

${\displaystyle y'=y,\quad y(0)=1.}$ 

The exact solution is ${\displaystyle y(t)=\mathrm {e} ^{t}}$ .

One-Step Euler

A simple numerical method is Euler's method:

${\displaystyle y_{n+1}=y_{n}+hf(t_{n},y_{n}).\,}$ 

Euler's method can be viewed as an explicit multistep method for the degenerate case of one step.

This method, applied with step size ${\displaystyle h={\tfrac {1}{2}}}$  on the problem ${\displaystyle y'=y}$ , gives the following results:

${\displaystyle {\begin{aligned}y_{1}&=y_{0}+hf(t_{0},y_{0})=1+{\tfrac {1}{2}}\cdot 1=1.5,\\y_{2}&=y_{1}+hf(t_{1},y_{1})=1.5+{\tfrac {1}{2}}\cdot 1.5=2.25,\\y_{3}&=y_{2}+hf(t_{2},y_{2})=2.25+{\tfrac {1}{2}}\cdot 2.25=3.375,\\y_{4}&=y_{3}+hf(t_{3},y_{3})=3.375+{\tfrac {1}{2}}\cdot 3.375=5.0625.\end{aligned}}}$ 

Two-Step Adams Bashforth

Euler's method is a one-step method. A simple multistep method is the two-step Adams–Bashforth method

${\displaystyle y_{n+2}=y_{n+1}+{\tfrac {3}{2}}hf(t_{n+1},y_{n+1})-{\tfrac {1}{2}}hf(t_{n},y_{n}).}$ 

This method needs two values, ${\displaystyle y_{n+1}}$  and ${\displaystyle y_{n}}$ , to compute the next value, ${\displaystyle y_{n+2}}$ . However, the initial value problem provides only one value, ${\displaystyle y_{0}=1}$ . One possibility to resolve this issue is to use the ${\displaystyle y_{1}}$  computed by Euler's method as the second value. With this choice, the Adams–Bashforth method yields (rounded to four digits):

${\displaystyle {\begin{aligned}y_{2}&=y_{1}+{\tfrac {3}{2}}hf(t_{1},y_{1})-{\tfrac {1}{2}}hf(t_{0},y_{0})=1.5+{\tfrac {3}{2}}\cdot {\tfrac {1}{2}}\cdot 1.5-{\tfrac {1}{2}}\cdot {\tfrac {1}{2}}\cdot 1=2.375,\\y_{3}&=y_{2}+{\tfrac {3}{2}}hf(t_{2},y_{2})-{\tfrac {1}{2}}hf(t_{1},y_{1})=2.375+{\tfrac {3}{2}}\cdot {\tfrac {1}{2}}\cdot 2.375-{\tfrac {1}{2}}\cdot {\tfrac {1}{2}}\cdot 1.5=3.7812,\\y_{4}&=y_{3}+{\tfrac {3}{2}}hf(t_{3},y_{3})-{\tfrac {1}{2}}hf(t_{2},y_{2})=3.7812+{\tfrac {3}{2}}\cdot {\tfrac {1}{2}}\cdot 3.7812-{\tfrac {1}{2}}\cdot {\tfrac {1}{2}}\cdot 2.375=6.0234.\end{aligned}}}$ 

The exact solution at ${\displaystyle t=t_{4}=2}$  is ${\displaystyle \mathrm {e} ^{2}=7.3891\ldots }$ , so the two-step Adams–Bashforth method is more accurate than Euler's method. This is always the case if the step size is small enough.

Multistep Method Families

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 ${\displaystyle a_{s-1}=-1}$  and ${\displaystyle a_{s-2}=\cdots =a_{0}=0}$ , while the ${\displaystyle b_{j}}$  are chosen such that the methods has order s (this determines the methods uniquely).

The Adams–Bashforth methods with s = 1, 2, 3, 4, 5 are (Hairer, Nørsett & Wanner 1993, §III.1; Butcher 2003, p. 103):

• ${\displaystyle y_{n+1}=y_{n}+hf(t_{n},y_{n})\,}$ —this is simply the Euler method;
• ${\displaystyle y_{n+2}=y_{n+1}+h\left({\tfrac {3}{2}}f(t_{n+1},y_{n+1})-{\tfrac {1}{2}}f(t_{n},y_{n})\right);}$ 
• ${\displaystyle y_{n+3}=y_{n+2}+h\left({\tfrac {23}{12}}f(t_{n+2},y_{n+2})-{\tfrac {4}{3}}f(t_{n+1},y_{n+1})+{\tfrac {5}{12}}f(t_{n},y_{n})\right);}$ 
• ${\displaystyle y_{n+4}=y_{n+3}+h\left({\tfrac {55}{24}}f(t_{n+3},y_{n+3})-{\tfrac {59}{24}}f(t_{n+2},y_{n+2})+{\tfrac {37}{24}}f(t_{n+1},y_{n+1})-{\tfrac {3}{8}}f(t_{n},y_{n})\right);}$ 
• ${\displaystyle {\begin{aligned}y_{n+5}=y_{n+4}+h{\bigl (}&{\tfrac {1901}{720}}f(t_{n+4},y_{n+4})-{\tfrac {1387}{360}}f(t_{n+3},y_{n+3})\\&+{\tfrac {109}{30}}f(t_{n+2},y_{n+2})-{\tfrac {637}{360}}f(t_{n+1},y_{n+1})+{\tfrac {251}{720}}f(t_{n},y_{n}){\bigr )}.\end{aligned}}}$ 

The coefficients ${\displaystyle b_{j}}$  can be determined as follows. Use polynomial interpolation to find the polynomial p of degree ${\displaystyle s-1}$  such that

${\displaystyle p(t_{n+i})=f(t_{n+i},y_{n+i}),\qquad {\text{for }}i=0,\ldots ,s-1.}$ 

The Lagrange formula for polynomial interpolation yields

${\displaystyle p(t)=\sum _{j=0}^{s-1}{\frac {(-1)^{s-j-1}f(t_{n+j},y_{n+j})}{j!(s-j-1)!h^{s-1}}}\prod _{i=0 \atop i\neq j}^{s-1}(t-t_{n+i}).}$ 

The polynomial p is locally a good approximation of the right-hand side of the differential equation ${\displaystyle y'=f(t,y)}$  that is to be solved, so consider the equation ${\displaystyle y'=p(t)}$  instead. This equation can be solved exactly; the solution is simply the integral of p. This suggests taking

${\displaystyle y_{n+s}=y_{n+s-1}+\int _{t_{n+s-1}}^{t_{n+s}}p(t)\,dt.}$ 

The Adams–Bashforth method arises when the formula for p is substituted. The coefficients ${\displaystyle b_{j}}$  turn out to be given by

${\displaystyle b_{s-j-1}={\frac {(-1)^{j}}{j!(s-j-1)!}}\int _{0}^{1}\prod _{i=0 \atop i\neq j}^{s-1}(u+i)\,du,\qquad {\text{for }}j=0,\ldots ,s-1.}$ 

Replacing f(t, y) by its interpolant p incurs an error of order h^s, and it follows that the s-step Adams–Bashforth method has indeed order s (Iserles 1996, §2.1)

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 ${\displaystyle a_{s-1}=-1}$  and ${\displaystyle a_{s-2}=\cdots =a_{0}=0}$ . Again the b coefficients are chosen to obtain the highest order possible. However, the Adams–Moulton methods are implicit methods. By removing the restriction that ${\displaystyle b_{s}=0}$ , an s-step Adams–Moulton method can reach order ${\displaystyle s+1}$ , while an s-step Adams–Bashforth methods has only order s.

The Adams–Moulton methods with s = 0, 1, 2, 3, 4 are (Hairer, Nørsett & Wanner 1993, §III.1; Quarteroni, Sacco & Saleri 2000):

• ${\displaystyle y_{n}=y_{n-1}+hf(t_{n},y_{n})\,}$  — this is the backward Euler method;
• ${\displaystyle y_{n+1}=y_{n}+{\tfrac {1}{2}}h{\big (}f(t_{n+1},y_{n+1})+f(t_{n},y_{n}){\big )}}$  — this is the trapezoidal rule;
• ${\displaystyle y_{n+2}=y_{n+1}+h{\big (}{\tfrac {5}{12}}f(t_{n+2},y_{n+2})+{\tfrac {2}{3}}f(t_{n+1},y_{n+1})-{\tfrac {1}{12}}f(t_{n},y_{n}){\big )};}$ 
• ${\displaystyle y_{n+3}=y_{n+2}+h{\big (}{\tfrac {3}{8}}f(t_{n+3},y_{n+3})+{\tfrac {19}{24}}f(t_{n+2},y_{n+2})-{\tfrac {5}{24}}f(t_{n+1},y_{n+1})+{\tfrac {1}{24}}f(t_{n},y_{n}){\big )}.}$ 
• ${\displaystyle {\begin{aligned}y_{n+4}=y_{n+3}+h{\big (}&{\tfrac {251}{720}}f(t_{n+4},y_{n+4})+{\tfrac {646}{720}}f(t_{n+3},y_{n+3})\\&-{\tfrac {264}{720}}f(t_{n+2},y_{n+2})+{\tfrac {106}{720}}f(t_{n+1},y_{n+1})-{\tfrac {19}{720}}f(t_{n},y_{n}){\big )}.\end{aligned}}}$ 

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 t_n−1, … t_n−s, as above, but also ${\displaystyle t_{n}}$ . The coefficients are given by

${\displaystyle b_{s-j}={\frac {(-1)^{j}}{j!(s-j)!}}\int _{0}^{1}\prod _{i=0 \atop i\neq j}^{s}(u+i-1)\,du,\qquad {\text{for }}j=0,\ldots ,s.}$ 

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).

Analysis

The central concepts in the analysis of linear multistep methods, and indeed any numerical method for differential equations, are convergence, order, and stability.

The first question is whether the method is consistent: is the difference equation

${\displaystyle {\begin{aligned}&y_{n+s}+a_{s-1}y_{n+s-1}+a_{s-2}y_{n+s-2}+\cdots +a_{0}y_{n}\\&\qquad {}=h{\bigl (}b_{s}f(t_{n+s},y_{n+s})+b_{s-1}f(t_{n+s-1},y_{n+s-1})+\cdots +b_{0}f(t_{n},y_{n}){\bigr )},\end{aligned}}}$ 

a good approximation of the differential equation ${\displaystyle y'=f(t,y)}$ ? More precisely, a multistep method is consistent if the local error goes to zero as the step size h goes to zero, where the local error is defined to be the difference between the result ${\displaystyle y_{n+s}}$  of the method, assuming that all the previous values ${\displaystyle y_{n+s-1},\ldots ,y_{n}}$  are exact, and the exact solution of the equation at time ${\displaystyle t_{n+s}}$ . A computation using Taylor series shows out that a linear multistep method is consistent if and only if

${\displaystyle \sum _{k=0}^{s-1}a_{k}=-1\quad {\text{and}}\quad \sum _{k=0}^{s}b_{k}=s+\sum _{k=0}^{s-1}ka_{k}.}$ 

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 ${\displaystyle O(h^{p+1})}$  as h goes to zero. This is equivalent to the following condition on the coefficients of the methods:

${\displaystyle \sum _{k=0}^{s-1}a_{k}=-1\quad {\text{and}}\quad qk^{q-1}\sum _{k=0}^{s}b_{k}=s^{q}+\sum _{k=0}^{s-1}k^{q}a_{k}{\text{ for }}q=1,\ldots ,p.}$ 

The s-step Adams–Bashforth method has order s, while the s-step Adams–Moulton method has order ${\displaystyle s+1}$  (Hairer, Nørsett & Wanner 1993, §III.2).

These conditions are often formulated using the characteristic polynomials

${\displaystyle \rho (z)=z^{s}+\sum _{k=0}^{s-1}a_{k}z^{k}\quad {\text{and}}\quad \sigma (z)=\sum _{k=0}^{s}b_{k}z^{k}.}$ 

In terms of these polynomials, the above condition for the method to have order p becomes

${\displaystyle \rho (\mathrm {e} ^{h})-h\sigma (\mathrm {e} ^{h})=O(h^{p+1})\quad {\text{as }}h\to 0.}$ 

In particular, the method is consistent if it has order one, which is the case if ${\displaystyle \rho (1)=0}$  and ${\displaystyle \rho '(1)=\sigma (1)}$ .

If the roots of the characteristic polynomial ${\displaystyle \rho }$  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. The method is convergent if and only if it is consistent and the root condition is satisfied. Consequently, a consistent method is stable if and only if this condition is satisfied, and thus the method is convergent if and only if it is stable.

Furthermore, if the method is stable, the method is said to be strongly stable if ${\displaystyle z=1}$  is the only root of modulus 1. If it is stable and all roots of modulus 1 are not repeated, but there is more than one such root, it is said to be relatively stable. Note that 1 must be a root; thus stable methods are always one of these two.

Example

Consider the Adams–Bashforth three-step method

${\displaystyle y_{n+1}=y_{n}+h\left({23 \over 12}f(t_{n},y_{n})-{16 \over 12}f(t_{n-1},y_{n-1})+{5 \over 12}f(t_{n-2},y_{n-2})\right).}$ 

The characteristic equation is thus

${\displaystyle q(z)=z^{3}-z^{2}=z^{2}(z-1)\,}$ 

which has roots ${\displaystyle z=0,1}$ , and the conditions above are satisfied. As ${\displaystyle z=1}$  is the only root of modulus 1, the method is strongly stable.

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.

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 (Hairer & Wanner 1996, Thm V.1.4).

See also

• Digital energy gain

References

• Bashforth, Francis (1883), An Attempt to test the Theories of Capillary Action by comparing the theoretical and measured forms of drops of fluid. With an explanation of the method of integration employed in constructing the tables which give the theoretical forms of such drops, by J. C. Adams, Cambridge.
• Butcher, John C. (2003), Numerical Methods for Ordinary Differential Equations, John Wiley, ISBN 978-0-471-96758-3.
• Goldstine, Herman H. (1977), A History of Numerical Analysis from the 16th through the 19th Century, New York: Springer-Verlag, ISBN 978-0-387-90277-7.
• Hairer, Ernst; Nørsett, Syvert Paul; Wanner, Gerhard (1993), Solving ordinary differential equations I: Nonstiff problems (2nd ed.), Berlin: Springer Verlag, ISBN 978-3-540-56670-0.
• Hairer, Ernst; Wanner, Gerhard (1996), Solving ordinary differential equations II: Stiff and differential-algebraic problems (2nd ed.), Berlin, New York: Springer-Verlag, ISBN 978-3-540-60452-5.
• Iserles, Arieh (1996), A First Course in the Numerical Analysis of Differential Equations, Cambridge University Press, ISBN 978-0-521-55655-2.
• Milne, W. E. (1926), "Numerical integration of ordinary differential equations", American Mathematical Monthly, 33 (9), Mathematical Association of America: 455–460, doi:10.2307/2299609, JSTOR 10.2307/2299609 {{citation}}: More than one of |number= and |issue= specified (help).
• Moulton, Forest R. (1926), New methods in exterior ballistics, University of Chicago Press.
• Quarteroni, Alfio; Sacco, Riccardo; Saleri, Fausto (2000), Matematica Numerica, Springer Verlag, ISBN 978-8-847-00077-3

External links

• Weisstein, Eric W. "Adams Method". MathWorld.
• Adams-Bashforth-Moulton Method
• DotNumerics: Ordinary Differential Equations for C# and VB.NET Initial-value problem for nonstiff and stiff ordinary differential equations (explicit Runge-Kutta, implicit Runge-Kutta, Gear’s BDF and Adams-Moulton).