Multi-step methods

We further consider some methods that estimate the slope $y'(t+ch)$ by points in addition to the two end points $y'(t)$ and $y'(t+h)$.

The Adams-Bashforth methods

Here we consider the multi-step methods for approximating $y'(t+ch)$ at some point inside the interval $[t,\;t+h]$ as a linear interpolation between the two end points $y'(t)$ and $y'(t+h)$. Specifically, the derivative $y'(t)$ as a function of time $t$ can be approximated by Lagrange interpolation:

$$y'(t) \approx \hat{y'}(t)=\frac{t-t_{n+1}}{t_n-t_{n+1}}y'(t_n) +\frac{t-t_n}{t_{n+1}-t_n}y'(t_{n+1})$$

$$= \frac{t_{n+1}-t}{h}f(t_n,y(t_n))+\frac{t-t_n}{h}f(t_{n+1},y(t_{n+1}))$$

$$= \frac{t_{n+1}-t}{h}f_n+\frac{t-t_n}{h}f_{n+1}$$ (220)

Now the increment of $y(t)$ from $t_{n+1}$ to $t_{n+2}=t_{n+1}+h$ can be found to be:

$$\Delta y = y(t_{n+2})-y(t_{n+1})=\int_{t_{n+1}}^{t_{n+2}} y'(t)dt \approx \i... ...t_{n+1}}^{t_{n+2}} \left[\frac{t_{n+1}-t}{h}f_n+\frac{t-t_n}{h}f_{n+1}\right]dt$$

$$= \frac{f_n}{h}\int_{t_{n+1}}^{t_{n+1}+h}(t_{n+1}-t)dt +\frac{f_{n+1}}{h}\int_{t_{n+1}}^{t_{n+1}+h}(t-t_n)dt$$

$$= \frac{f_n}{h}\left[ h t_{n+1}-\frac{(t_{n+1}+h)^2+t_{n+1}^2}{2}\right] +\frac{f_{n+1}}{h}\left[ \frac{(t_{n+1}+h)^2-t_{n+1}^2}{2}-h t_n\right]$$

$$= \frac{3h}{2}f_{n+1}-\frac{h}{2}f_{n}$$ (221)

and the iteration can be formed based on two previous steps:

$$y_{n+2}=y_{n+1}+\Delta y=y_{n+1}+h\left(\frac{3}{2}f_{n+1}-\frac{1}{2}f_{n}\right)$$ (222)

This method can be generalized to an mth order multi-step Adams-Bashforth method, which approximates $y'(t)$ as a weighted average of $y'_i=f(t_i,y(t_i))$ ( $i=n,\cdots,n+m-1$) obtained in the previous $m$ steps:

$$y'_{n+m-1}=\sum_{i=n}^{n+m-1} b_i f(t_i,y(t_i)) =\sum_{i=n}^{n+m-1} b_i f(t_i,y(t_i))$$ (223)

based on which the next function value can be obtained as

$$y_{n+m}=y_{n+m-1}+h\;\sum_{i=n}^{n+m-1} b_i f_i =y_{n+m-1}+h\;\sum_{i=n}^{n+m-1} b_i f(t_i,y(t_i))$$ (224)

The specific values of the coefficients $b_i$ can be found in a fashion similar to the case of $m=2$ as shown above, based on the mth order Lagrange interpolation of $m$ previous results $y'_i=f(t_i,y(t_i))$ ( $i=n,\cdots,n+m-1$). Specially, when $m=1$, this becomes forward Euler's method.

In the Adams-Bashforth methods, the slope $y'(t)$ in the interval $(t_{n+m-1} \le t \le t_{n+m})$ is approximated by the previous $m$ points $y'_n,\cdots,y'_{n+m-1}$, excluding $y'_{n+m}$ at $t_{n+m}$, the end point of the current interval. This multi-step methods can be modified to also include the next point $y'_{n+m}=f(t_{n+m},y_{n+m})$ in the summation that approximates $y'(t)$:

$$y_{n+m}=y_{n+m-1}+h\;\sum_{i=n}^{n+m} b_i f_i =y_{n+m-1}+h\;\sum_{i=n}^{n+m} b_i f(t_i,y(t_i))$$ (225)

Note that this iteration becomes implicit as $y_{n+m}$ to be estimated appears on both sides of the equation, which needs to be solved to get $y_{n+m}$. Such methods are called the Adams-Moulton methods. Specially, when $m=0$, this is the backward Euler's method; when $m=1$, this is the trapezoidal method.