Backward differentiation formula

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]

General formula

A BDF is used to solve the initial value problem

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

The general formula for a BDF can be written as [2]

\sum _{k=0}^{s}a_{k}y_{n+k}=h\beta f(t_{n+s},y_{n+s}),

where $h$ denotes the step size and $t_{n}=t_{0}+nh$ . Since $f$ is evaluated for the unknown $y_{n+s}$ , BDF methods are implicit and possibly require the solution of nonlinear equations at each step. The coefficients $a_{k}$ and $\beta$ are chosen so that the method achieves order $s$ , which is the maximum possible.

Derivation of the coefficients

Starting from the formula ${\textstyle y'(t_{n+s})=f(t_{n+s},y(t_{n+s}))}$ one approximates $y(t_{n+s})\approx y_{n+s}$ and $y'(t_{n+s})\approx p_{n,s}'(t_{n+s})$ , where $p_{n,s}(t)$ is the Lagrange interpolation polynomial for the points $(t_{n},y_{n}),\ldots ,(t_{n+s},y_{n+s})$ . Using that $t_{n}=t_{0}+nh$ and multiplying by $h$ one arrives at the BDF method of order $s$ .

Specific formulas

The s-step BDFs with s < 7 are:[3]

BDF1: $y_{n+1}-y_{n}=hf(t_{n+1},y_{n+1})$ (this is the backward Euler method)
BDF2: $y_{n+2}-{\tfrac {4}{3}}y_{n+1}+{\tfrac {1}{3}}y_{n}={\tfrac {2}{3}}hf(t_{n+2},y_{n+2})$
BDF3: $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})$
BDF4: $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})$
BDF5: $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})$
BDF6: $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})$

Methods with s > 6 are not zero-stable so they cannot be used.[4]

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.[4]

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)
Süli & Mayers 2003, p. 349

Referred works

Ascher, U. M.; Petzold, L. R. (1998), Computer Methods for Ordinary Differential Equations and Differential-Algebraic Equations, SIAM, Philadelphia, ISBN 0-89871-412-5.
Iserles, Arieh (1996), A First Course in the Numerical Analysis of Differential Equations, Cambridge University Press, ISBN 978-0-521-55655-2.
Süli, Endre; Mayers, David (2003), An Introduction to Numerical Analysis, Cambridge University Press, ISBN 0-521-00794-1.

Numerical methods for integration
First-order methods	Euler method Backward Euler Semi-implicit Euler Exponential Euler
Second-order methods	Verlet integration Velocity Verlet Trapezoidal rule Beeman's algorithm Midpoint method Heun's method Newmark-beta method Leapfrog integration
Higher-order methods	Exponential integrator Runge–Kutta methods List of Runge–Kutta methods Linear multistep method General linear methods Backward differentiation formula Yoshida
Theory	Symplectic integrator