Multistep Methods

Runge–Kutta methods spend several evaluations of $f$ per step and then forget them. Multistep methods keep the slopes from earlier steps and reuse them, so each step needs only one new evaluation of $f$. Their accuracy is measured just as in Local and Global Error.

The two-step Adams–Bashforth method (AB2) is $$y_{n+1} = y_n + \frac{h}{2}\big(3f_n - f_{n-1}\big),\qquad f_k = f(t_k, y_k).$$

Key idea

Adams–Bashforth methods integrate a polynomial through earlier slopes. The $k$-step method has order $k$ and uses one new $f$ value per step, but it needs $k - 1$ extra starting values, which a one-step method (such as RK4) must supply.

Why it works

Exactly, $y(t_{n+1}) = y(t_n) + \int_{t_n}^{t_{n+1}}f(t, y(t))\,dt$. Replace $f$ by the line through $(t_{n-1}, f_{n-1})$ and $(t_n, f_n)$ and integrate it over $[t_n, t_{n+1}]$: the line has value $f_n$ at $t_n$ and $f_n + (f_n - f_{n-1})$ at $t_{n+1}$, so its average over the step is $\frac{3f_n - f_{n-1}}{2}$. The interpolation error is $O(h^{2})$, which gives local error $O(h^{3})$ and global error $O(h^{2})$. Using more past slopes gives higher order in the same way.

Worked example: Two steps of AB2

Solve $y' = -2y$, $y(0) = 1$ with $h = 0.1$, taking the exact value $y_1 = e^{-0.2} = 0.818731$ as the starting value. Find $y_2$.

$f_0 = -2(1) = -2$ and $f_1 = -2(0.818731) = -1.637462$.
$y_2 = 0.818731 + 0.05\big(3(-1.637462) - (-2)\big) = 0.818731 - 0.145619 = 0.673112$.
Exact: $e^{-0.4} = 0.670320$. Error $0.0028$, from one new evaluation of $f$.

Answer: $0.673112$

Worked example: Counting the work

Compare the evaluations of $f$ for 1000 steps of RK4 and of AB4 (started with 3 RK4 steps).

RK4: 4 per step, $4000$.
AB4: $3 \times 4 = 12$ to start, then $997$ steps with one new value each: $1009$.
Both have order 4; AB4 does about a quarter of the work, which matters when $f$ is expensive.

Answer: $4000$ versus $1009$

Worked example: Why it cannot start alone

Why can AB2 not compute $y_1$ from $y_0$?

The formula for $y_1$ would need $f_0$ and $f_{-1}$, a slope at $t_{-1}$, before the problem even starts.
So $y_1$ comes from a one-step method of matching accuracy, such as Heun's (order 2) for AB2, or RK4 for AB4. After that the formula runs on its own.

Answer: it needs a slope from before t₀

Global error at t = 1 for y′ = −2y with two Adams–Bashforth methods. Starting values that are not accurate enough drag AB3 down to order 2.

Multistep methods have costs of their own. Changing the step size is awkward, because the stored slopes sit at the old spacing. Their stability regions are smaller than those of Runge–Kutta methods of the same order, so they suit non-stiff problems; implicit relatives (Adams–Moulton and the backward differentiation formulas) are the standard tools for stiff ones.

Common mistake

Trying to take the first step with the two-step formula before there is an earlier slope to use. There is no $f_{-1}$; inventing one (say, setting it equal to $f_0$) quietly turns the first step into a different method. The starting values must be as accurate as the method itself: AB4 needs them accurate to order $h^{4}$, and starting it with Euler steps (each with error of order $h^{2}$) drags the whole computation down to order 2. Check: name the method that made each starting value, and its order.

Multistep Methods

Practice

Builds on

Leads to

Sources and further reading