User:Wolfrock/BDF

Warning: This is my working draft for revisions to the BDF article. Ideally, I would just make the changes there but it will take more than I have at one time to complete this so I'm trying to do it here...

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 times, thereby increasing the accuracy of the approximation. These methods are especially used for the solution of stiff differential equations.

History

Backward Differentiation Formulas (BDFs) were first introduced in 1953 by Curtiss and Hirschfelder. The motivation for BDFs came from stiff equations.

TODO: Elaborate on Motivation.

TODO: Stiff decay property?

Gear was the first to propose a general method for solving DAEs, which was based on BDFs.

Formulation

A BDF is used to solve the initial value problem

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

BDFs are a kind of linear multistep method. The general formula for a linear mulitistep method can be written as (cite something here)

${\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 the coefficients $a_{0},\ldots ,a_{s-1}$ and $b_{0},\ldots ,b_{s}$ determine the particular linear multistep method. BDFs are a particular family of linear multistep method in which $f(t,y)$ is evaluated only at $(t_{n},y_{n})$, or, in other words, $b_{i}=0$ for $i>0$. BDFs solve the initial value problem by differentiating the polynomial that interpolates the previous values of $y$ and setting the derivative at $t_{n}$ equal to $f(t_{n},y_{n})$

TODO: perhaps elaborate in words. TODO: emphasize why BDFs are a noteworthy type of LMM.

A BDF can be written as

$\sum _{i=0}^{k}a_{i}y_{n-i}=hb_{0}f(t_{n},y_{n})$

where....

BDF methods are implicit and, as such, require the solution of non-linear equations at each step. Typically, a modified Newton's method is used to solve these nonlinear equations (Ascher and Petzold).

TODO: ensure notation is consistent with other numerical ODE articles

TODO: explain the notation in this article - it needs to stand alone

TODO: cite things properly.

TODO: starting methods...

Particular BDFs

The simplest BDF is the one-step first-order backward Euler method

$y_{n}-y_{n-1}=hf(t_{n},y_{n})$

BDF methods of orders 2-6

$y_{n}-{\frac {4}{3}}y_{n-1}+{\frac {1}{3}}y_{n-2}={\frac {2}{3}}hf(t_{n},y_{n})$

$y_{n}-{\frac {18}{11}}y_{n-1}+{\frac {9}{11}}y_{n-2}-{\frac {2}{11}}y_{n-3}={\frac {6}{11}}hf(t_{n},y_{n})$

$y_{n}-{\frac {48}{25}}y_{n-1}+{\frac {36}{25}}y_{n-2}-{\frac {16}{25}}y_{n-3}+{\frac {3}{25}}y_{n-4}={\frac {12}{25}}hf(t_{n},y_{n})$

$y_{n}-{\frac {300}{137}}y_{n-1}+{\frac {300}{137}}y_{n-2}-{\frac {200}{137}}y_{n-3}+{\frac {75}{137}}y_{n-4}-{\frac {12}{137}}y_{n-5}={\frac {60}{137}}hf(t_{n},y_{n})$

$y_{n}-{\frac {360}{147}}y_{n-1}+{\frac {450}{147}}y_{n-2}-{\frac {400}{147}}y_{n-3}+{\frac {225}{147}}y_{n-4}-{\frac {72}{147}}y_{n-5}+{\frac {10}{147}}y_{n-6}={\frac {60}{147}}hf(t_{n},y_{n})$

TODO: Elaborate on where these coefficients come from.

TODO: Double check the above.

TODO: Why is BE so small?

BDF methods are stable for k > 6 - cite Hairer.

BDF code

Some popular BDF codes.

• DASSEL
• LSODI
• ode15s (depending on an option)

I think COMSOL uses it as well (based on DASSEL?)

Citations

TODO: Fix citations so they link properly.

References

• U.M. Ascher, L.R. Petzold. Computer Methods for Ordinary Differential Equations and Differential-Algebraic Equations. SIAM, Philadelphia. ISBN 0-89871-412-5
• K. E. Brennen, S. L. Campbell, L. R. Petzold Numerical solution of initial-value problems in differential-algebraic equations. Philadelphia: SIAM, 1995. ISBN 0-89871-353-6
• Ernst Hairer, Syvert Paul Nørsett, and Gerhard Wanner. Solving ordinary differential equations I: Nonstiff problems, second edition. Berlin: Springer Verlag, 1993. ISBN 3-540-56670-8.