2. Explicit Runge-Kutta Methods

Fig. 2.1 Carl Runge (1856 - 1927)

Fig. 2.2 Martin Kutta (1867 - 1944)

In the previous chapter we saw that Euler’s method is simple to implement but often requires very small step sizes to obtain accurate solutions. Runge-Kutta methods improve accuracy by evaluating the derivative several times within each step and combining these evaluations in a carefully chosen weighted average. They form one of the most important classes of numerical methods for solving ordinary differential equations and are widely used in science and engineering.

The Runge-Kutta method was developed independently by German mathematicians Carl Runge and Martin Kutta in the late 19th century. Runge-Kutta methods are known as single step methods, since we only require values at the current step to advance the solution to the next, as opposed to multistep methods such as the linear multistep methods family of methods that require values from multiple steps to compute the next step.

2.1. General form of a Runge-Kutta method

The key idea of a Runge-Kutta method is that, instead of using a single estimate of the derivative as in Euler’s method, several derivative evaluations are computed within each step. These derivative evaluations are called stages.

The general form of a Runge-Kutta method for solving the initial value problem \(y' =f(t,y)\), \(t \in [t_0, t_{\max}]\), \(y(t_0) = y_0\) is

(2.1)\[\begin{split} \begin{align} y_{n+1} &=y_n + h \sum_{i=1}^s b_i k_i,\\ k_i &= f(t_n +c_i h,y_n + h \sum_{j=1}^s a_{ij} k_j ), \end{align} \end{split}\]

where \(k_i\) for \(i = 1,2, \ldots, s\) are the stages which used to calculate \(y_{n+1}\). The coefficient \(c_i\) determines where within the step the derivative is evaluated, while \(a_{ij}\) determines how previous stage values are combined and \(b_i\) determines how the stages are weighted to compute \(y_{n+1}\).

For example, Heun’s method is a 2-stage Runge-Kutta method which is written as

(2.2)\[\begin{split} \begin{align*} y_{n+1} &= y_n + \frac{h}{2}(k_1 + k_2), \\ k_1 &= f(t_n, y_n), \\ k_2 &= f(t_n + h, y_n + h k_1), \\ \end{align*} \end{split}\]

The general form of a 2-stage method is

(2.3)\[\begin{split} \begin{align*} y_{n+1} &= y_n + h (b_1k_1 + b_2 k_2 ), \\ k_1 &= f(t_n + c_1 h, y_n + h(a_{11} k_1 + a_{12} k_2)), \\ k_2 &= f(t_n + c_2 h, y_n + h(a_{21} k_1 + a_{22} k_2)). \end{align*} \end{split}\]

So comparing equations (2.2) and (2.3) we can see that

\[\begin{split} \begin{align*} c_1 &= 0, & a_{11} &= 0, & a_{12} &= 0, \\ c_2 &= 1, & a_{21} &= 1, & a_{22} &= 0, \\ && b_1 &= \frac{1}{2}, & b_2 &= \frac{1}{2}, \\ \end{align*} \end{split}\]

2.1.1. Butcher tableau

Runge-Kutta methods are often summarised in a Butcher tableau named after the New Zealand mathematician John Butcher. A Butcher tableau is a table of values containing the coefficients \(a_{ij}\), \(b_i\) and \(c_i\) for a Runge-Kutta method

\[\begin{split} \begin{align*} \begin{array}{c|cccc} c_1 & a_{11} & a_{12} & \cdots & a_{1s} \\ c_2 & a_{21} & a_{22} & \cdots & a_{2s} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ c_s & a_{s1} & a_{s2} & \cdots & a_{ss} \\ \hline & b_1 & b_2 & \cdots & b_s \end{array} \end{align*} \end{split}\]

For example, the Butcher tableau for the RK2 method in equation (2.2) is

\[\begin{split} \begin{align*} \begin{array}{c|cccc} 0 & \\ 1 & 1 \\ \hline & \frac{1}{2} & \frac{1}{2} \end{array} \end{align*} \end{split}\]

Example 2.1

Determine theButcher tableau corresponding to the following four-stage Runge-Kutta method

\[\begin{split} \begin{align*} y_{n+1} &= y_n + \frac{h}{6}(k_1 + 2k_2 + 2k_3 + k_4), \\ k_1 &= f(t_n, y_n), \\ k_2 &= f(t_n + \tfrac{1}{2} h, y_n + \tfrac{1}{2} h k_1 ), \\ k_3 &= f(t_n + \tfrac{1}{2} h, y_n + \tfrac{1}{2} h k_2 ), \\ k_4 &= f(t_n + h, y_n + h k_3). \end{align*} \end{split}\]

---

Solution

Comparing the Runge-Kutta method above to the general form of a 4-stage Runge-Kutta method we can see that the Butcher tableau is

\[\begin{split} \begin{align*} \begin{array}{c|cc} 0 & 0 & 0 & 0 & 0 \\ \frac{1}{2} & \frac{1}{2} & 0 & 0 & 0 \\ \frac{1}{2} & 0 & \frac{1}{2} & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 \\ \hline & \frac{1}{6} & \frac{1}{3} & \frac{1}{3} & \frac{1}{6} \end{array} \end{align*} \end{split}\]

2.2. Explicit and implicit Runge-Kutta methods

Not all Runge-Kutta methods can be evaluated stage-by-stage. Depending on the coefficient matrix \(A = (a_{ij})\), the stage equations may need to be solved simultaneously. This distinction leads to the classification of Runge-Kutta methods as explicit or implicit.

The stage values for an \(s\)-stage Runge-Kutta method are

\[\begin{split} \begin{align*} k_1 &=f(t_n +c_1 h,y_n +h(a_{11} k_1 +a_{12} k_2 +\cdots +a_{1s} k_s )),\\ k_2 &=f(t_n +c_2 h,y_n +h(a_{21} k_1 +a_{22} k_2 +\cdots +a_{2s} k_s )),\\ &\vdots \\ k_s &=f(t_n +c_s h,y_n +h(a_{s1} k_1 +a_{s2} k_s +\cdots +a_{ss} k_s )). \end{align*} \end{split}\]

In the first equation we are calculating \(k_1\) includes \(k_1\) on the right-hand side and in the second equation we are calculating \(k_2\) includes \(k_2\) on the right-hand side and so on. These are examples of implicit functions and Runge-Kutta methods where the stage values are expressed using implicit functions are known as Implicit Runge-Kutta (IRK) methods. To calculate the solution of the stage values of an IRK method involves solving a system of equations (see Implicit Runge-Kutta Methods).

If the summation in the stage value \(k_i\) in equation (2.1) is altered so the upper limit to the sum is \(i-1\), i.e.,

\[ \begin{align*} k_i = f(t_n + c_i h,y_n + h\sum_{j=1}^{i-1} a_{ij} k_j) \end{align*} \]

and let \(c_1 = 0\) then we have the following equations for calculating the stage values

\[\begin{split} \begin{align*} k_1 &=f(t_n ,y_n),\\ k_2 &=f(t_n +c_2 h,y_n +ha_{21} k_1 ),\\ k_3 &=f(t_n +c_3 h,y_n +h(a_{31} k_1 +a_{32} k_2 )),\\ &\vdots \\ k_s &=f(t_n +c_s h,y_n +h(a_{s1} k_1 +a_{s2} k_2 +\cdots +a_{s,s-1} k_{s-1} )). \end{align*} \end{split}\]

These stage values are explicit functions where the subject of the equation does not appear on the right-hand side. Runge-Kutta methods where the stages values are calculated using explicit functions are known as Explicit Runge Kutta (ERK) methods. These are easier to compute than implicit Runge-Kutta methods because the stage values can be calculated sequentially in order, i.e., \(k_1\) can be calculated using \(t_n\) and \(y_n\); \(k_1\) is then used to compute \(k_2\); \(k_1\) and \(k_2\) are then used to compute \(k_3\) and so on. However for some ODEs explicit methods require a very small value for the step length and and we must then use implicit methods (see the chapter on stability for more details).

Explicit and implicit Runge-Kutta methods can be easily distinguished by looking at their Butcher tableaux. An explicit method satisfies

\[ a_{ij} = 0, \qquad j \ge 1, \]

so the coefficient matrix \(A\) is strictly lower triangular, whereas an implicit method will have at least one non-zero element in the upper triangular region or main diagonal.

Explicit Runge-Kutta method

\[\begin{split} \begin{array}{c|ccccc} 0 & 0 & & & & \\ c_2 & a_{21} & & & & \\ c_3 & a_{31} & a_{32} & & & \\ \vdots & \vdots & \vdots & \ddots & & \\ c_s & a_{s1} & a_{s2} & \cdots & a_{s,s-1} & \\ \hline & b_1 & b_2 & \cdots & b_{s-1} & b_s \end{array} \end{split}\]

Implicit Runge-Kutta method

\[\begin{split} \begin{array}{c|ccccc} c_1 & a_{11} & a_{12} & a_{13} & \cdots & a_{1s} \\ c_2 & a_{21} & a_{22} & a_{23} & \cdots & a_{2s} \\ c_3 & a_{31} & a_{32} & a_{33} & \cdots & a_{3s} \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ c_s & a_{s1} & a_{s2} & a_{s3} & \cdots & a_{ss} \\ \hline & b_1 & b_2 & b_3 & \cdots & b_s \end{array} \end{split}\]