2.8. Multi-step and multi-stage methods

Multi-stage methods approximate the slope in multiple stages but still depend on only one point managing to increase the accuracy but increasing heavily the computational cost. A multi-step method uses more than one point to approximate the slope.

Multi-step method: Adams-Bashfort

A well-known explicit method is the two-step Adams-Bashforth method:

\[y_{i+1} = y_i + \frac{\Delta t}{2}\left(3 f(y_i) - f(y_{i-1})\right)\]

It can be derived using TSE applied at multiple points. As you might guess by now, the more points used, the more accurate the solution will be. A problem arises at the very beginning of the solution. The explicit method above requires to solve \(y_{i+1}\) that \(y_i\) and \(y_{i-1}\) are known. That is fine at step \(y_2\) because \(y_1\) and \(y_0\) would already have been computed but what happens when you compute \(y_1\)? Then a point will be missing. That is why this multi-step methods are considered to not be self-starting. This method and also what happens when you compute \(y_1\) is shown in the figure below.

Fig. 2.14 Illustrating the Adams-Bashfort method

Multi-step methods require an initialization. Either a method that requires less points is applied at the beginning (with the disadvantage that the order of error is not consistent throughout the solution) or another method is applied, one that has the same accuracy as the multi-step method but that depends on less points. This is where multi-stage methods are used. The most well-known of their kind are the Runge-Kutta methods.

There are also multi-step methods that are implicit! The most well-known are called Adams-Moulton.

Multi-stage methods: examples

Runge-Kutta

A widely used family of multi-stage methods for initial value problems are the Runge-Kutte methods. The “classical” 4th-order explicit Runge-Kutta (RK4) method has four stages and the whole process only uses one single point:

\[y_{i+1} = y_i + \frac{\Delta t}{6}(k_1+2k_2+2k_3+k_4) + \mathcal{O}(\Delta t^5) \]

The coefficients \(k\) are calculated using:

\[\begin{split}\begin{cases} k_1 = f(y_i)&\\ k_2 = f(y_{i+1/2}^\ast) \quad &\text{with} \quad y_{i+1/2}^\ast=y_i+\frac{\Delta t}{2}k_1 \\ k_3 = f(y_{i+1/2}^{\ast\ast}) \quad &\text{with} \quad y_{i+1/2}^{\ast\ast}=y_i+\frac{\Delta t}{2}k_2 \\ k_4 = f(y_{i+1}^\ast) \quad &\text{with} \quad y_{i+1}^\ast=y_i+\Delta t \text{ } k_3 \\ \end{cases}\end{split}\]

Fig. 2.15 Schematic representation of the Forward Euler method (on the left) and the Runge-Kutta 4 scheme (on the right)

Exercise

Consider the following initial value problem:

\[\frac{dy}{dt} = -y\]

\[y(0) = y_0 = 1\]

What is the value of \(y_1\), using the RK4 method and a time step of \(\Delta t = 0.2\)?

Solution

First, compute the coefficients \(k_1\) to \(k_4\):

\[k_1 = -y_0 = -1 \Rightarrow y_{1/2}^\ast= 1 + \frac{0.2}{2} (-1) = 0.9\]

\[k_2 = -y_{1/2}^\ast = -0.9 \Rightarrow y_{1/2}^{\ast\ast} = 1 + \frac{0.2}{2} (-0.9) = 0.91\]

\[k_3 = -y_{1/2}^{\ast\ast} = -0.91 \Rightarrow y_1^\ast = 1 + 0.2 (-0.91) = 0.818\]

\[k_4 = -y_1^\ast = -0.818\]

Now, we plug the coefficients into the formula for \(y_{i+1}\):

\[y_1 = 1 + \frac{0.2}{6}(-1 - 2 \cdot 0.9 - 2 \cdot 0.91 -0.818) = 0.8187\bar{3}\]

Compare this to the true solution \(y(t) = y_0 \exp(-t)\) for \(t=0.2\):

\[y(0.2) = \exp(-0.2) = 0.8187307\ldots\]

The approximation with the fourth order Runge-Kutta scheme is very accurate!

Heun’s method

A simpler Runge-Kutta scheme is Heun’s method, which is basically a 2-stage Runge-Kutta (RK2) method.

\[y_{i+1} = y_i + \frac{\Delta t}{2}(k_1+k_2) + \mathcal{O}(\Delta t^3) \]

The coefficients \(k_j\) are calculated using:

\[\begin{split}\begin{cases} k_1 &= f(y_i) \\ k_2 &= f(y_{i+1}^\ast) \quad\text{with} \quad y_{i+1}^\ast=y_i+\Delta t \, k_1 \\ \end{cases}\end{split}\]

Advantages of each method

Multi-step methods are easier to implement, computationally more efficient and stabler, allowing the use of larger time steps. Multi-stage methods require less points but are computationally expensive.

Regardless, each method has its advantages and is generally employed based on a desired accuracy or computational efficiency. The choice, however, can often be complicated and requires thorough knowledge of the underlying mathematics. The RK4 and Adams-Bashfort method have to comply with stability criteria, just as expected from any explicit method.

Attribution

This chapter is written by Jaime Arriaga Garcia, Anna Störiko, Justin Pittman and Robert Lanzafame. Find out more here.