Linear multistep methods are used for the numerical solution of ordinary differential equations

Numerical ordinary differential equations

Numerical ordinary differential equations is the part of numerical analysis which studies 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

Runge–Kutta methods

In numerical analysis, the Runge–Kutta methods are an important family of implicit and explicit iterative methods for the approximation of solutions of ordinary differential equations. These techniques were developed around 1900 by the German mathematicians C. Runge and M.W. Kutta.See the article...

 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

Linear combination

In mathematics, a linear combination is an expression constructed from a set of terms by multiplying each term by a constant and adding the results...

 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

The result is approximations for the value of at discrete times :

where h is the time step (sometimes referred to as ).

A linear multistep method uses a linear combination of and 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 .

A linear multistep method is a method of the form

where h denotes the step size and f the right-hand side of the differential equation. The coefficients and 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 when it is an nth order polynomial.

If , then the method is called "explicit", since the formula can directly compute .

If then the method is called "implicit", since the value of depends on the value of , and the equation must be solved for . Iterative methods such as Newton's method

Newton's method

In numerical analysis, Newton's method , named after Isaac Newton and Joseph Raphson, is a method for finding successively better approximations to the roots of a real-valued function. The algorithm is first in the class of Householder's methods, succeeded by Halley's method...

 are often used to solve the implicit formula.

Sometimes an explicit multistep method is used to "predict" the value of . That value is then used in an implicit formula to "correct" the value. The result is a Predictor-corrector method

Predictor-corrector method

In mathematics, particularly numerical analysis, a predictor–corrector method is an algorithm that proceeds in two steps. First, the prediction step calculates a rough approximation of the desired quantity...

.

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 on the problem , gives the following results:

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, and , to compute the next value, . However, the initial value problem provides only one value, . One possibility to resolve this issue is to use the computed by Euler's method as the second value. With this choice, the Adams–Bashforth method yields (rounded to four digits):

The exact solution at is , 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 formula

Backward differentiation formula

The backward differentiation formula is a family of implicit methods for the numerical integration of ordinary differential equations. They are linear multistep methods that, for a given function and time, approximate the derivative of that function using information from already computed times,...

s (BDFs).

Adams–Bashforth methods

The Adams–Bashforth methods are explicit methods. The coefficients are and , while the 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 :

• —this is simply the Euler method;
• 
• 
• 
• 
  
  The coefficients can be determined as follows. Use polynomial interpolation
  Polynomial interpolation
  In numerical analysis, polynomial interpolation is the interpolation of a given data set by a polynomial: given some points, find a polynomial which goes exactly through these points.- Applications :...
  
   to find the polynomial p of degree such that
  The Lagrange formula
  Lagrange polynomial
  In numerical analysis, Lagrange polynomials are used for polynomial interpolation. For a given set of distinct points x_j and numbers y_j, the Lagrange polynomial is the polynomial of the least degree that at each point x_j assumes the corresponding value y_j...
  
   for polynomial interpolation yields
  The polynomial p is locally a good approximation of the right-hand side of the differential equation that is to be solved, so consider the equation instead. This equation can be solved exactly; the solution is simply the integral of p. This suggests taking
  The Adams–Bashforth method arises when the formula for p is substituted. The coefficients turn out to be given by
  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
  
  The Adams–Bashforth methods were designed by John Couch Adams
  John Couch Adams
  John Couch Adams was a British mathematician and astronomer. Adams was born in Laneast, near Launceston, Cornwall, and died in Cambridge. The Cornish name Couch is pronounced "cooch"....
  
   to solve a differential equation modelling capillary action
  Capillary action
  Capillary action, or capilarity, is the ability of a liquid to flow against gravity where liquid spontanously rise in a narrow space such as between the hair of a paint-brush, in a thin tube, or in porous material such as paper or in some non-porous material such as liquified carbon fiber, or in a...
  
   due to Francis Bashforth. published his theory and Adams' numerical method .
  

  Adams–Moulton methods

  The Adams–Moulton methods are similar to the Adams–Bashforth methods in that they also have and . 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 , an s-step Adams–Moulton method can reach order , while an s-step Adams–Bashforth methods has only order s.
  
  The Adams–Moulton methods with s = 0, 1, 2, 3, 4 are :
  • — this is the backward Euler method;
  • — this is the trapezoidal rule;
  • 
  • 
  • 
    
    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 . The coefficients are given by
    
    The Adams–Moulton methods are solely due to John Couch Adams
    John Couch Adams
    John Couch Adams was a British mathematician and astronomer. Adams was born in Laneast, near Launceston, Cornwall, and died in Cambridge. The Cornish name Couch is pronounced "cooch"....
    
    , like the Adams–Bashforth methods. The name of Forest Ray Moulton
    Forest Ray Moulton
    Forest Ray Moulton was an American astronomer.He was born in Le Roy, Michigan, and was educated at Albion College. After graduating in 1894 , he performed his graduate studies at the University of Chicago and gained a Ph.D. in 1899...
    
     became associated with these methods because he realized that they could be used in tandem with the Adams–Bashforth methods as a predictor-corrector
    Predictor-corrector method
    In mathematics, particularly numerical analysis, a predictor–corrector method is an algorithm that proceeds in two steps. First, the prediction step calculates a rough approximation of the desired quantity...
    
     pair ; had the same idea. Adams used Newton's method
    Newton's method
    In numerical analysis, Newton's method , named after Isaac Newton and Joseph Raphson, is a method for finding successively better approximations to the roots of a real-valued function. The algorithm is first in the class of Householder's methods, succeeded by Halley's method...
    
     to solve the implicit equation .
    

    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
    a good approximation of the differential equation ? 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 of the method, assuming that all the previous values are exact, and the exact solution of the equation at time , divided by h. A computation using Taylor series
    Taylor series
    In mathematics, a Taylor series is a representation of a function as an infinite sum of terms that are calculated from the values of the function's derivatives at a single point....
    
     shows out that a linear multistep method is consistent if and only if
    All the methods mentioned above are consistent .
    
    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 as h goes to zero. This is equivalent to the following condition on the coefficients of the methods:
    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 and .
    
    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.
    The method is convergent if and only if
    If and only if
    In logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements....
    
     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 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
    The characteristic equation is thus
    which has roots , and the conditions above are satisfied. As 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
    Germund Dahlquist
    Germund Dahlquist was a Swedish mathematician known primarily for his early contributions to the theory of numerical analysis as applied to differential equations....
    
     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 .
    

    Second Dahlquist barrier

    There are no explicit A-stable and linear multistep methods. The implicit ones have order of convergence at most 2 .
    

    External links

    • 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).
    The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.