Linear multistep method

Multi-step methods are methods for the numerical solution of initial value problems. In contrast to one-step procedures such as the Runge- Kutta method, to use multi-step process the information from the previously calculated points.

  • 3.1 Explicit methods
  • 3.2 Implicit methods
  • 4.1 start values
  • 4.2 predictor-corrector method 4.2.1

Theory

There is an initial value problem

Optionally with an initial condition. A linear multistep method ( LMV ) generated at a given increment a sequence of approximations to the function values

It exists between the approximations and the differential equation of the linear recurrence

The coefficients and determine the multi-step process, this is true.

It is called the LMV implicitly, if, and explicitly, is appropriate. Implicit methods can have one to one higher order of consistency as an explicit method with the same length m of Koeffiziententupel. Its disadvantage, however, that is required in the calculation of this. This leads to non-linear systems of equations. For explicit methods can be the linear recurrence equation in the explicit form

Switch.

In any case, the first m terms of the sequence of the approximate values ​​to be determined by another method, in the simplest case is extrapolated linearly,

These values ​​can be generally obtained by any one-step process for the first value, a maximum of 2 step process for the second value, and so on until the value by a maximum of ( m-1) -step process. This calculation is also called start-up bill for the multi-step process.

Analysis

A linear multi-step process is convergent if it is consistent and stable for the equation (this property is also called 0 - stability). Convergence implies that the difference between approximate and the exact solution for fixed value for each t can be kept arbitrarily small by decreasing the step size.

Consistency

Be arbitrary, x defined in a neighborhood of a point and once continuously differentiable function. This complies with the trivial differential equation. For this the first order of the multi- step process error can be used as

Be determined. We define then:

A LMV is called consistent if

For arbitrary choices of x and of y. It is called consistent of order p if in Landau notation

Applies, that is, is always limited to the top.

We checked this with the help of the Taylor expansion. Thus, for a p- times differentiable differential equation, the solution p 1 times differentiable and it holds

Wherein the L- th derivative of the position designated. This is carried through for all terms occurring in the LMV and puts this into. It is sufficient to examine this to the exponential function and its differential equation.

Stability

One defines two so-called associated polynomials

A LMV is completely characterized by these two polynomials, so that one speaks instead of the above notation of the linear multistep method, by a " LMV ()".

Be a zero of. A LMV () is zero-stable if for any zeros:

  • It lies either in the interior of the unit circle, or
  • On the edge of the unit circle, in which case they must be a simple zero. A more general case is discussed in the article stability function.

Regarding the A- stability is considered the second Dahlquist barrier that an A - stable linear multistep method can not have more than two order.

Examples

Explicit methods

An explicit method in this context means that for calculating the approximate values ​​only values ​​are used which are to be computed prior to the time. Probably the best known explicit LMV is the s 1- step Adams - Bashforth method ( after John Couch Adams and Francis Bashforth ). This has the form:

With

Eg

Etc.

Implicit methods

In implicit methods and the value to be calculated itself is used for the calculation. In the example as dips on both sides of the equation. A well-known class of implicit multistep methods are the Adams - Moulton method ( by Forest Ray Moulton and John Couch Adams). These have the form:

With

Eg

In addition, in particular, the BDF methods for stiff initial value problems in use as these have better stability properties. BDF -2 is A- stable, the other still - stable, from BDF -7 but unstable.

Practice

Starting values

Often there is in practice with problems of the type:

To do. There is a lack of start values ​​. These are obtained by first -step procedure (for example, the classical Runge- Kutta method ).

Predictor-corrector method

With the thought that to use in comparison to one higher order of consistency of the implicit LMVs bypasses one solving the nonlinear equations by the so-called predictor-corrector method. The value needed in the implicit method is calculated for an explicit method, which is attempted by iteration, the value for to improve. There are various methods commonly:

When (P = predict, E = evaluate, C = correct ) the value obtained by the explicit Prädiktorverfahren is used for back in the implicit corrector method, yielding. A new value for, that receives This is as long iterated until less than a specified error tolerance, or is iterated m times.

Stiff equation
29161
de