Numerical method for solving ordinary differential equations
The backward differentiation formula (BDF) 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 time points, thereby increasing the accuracy of the approximation. These methods are especially used for the solution of
stiff differential equations. The methods were first introduced by
Charles F. Curtiss and
Joseph O. Hirschfelder in 1952.
[1] In 1967 the field was formalized by
C. William Gear in a seminal paper based on his earlier unpublished work.
[2]
General formula
A BDF is used to solve the initial value problem
![{\displaystyle y'=f(t,y),\quad y(t_{0})=y_{0}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/efd412048e03327a10228cf471e1b3cb964dfc3b)
The general formula for a BDF can be written as [3]
![{\displaystyle \sum _{k=0}^{s}a_{k}y_{n+k}=h\beta f(t_{n+s},y_{n+s}),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/96a48684c0195f0dd841c1d2e556c3637bef6d0e)
where
denotes the step size and
. Since
is evaluated for the unknown
, BDF methods are implicit and possibly require the solution of nonlinear equations at each step. The coefficients
and
are chosen so that the method achieves order
, which is the maximum possible.
Derivation of the coefficients
Starting from the formula
one approximates
and
, where
is the Lagrange interpolation polynomial for the points
. Using that
and multiplying by
one arrives at the BDF method of order
.
Specific formulas
The s-step BDFs with s < 7 are:[4]
- BDF1:
![{\displaystyle y_{n+1}-y_{n}=hf(t_{n+1},y_{n+1})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d5985a6744966f282d8fa1dce1f7a3e11eaa64d6)
(this is the backward Euler method)
- BDF2:
![{\displaystyle y_{n+2}-{\tfrac {4}{3}}y_{n+1}+{\tfrac {1}{3}}y_{n}={\tfrac {2}{3}}hf(t_{n+2},y_{n+2})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cc6672bd1e850d23b3ef387b91976fc0ef307dde)
- BDF3:
![{\displaystyle y_{n+3}-{\tfrac {18}{11}}y_{n+2}+{\tfrac {9}{11}}y_{n+1}-{\tfrac {2}{11}}y_{n}={\tfrac {6}{11}}hf(t_{n+3},y_{n+3})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c9cd315c0d5f6a6f32618898b6a9f19a146ed3db)
- BDF4:
![{\displaystyle y_{n+4}-{\tfrac {48}{25}}y_{n+3}+{\tfrac {36}{25}}y_{n+2}-{\tfrac {16}{25}}y_{n+1}+{\tfrac {3}{25}}y_{n}={\tfrac {12}{25}}hf(t_{n+4},y_{n+4})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f94496f0a3f055276e34fa0c4d9710b1ca63e535)
- BDF5:
![{\displaystyle y_{n+5}-{\tfrac {300}{137}}y_{n+4}+{\tfrac {300}{137}}y_{n+3}-{\tfrac {200}{137}}y_{n+2}+{\tfrac {75}{137}}y_{n+1}-{\tfrac {12}{137}}y_{n}={\tfrac {60}{137}}hf(t_{n+5},y_{n+5})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/28c269d2da3bb6bafb63b0bf766467546c8d5b25)
- BDF6:
![{\displaystyle y_{n+6}-{\tfrac {360}{147}}y_{n+5}+{\tfrac {450}{147}}y_{n+4}-{\tfrac {400}{147}}y_{n+3}+{\tfrac {225}{147}}y_{n+2}-{\tfrac {72}{147}}y_{n+1}+{\tfrac {10}{147}}y_{n}={\tfrac {60}{147}}hf(t_{n+6},y_{n+6})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7176fc6ff2e11064ef53bd91f74c303de30875ca)
Methods with s > 6 are not
zero-stable so they cannot be used.
[5]
Stability
The stability of numerical methods for solving stiff equations is indicated by their region of absolute stability. For the BDF methods, these regions are shown in the plots below.
Ideally, the region contains the left half of the complex plane, in which case the method is said to be A-stable. However, linear multistep methods with an order greater than 2 cannot be A-stable. The stability region of the higher-order BDF methods contain a large part of the left half-plane and in particular the whole of the negative real axis. The BDF methods are the most efficient linear multistep methods of this kind.[5]
The pink region shows the stability region of the BDF methods
-
BDF1
-
BDF2
-
BDF3
-
BDF4
-
BDF5
-
BDF6
References
Citations
- ^ Curtiss, C. F., & Hirschfelder, J. O. (1952). Integration of stiff equations. Proceedings of the National Academy of Sciences, 38(3), 235-243.
- .
- ^ Ascher & Petzold 1998, §5.1.2, p. 129
- ^ Iserles 1996, p. 27 (for s = 1, 2, 3); Süli & Mayers 2003, p. 349 (for all s)
- ^ a b Süli & Mayers 2003, p. 349
Referred works
Further reading
- BDF Methods at the SUNDIALS wiki (SUNDIALS is a library implementing BDF methods and similar algorithms).