Multistep methods

In Runge–Kutta methods we start at $u_i$ to find ${u}_{i+1}$, taking multiple $f$-evaluations (stages) to achieve high accuracy. In contrast, multistep methods boost accuracy by employing more of the history of the solution, taking information from the recent past. For the discussion in this and following sections, we introduce the shorthand notation

The quantities $u$ and $f$ in (6.6.2) are shown as scalars, but in general they can be vectors.

In order to use (6.6.2) as a numerical method, we iterate through $i=k-1,\ldots,n-1$. The value $u_0$ is determined by the initial condition, but we also need some way of generating the starting values

In practice the starting values are often found using an RK formula.^[1]

The difference formula (6.6.2) defines ${u}_{i+1}$ in terms of known values of the solution and its derivative from the past. In the explicit case with $b_k=0$, Equation (6.6.2) immediately gives a formula for the unknown quantity ${u}_{i+1}$ in terms of values at time level $t_i$ and earlier. Thus only one new evaluation of $f$ is needed to make a time step, provided that we store the recent history.

For an implicit method, however, $b_k\neq 0$ and (6.6.2) has the form

Now the unknown ${u}_{i+1}$ that we seek appears inside the function $f$. In general this equation is a nonlinear rootfinding problem for ${u}_{i+1}$ and is not solvable in a finite number of steps by a formula. The implementation of both explicit and implicit multistep formulas is discussed in detail in Implementation of multistep methods.

As with RK formulas, a multistep method is entirely specified by the values of a few constants. Table 6.6.1 and Table 6.6.2 present some of the most well-known and important formulas. The Adams–Bashforth (AB) methods are explicit, while Adams–Moulton (AM) and backward differentiation formulas (BD) are implicit. The tables also list the methods’ order of accuracy, to be defined shortly. We adopt the convention of referring to a multistep method by appending its order of accuracy to a two-letter name abbreviation, e.g., the AB3 method.

6.6.1Generating polynomials¶

An alternative description of a multistep method is the generating polynomials

For example, the AB3 method is completely specified by

The connection between the generating polynomials and the numerical method requires a little abstraction. Let $\mathcal{Z}$ be a forward-shift operator, so that, for example, $\mathcal{Z} t_i = t_{i+1}$, $\mathcal{Z}^3 u_{i-1} = u_{i+2}$, and so on. With this, the difference formula (6.6.2) can be written concisely as

6.6.2Truncation and global error¶

The definition of local truncation error is easily extended to multistep methods.

Although we will not present the analysis, the main conclusion for the multistep methods in this section is the same as for one-step methods.

6.6.3Derivation of the formulas¶

Where do coefficients like those in Table 6.6.1 come from? There are different ways to answer that question, but Adams and BD methods have distinctive stories to tell. The derivation of Adams methods begins with the observation that

As a result, a $k$-step Adams method always has $\rho(z)=z^k-z^{k-1}$. While the integrand above is unknown over the interval of integration, we can approximate it by a polynomial interpolant of the historical values of $f$. That polynomial can be integrated analytically, leading to a derivation of the coefficients $b_0,\ldots,b_k$.

In AB methods, the interpolating polynomial has degree $k-1$, which means that its interpolation error is $O(h^k)$. Upon integrating we get a local error of $O(h^{k+1})$, which reduces to a global error of $O(h^k)$. The AM interpolating polynomial is one degree larger, so its order of accuracy is one higher for the same number of steps.

The idea behind backward differentiation formulas is complementary to that for Adams: Interpolate solution values ${u}_{i+1},\ldots,u_{i-k+1}$ by a polynomial $q$, and then, motivated by $f(t,\hat{u})=\hat{u}'(t)$, set

The quantity $q'(t_{i+1})$ can be approximated by a finite difference of the past solution values, leading to the coefficients of $\rho(z)$ and $\sigma(z)=b_k z^k$.

6.6.4Exercises¶

1. ✍ For each method, write out the generating polynomials $\rho(z)$ and $\sigma(z)$.

   (a) AM2, (b) AB2, (c) BD2, (d) AM3, (e) AB3.

2. ✍ Write out by hand an equation that defines the first solution value $u_1$ produced by AM1 (backward Euler) for each IVP. (Reminder: This is an implicit formula.)

   (a) $u' = -2t u, \quad 0 \le t \le 2, \quad u_0 = 2, \quad h = 0.2$

   (b) $u' = u + t, \quad 0 \le t \le 1, \quad u_0 = 2, \quad h = 0.1$

   (c) $(1+x^3)uu' = x^2,\quad 0 \le x \le 3, \quad u_0=1, , \quad h = 0.5$

3. ✍ Do the preceding exercise for AM2 (trapezoid) instead of backward Euler.

4. ✍ For each method, find the leading term in the local truncation error using (6.6.8).

   (a) AM2, (b) AB2, (c) BD2.

5. ✍/ ⌨ For each method, find the leading term in the local truncation error using (6.6.8). (Computer algebra is recommended.)

   (a) AM3, (b) AB3, (c) BD4.

6. ✍ A formula for the quadratic polynomial interpolant through the points $(s_1,y_1)$, $(s_2,y_2)$, and $(s_3,y_3)$ is

   $$p(x) = \frac{(x-s_2)(x-s_3)}{(s_1-s_2)(s_1-s_3)}\,y_1 + \frac{(x-s_1)(x-s_3)}{(s_2-s_1)(s_2-s_3)}\,y_2 + \frac{(x-s_1)(x-s_2)}{(s_3-s_1)(s_3-s_2)}\,y_3.$$

   (6.6.19)

   (a) Use (6.6.13) and a polynomial interpolant through three points to derive the coefficients of the AM3 method.

   (b) Use (6.6.16) and a polynomial interpolant through three points to derive the coefficients of the BD2 method.

7. ✍ By doing series expansion about the point $z=1$, show for BD2 that

   $$\frac{\rho(z)}{\sigma(z)} - \log(z-1) = O\bigl( (z-1)^3 \bigr).$$

   (6.6.20)

8. ✍/ ⌨ By doing series expansion about the point $z=1$, show for AB3 and AM3 that

   $$\frac{\rho(z)}{\sigma(z)} - \log(z-1) = O\bigl( (z-1)^4 \bigr).$$

   (6.6.21)

   (Computer algebra is recommended.)