---

Categories: Mathematics, Numerical methods.

Runge-Kutta method

A Runge-Kutta method (RKM) is a popular approach to numerically solving systems of ordinary differential equations. Let $\vb{x}(t)$ be the vector we want to find, governed by $\vb{f}(t, \vb{x})$:

$$\begin{aligned} \vb{x}'(t) = \vb{f}\big(t, \vb{x}(t)\big) \end{aligned}$$

Like in all numerical methods, the $t$-axis is split into discrete steps. If a step has size $h$, then as long as $h$ is small enough, we can make the following approximation:

$$\begin{aligned} \vb{x}'(t) + a h \vb{x}''(t) &\approx \vb{x}'(t \!+\! a h) \\ &\approx \vb{f}\big(t \!+\! a h,\, \vb{x}(t \!+\! a h)\big) \\ &\approx \vb{f}\big(t \!+\! a h,\, \vb{x}(t) \!+\! a h \vb{x}'(t) \big) \end{aligned}$$

For sufficiently small $h$, higher-order derivates can also be included, albeit still at $t \!+\! a h$:

$$\begin{aligned} \vb{x}'(t) + a h \vb{x}''(t) + b h^2 \vb{x}'''(t) &\approx \vb{f}\big(t \!+\! a h,\, \vb{x}(t) \!+\! a h \vb{x}'(t) \!+\! b h^2 \vb{x}''(t) \big) \end{aligned}$$

Although these approximations might seem innocent, they actually make it quite complicated to determine the error order of a given RKM.

Now, consider a Taylor expansion around the current $t$, truncated at a chosen order $n$:

$$\begin{aligned} \vb{x}(t \!+\! h) &= \vb{x}(t) + h \vb{x}'(t) + \frac{h^2}{2} \vb{x}''(t) + \frac{h^3}{6} \vb{x}'''(t) + \:...\, + \frac{h^n}{n!} \vb{x}^{(n)}(t) \\ &= \vb{x}(t) + h \bigg[ \vb{x}'(t) + \frac{h}{2} \vb{x}''(t) + \frac{h^2}{6} \vb{x}'''(t) + \:...\, + \frac{h^{n-1}}{n!} \vb{x}^{(n)}(t) \bigg] \end{aligned}$$

We are free to split the terms as follows, choosing real factors $\omega_{mj}$ subject to $\sum_{j} \omega_{mj} = 1$:

$$\begin{aligned} \vb{x}(t \!+\! h) &= \vb{x} + h \bigg[ \sum_{j = 1}^{N_1} \omega_{1j} \, \vb{x}' + \frac{h}{2} \sum_{j = 1}^{N_2} \omega_{2j} \, \vb{x}'' + \:...\, + \frac{h^{n-1}}{n!} \sum_{j = 1}^{N_n} \omega_{nj} \, \vb{x}^{(n)} \bigg] \end{aligned}$$

Where the integers $N_1,...,N_n$ are also free to choose, but for reasons that will become clear later, the most general choice for an RKM is $N_1 = n$, $N_n = 1$, and:

$$\begin{aligned} N_{n-1} = N_n \!+\! 2 ,\quad \cdots ,\quad N_{n-m} = N_{n-m+1} \!+\! m \!+\! 1 ,\quad \cdots ,\quad N_{2} = N_3 \!+\! n \!-\! 1 \end{aligned}$$

In other words, $N_{n-m}$ is the $m$th triangular number. This is not so important, since this is not a practical way to describe RKMs, but it is helpful to understand how they work.

Example derivation

For example, let us truncate at $n = 3$, such that $N_1 = 3$, $N_2 = 3$ and $N_3 = 1$. The following derivation is very general, except it requires all $\alpha_j \neq 0$. Renaming $\omega_{mj}$, we start from:

$$\begin{aligned} \vb{x}(t \!+\! h) &= \vb{x} + h \bigg[ (\alpha_1 + \alpha_2 + \alpha_3) \, \vb{x}' + \frac{h}{2} (\beta_2 + \beta_{31} + \beta_{32}) \, \vb{x}'' + \frac{h^2}{6} \gamma_3 \, \vb{x}''' \bigg] \\ &= \vb{x} + h \bigg[ \alpha_1 \vb{x}' + \Big( \alpha_2 \vb{x}' + \frac{h}{2} \beta_2 \vb{x}'' \Big) + \Big( \alpha_3 \vb{x}' + \frac{h}{2} (\beta_{31} + \beta_{32}) \vb{x}'' + \frac{h^2}{6} \gamma_3 \vb{x}''' \Big) \bigg] \end{aligned}$$

As discussed earlier, the parenthesized expressions can be approximately rewritten with $\vb{f}$:

$$\begin{aligned} \vb{x}(t \!+\! h) = \vb{x} + h &\bigg[ \alpha_1 \vb{f}(t, \vb{x}) + \alpha_2 \vb{f}\Big( t \!+\! \frac{h \beta_2}{2 \alpha_2}, \; \vb{x} \!+\! \frac{h \beta_2}{2 \alpha_2} \vb{x}' \Big) \\ & + \alpha_3 \vb{f}\Big( t \!+\! \frac{h (\beta_{31} \!\!+\!\! \beta_{32})}{2 \alpha_3}, \; \vb{x} \!+\! \frac{h \beta_{31}}{2 \alpha_3} \vb{x}' \!+\! \frac{h \beta_{32}}{2 \alpha_3} \vb{x}' \!+\! \frac{h^2 \gamma_3}{6 \alpha_3} \vb{x}'' \Big) \bigg] \\ = \vb{x} + h &\bigg[ \alpha_1 \vb{k}_1 + \alpha_2 \vb{f}\Big( t \!+\! \frac{h \beta_2}{2 \alpha_2}, \; \vb{x} \!+\! \frac{h \beta_2}{2 \alpha_2} \vb{k}_1 \!\Big) \\ & + \alpha_3 \vb{f}\Big( t \!+\! \frac{h (\beta_{31} \!\!+\!\! \beta_{32})}{2 \alpha_3}, \; \vb{x} \!+\! \frac{h \beta_{31}}{2 \alpha_3} \vb{k}_1 \!+\! \frac{h \beta_{32}}{2 \alpha_3} \vb{f}\Big( t \!+\! \frac{h \gamma_3}{3 \beta_{32}}, \; \vb{x} \!+\! \frac{h \gamma_3}{3 \beta_{32}} \vb{k}_1 \!\Big) \!\Big) \bigg] \end{aligned}$$

Here, we can see an opportunity to save some computational time by reusing an evaluation of $\vb{f}$. Technically, this is optional, but it would be madness not to, so we choose:

$$\begin{aligned} \frac{\beta_2}{2 \alpha_2} = \frac{\gamma_3}{3 \beta_{32}} \end{aligned}$$

Such that the next step of $\vb{x}$’s numerical solution is as follows, recalling that $\sum_{j} \alpha_j = 1$:

$$\begin{aligned} \boxed{ \vb{x}(t \!+\! h) = \vb{x}(t) + h \Big( \alpha_1 \vb{k}_1 + \alpha_2 \vb{k}_2 + \alpha_3 \vb{k}_3 \Big) } \end{aligned}$$

Where $\vb{k}_1$, $\vb{k}_2$ and $\vb{k}_3$ are different estimates of the average slope $\vb{x}'$ between $t$ and $t \!+\! h$, whose weighted average is used to make the $t$-step. They are given by:

$$\begin{aligned} \boxed{ \begin{aligned} \vb{k}_1 &\equiv \vb{f}(t, \vb{x}) \\ \vb{k}_2 &\equiv \vb{f}\bigg( t + \frac{h \beta_2}{2 \alpha_2}, \; \vb{x} + \frac{h \beta_2}{2 \alpha_2} \vb{k}_1 \bigg) \\ \vb{k}_3 &\equiv \vb{f}\bigg( t + \frac{h (\beta_{31} \!\!+\!\! \beta_{32})}{2 \alpha_3}, \; \vb{x} + \frac{h \beta_{31}}{2 \alpha_3} \vb{k}_1 + \frac{h \beta_{32}}{2 \alpha_3} \vb{k}_2 \bigg) \end{aligned} } \end{aligned}$$

Despite the contraints on $\alpha_j$ and $\beta_j$, there is an enormous freedom of choice here, all leading to valid RKMs, although not necessarily good ones.

General form

A more practical description goes as follows: in an $s$-stage RKM, a weighted average is taken of up to $s$ slope estimates $\vb{k}_j$ with weights $b_j$. Let $\sum_{j} b_j = 1$, then:

$$\begin{aligned} \boxed{ \vb{x}(t \!+\! h) = \vb{x}(t) + h \sum_{j = 1}^{s} b_j \vb{k}_j } \end{aligned}$$

Where the estimates $\vb{k}_1, ..., \vb{k}_s$ depend on each other, and are calculated one by one as:

$$\begin{aligned} \boxed{ \vb{k}_m = \vb{f}\bigg( t + h c_m,\; \vb{x} + h \sum_{j = 1}^{m - 1} a_{mj} \vb{k}_j \bigg) } \end{aligned}$$

With $c_1 = 1$ and $\sum_{j = 1} a_{mj} = c_m$. Writing this out for the first few $m$, the pattern is clear:

$$\begin{aligned} \vb{k}_1 &= \vb{f}(t, \vb{x}) \\ \vb{k}_2 &= \vb{f}\big( t + h c_2,\; \vb{x} + h a_{21} \vb{k}_1 \big) \\ \vb{k}_3 &= \vb{f}\big( t + h c_3,\; \vb{x} + h (a_{31} \vb{k}_1 + a_{32} \vb{k}_2) \big) \\ \vb{k}_4 &= \:... \end{aligned}$$

The coefficients of a given RKM are usually compactly represented in a Butcher tableau:

$$\begin{aligned} \begin{array}{c|ccc} 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{aligned}$$

Each RKM has an order $p$, such that the global truncation error is $\mathcal{O}(h^p)$, i.e. the accumulated difference between the numerical and the exact solutions is proportional to $h^p$.

The surprise is that $p$ need not be equal to the Taylor expansion order $n$, nor the stage count $s$. Typically, $s = n$ for computational efficiency, but $s \ge n$ is possible in theory.

The order $p$ of a given RKM is determined by a complicated set of equations on the coefficients, and the lowest possible $s$ for a desired $p$ is in fact only partially known. For $p \le 4$ the bound is $s \ge p$, whereas for $p \ge 5$ the only proven bound is $s \ge p \!+\! 1$, but for $p \ge 7$ no such efficient methods have been found so far.

If you need an RKM with a certain order, look it up. There exist many efficient methods for $p \le 4$ where $s = p$, and although less popular, higher $p$ are also available.

References

1. J.C. Butcher, Numerical methods for ordinary differential equations, 3rd edition, Wiley.

---