### 7.5 Runge–Kutta methods

In the method-of-lines approach one ends up effectively integrating a system of ordinary differential equations, which we now generically denote by
The majority of approaches in numerical relativity use one-step, multi-stage, explicit Runge–Kutta (RK) methods, which take the following form.

Definition 16. An explicit, s-stage, Runge–Kutta method is of the form

with , , and real numbers.

Next we present a few examples, in increasing order of accuracy. The simplest one is a forward finite-difference scheme [cf. Eq. (7.70)].

Example 42. The Euler method (first-order, one-stage):

It corresponds to all the coefficients set to zero except .

Example 43. Second-order, two-stages RK :

The non-vanishing coefficients are .

Example 44. Third-order, four-stages RK:

In the previous case, the number of stages is larger than the order of the scheme. It turns out that it is possible to have a third-order RK scheme with three stages.

Example 45. Third-order, three-stages Heun–RK method

It is also possible to find a fourth-order, four-stages RK scheme. Actually, there are multiple ones, with one and two-dimensional free parameters. A popular choice is

Example 46. The standard fourth-order, four-stages RK method:

At this point it is clear that since the RK methods have the same structure, it is not very efficient to explicitly write down all the stages and the final step. Butcher’s tables are a common way to represent them; they have the following structure:

Table 1: The structure of a Butcher table.
 0 ⋮ ⋮ ⋮ … …

Table 2 shows representations of Examples 42, 43, 44, 45, while Table 3 shows the classical fourth-order Runge–Kutta method of Example 46.

Table 2: From left to right: The Euler method, second and third-order RK, third-order Heun.
 0 1

 0 0 1/2 0 1

 0 1/2 1/2 1 0 1 1 0 0 1 1/6 2/3 0 1/6

 0 1/3 1/3 2/3 0 2/3 1/4 0 3/4

Table 3: The standard fourth-order Runge–Kutta method.
 0 1/2 1/2 1/2 0 1/2 1 0 0 1 1/6 1/3 1/3 1/6

The above examples explicitly show that up to, and including, fourth-order accuracy there are Runge–Kutta methods of order and stages with . It is interesting that even though the first RK methods date back to the end of the 19h century, the question of whether there are higher-order (than four) RK methods remained open until the following result was shown by Butcher in 1963 [93]: cannot be achieved anymore starting with fifth-order accurate schemes, and there are a number of barriers.

Theorem 13. For there are no Runge–Kutta methods with stages.

However, there are fifth and sixth-order RK methods with six and seven stages, respectively. Butcher in 1965 [94] and 1985 [95] respectively showed the following barriers.

Theorem 14. For there are no Runge–Kutta methods with stages.

Theorem 15. For there are no Runge–Kutta methods with stages.

Seventh and eighth-order methods with and stages, respectively, have been constructed, as well as a tenth-order one with stages.

#### 7.5.1 Embedded methods

In practice many approaches in numerical relativity use an adaptive timestep method. One way of doing so is to evolve the system of equations two steps with timestep and one with . The difference in both solutions at can be used, along with Richardson extrapolation, to estimate the new timestep needed to achieve any given tolerance error.

In more detail: if we call the solution at evolved from time in two steps of size , and the solution at the same time advanced from time in one step of size , then the following holds

where denotes the exact solution. Therefore, the term
can be used as an estimate of the error and to choose the next timestep.

Embedded methods also compute two solutions and use their difference to estimate the error and adapt the timestep. However, this is done by reusing the stages. Two Runge–Kutta methods, of order and (in most cases – but not always – or ) are constructed, which share the intermediate function values, so that there is no overhead cost. Therefore, their Butcher table looks as follows:

Table 4: The structure of embedded methods.
 0 ⋮ ⋮ ⋮ … … …

Embedded methods are denoted by , where is the order of the scheme, which advances the solution. For example, a method would be of fifth order, with a fourth-order scheme, which shares its function calls used to estimate the error.

Table 5 shows the coefficients for a popular embedded method, the seven stages Dormand–Prince [146]. Dormand–Prince methods are embedded methods, which minimize a quantification of the truncation error for the highest-order component, which is the one used for the evolution.

Table 5: The Dormand–Prince method.
 0