Backward Differentiation Formulas (BDF's)

Multi-step methods built with superior stability properties.

Construction: $P_p(x)\equiv$ polynomial of degree $\le p$ that interpolates $Y(x)$ at $x_{n+1},x_n,\ldots x_{n-p+1}$ for some $p\ge 1$:

$$P_p(x)=\sum^{p-1}_{j=-1}Y(x_{n-j})\ell_{j,n}(x)$$ (55)

where

$$\ell_{j,n}(x)=\prod^{n-p+1}_{j=n+1 \atop j\ne 1}\frac{x- x_j}{x_i-x_j}\qquad n+1\le i\le n-p+1$$

Lagrange interpolation basis functions, for nodes $x_{n+1}\dots x_{n-p+1}$ differentiate

$$P'_p(x_{n+1})\approx Y'(x_{n+1})=f(x_{n+1},Y(x_{n+1}))$$ (56)

Combine (55) and (56):

$$Y_{n+1}\approx\sum^{p-1}_{j=0}\alpha_jY(x_{n-j})+h\beta f(x_{n+1}, Y_{n+1})$$

$\therefore$ $p$-step method is

$$y_{n+1}=\sum^{p-1}_{j=0}\alpha_jy_{n-j}+h\beta f(x_{n+1},y_{n+1})$$

Can find coefficients $\alpha_j,\beta$ for given $p$ in many numerical analysis books.

Truncation error for the method:

$$T_n(Y)=-\frac{\beta}{p+1}h^{p+1}Y^{(p+1)}(\xi_n)x_{n-p+1}\le\xi_n \le x_{n+1}$$

Exercise: derive truncation formula (hint, review Lagrange Interpolation).

Example:

$p=1$     $\beta=1\quad \alpha_0=1$ get Implicit Euler
$p=2$     $y_{n+2}-\displaystyle \frac43 y_{n+1}+\frac{1}{3}y_n=\frac{2}{3} hf(x_{n+2} Y_{n+2})$
$p=3$     $y_{n+3}-\displaystyle \frac{18}{11}y_{n+2}+\frac{9}{11}y_{n+1}-\frac{2}{11} y_n=\frac{6}{11}hf(x_{n+3}, y_{n+3})$

$\Box$