List of Runge–Kutta methods explained

Runge–Kutta methods are methods for the numerical solution of the ordinary differential equation

dy
dt

=f(t,y).

Explicit Runge–Kutta methods take the form

\begin{align} yn+1&=yn+h

s
\sum
i=1

biki\\ k1&=f(tn,yn),\\ k2&=f(tn+c2h,yn+h(a21k1)),\\ k3&=f(tn+c3h,yn+h(a31k1+a32k2)),\\ &  \vdots\\ ki&=f\left(tn+cih,yn+h

i-1
\sum
j=1

aijkj\right). \end{align}

Stages for implicit methods of s stages take the more general form, with the solution to be found over all s

ki=f\left(tn+cih,yn+h

s
\sum
j=1

aijkj\right).

Each method listed on this page is defined by its Butcher tableau, which puts the coefficients of the method in a table as follows:

\begin{array}{c|cccc} c1&a11&a12&...&a1s\\ c2&a21&a22&...&a2s\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ cs&as1&as2&...&ass\\ \hline &b1&b2&...&bs\\ \end{array}

For adaptive and implicit methods, the Butcher tableau is extended to give values of

*
b
i
, and the estimated error is then

en+1=

s
h\sum
i=1

(bi-

*
b
i)

ki

.

Explicit methods

The explicit methods are those where the matrix

[aij]

is lower triangular.

Forward Euler

The Euler method is first order. The lack of stability and accuracy limits its popularity mainly to use as a simple introductory example of a numeric solution method.

\begin{array}{c|c} 0&0\\ \hline &1\\ \end{array}

Explicit midpoint method

The (explicit) midpoint method is a second-order method with two stages (see also the implicit midpoint method below):

\begin{array}{c|cc} 0&0&0\\ 1/2&1/2&0\\ \hline &0&1\\ \end{array}

Heun's method

Heun's method is a second-order method with two stages. It is also known as the explicit trapezoid rule, improved Euler's method, or modified Euler's method:

\begin{array}{c|cc} 0&0&0\\ 1&1&0\\ \hline &1/2&1/2\\ \end{array}

Ralston's method

Ralston's method is a second-order method[1] with two stages and a minimum local error bound:

\begin{array}{c|cc} 0&0&0\\ 2/3&2/3&0\\ \hline &1/4&3/4\\ \end{array}

Generic second-order method

\begin{array}{c|ccc} 0&0&0\\ \alpha&\alpha&0\\ \hline &1-

1
2\alpha

&

1
2\alpha

\\ \end{array}

Kutta's third-order method

\begin{array}{c|ccc} 0&0&0&0\\ 1/2&1/2&0&0\\ 1&-1&2&0\\ \hline &1/6&2/3&1/6\\ \end{array}

Generic third-order method

See Sanderse and Veldman (2019).[2]

for α ≠ 0,, 1:

\begin{array}{c|ccc}0&0&0&0\ \alpha&\alpha&0&0\ 1&1+

1-\alpha
\alpha(3\alpha-2)

&-

1-\alpha
\alpha(3\alpha-2)

&0\ \hline &

1-
2
1
6\alpha

&

1
6\alpha(1-\alpha)

&

2-3\alpha
6(1-\alpha)

\\ \end{array}

Heun's third-order method

\begin{array}{c|ccc} 0&0&0&0\\ 1/3&1/3&0&0\\ 2/3&0&2/3&0\\ \hline &1/4&0&3/4\\ \end{array}

Van der Houwen's/Wray third-order method

\begin{array}{c|ccc} 0&0&0&0\\ 8/15&8/15&0&0\\ 2/3&1/4&5/12&0\\ \hline &1/4&0&3/4\\ \end{array}

Ralston's third-order method

Ralston's third-order method[1] is used in the embedded Bogacki–Shampine method.

\begin{array}{c|ccc} 0&0&0&0\\ 1/2&1/2&0&0\\ 3/4&0&3/4&0\\ \hline &2/9&1/3&4/9\\ \end{array}

Third-order Strong Stability Preserving Runge-Kutta (SSPRK3)

\begin{array}{c|ccc} 0&0&0&0\\ 1&1&0&0\\ 1/2&1/4&1/4&0\\ \hline &1/6&1/6&2/3\\ \end{array}

Classic fourth-order method

The "original" Runge–Kutta method.[3]

\begin{array}{c|cccc} 0&0&0&0&0\\ 1/2&1/2&0&0&0\\ 1/2&0&1/2&0&0\\ 1&0&0&1&0\\ \hline &1/6&1/3&1/3&1/6\\ \end{array}

3/8-rule fourth-order method

This method doesn't have as much notoriety as the "classic" method, but is just as classic because it was proposed in the same paper (Kutta, 1901).

\begin{array}{c|cccc} 0&0&0&0&0\\ 1/3&1/3&0&0&0\\ 2/3&-1/3&1&0&0\\ 1&1&-1&1&0\\hline &1/8&3/8&3/8&1/8\\ \end{array}

Ralston's fourth-order method

This fourth order method[1] has minimum truncation error.

\begin{array}{c|cccc} 0&0&0&0&0\\

2
5

&

2
5

&0&0&0\\

14-3\sqrt{5
} & \frac & \frac & 0 & 0\\1 & \frac & \frac & \frac & 0\\\hline & \frac & \frac & \frac & \frac\\\end

Embedded methods

The embedded methods are designed to produce an estimate of the local truncation error of a single Runge–Kutta step, and as result, allow to control the error with adaptive stepsize. This is done by having two methods in the tableau, one with order p and one with order p-1.

The lower-order step is given by

*
y
n+1

=yn+

s
h\sum
i=1
*
b
i

ki,

where the

ki

are the same as for the higher order method. Then the error is

en+1=yn+1-

*
y
n+1

=

s
h\sum
i=1

(bi-

*
b
i)

ki,

which is

O(hp)

. The Butcher Tableau for this kind of method is extended to give the values of
*
b
i

\begin{array}{c|cccc} c1&a11&a12&...&a1s\\ c2&a21&a22&...&a2s\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ cs&as1&as2&...&ass\\ \hline &b1&b2&...&bs\\ &

*
b
1

&

*
b
2

&...&

*\\ \end{array}
b
s

Heun–Euler

The simplest adaptive Runge–Kutta method involves combining Heun's method, which is order 2, with the Euler method, which is order 1. Its extended Butcher Tableau is:

\begin{array}{c|cc} 0&\\ 1&1\\ \hline & 1/2&1/2\\ & 1& 0 \end{array}

The error estimate is used to control the stepsize.

Fehlberg RK1(2)

The Fehlberg method[4] has two methods of orders 1 and 2. Its extended Butcher Tableau is:

0
1/2 1/2
11/256255/256
1/512255/2561/512
1/256255/2560

The first row of b coefficients gives the second-order accurate solution, and the second row has order one.

Bogacki–Shampine

The Bogacki–Shampine method has two methods of orders 2 and 3. Its extended Butcher Tableau is:

0
1/2 1/2
3/4 0 3/4
1 2/9 1/3 4/9
2/9 1/3 4/9 0
7/24 1/4 1/3 1/8

The first row of b coefficients gives the third-order accurate solution, and the second row has order two.

Fehlberg

The Runge–Kutta–Fehlberg method has two methods of orders 5 and 4; it is sometimes dubbed RKF45 . Its extended Butcher Tableau is:

\begin{array}{r|ccccc} 0&&&&&\\ 1/4&1/4&&&\\ 3/8&3/32&9/32&&\\ 12/13&1932/2197&-7200/2197&7296/2197&\\ 1&439/216&-8&3680/513&-845/4104&\\ 1/2&-8/27&2&-3544/2565&1859/4104&-11/40\\ \hline&16/135&0&6656/12825&28561/56430&-9/50&2/55\\ &25/216&0&1408/2565&2197/4104&-1/5&0 \end{array}

The first row of b coefficients gives the fifth-order accurate solution, and the second row has order four.The coefficients here allow for an adaptive stepsize to be determined automatically.

Cash-Karp

Cash and Karp have modified Fehlberg's original idea. The extended tableau for the Cash–Karp method is

0
1/5 1/5
3/10 3/40 9/40
3/5 3/10 −9/10 6/5
1 −11/54 5/2 −70/27 35/27
7/8 1631/55296 175/512 575/13824 44275/110592 253/4096
37/378 0 250/621 125/594 0 512/1771
2825/27648 0 18575/48384 13525/55296 277/14336 1/4

The first row of b coefficients gives the fifth-order accurate solution, and the second row has order four.

Dormand–Prince

The extended tableau for the Dormand–Prince method is

0
1/5 1/5
3/10 3/40 9/40
4/5 44/45 −56/15 32/9
8/9 19372/6561 −25360/2187 64448/6561 −212/729
1 9017/3168 −355/33 46732/5247 49/176 −5103/18656
1 35/384 0 500/1113 125/192 −2187/6784 11/84
35/384 0 500/1113 125/192 −2187/6784 11/84 0
5179/57600 0 7571/16695 393/640 −92097/339200 187/2100 1/40

The first row of b coefficients gives the fifth-order accurate solution, and the second row gives the fourth-order accurate solution.

Implicit methods

Backward Euler

The backward Euler method is first order. Unconditionally stable and non-oscillatory for linear diffusion problems.

\begin{array}{c|c} 1&1\\ \hline &1\\ \end{array}

Implicit midpoint

The implicit midpoint method is of second order. It is the simplest method in the class of collocation methods known as the Gauss-Legendre methods. It is a symplectic integrator.

\begin{array}{c|c} 1/2&1/2\\ \hline &1 \end{array}

Crank-Nicolson method

The Crank–Nicolson method corresponds to the implicit trapezoidal rule and is a second-order accurate and A-stable method.

\begin{array}{c|cc} 0&0&0\\ 1&1/2&1/2\\ \hline &1/2&1/2\\ \end{array}

Gauss–Legendre methods

These methods are based on the points of Gauss–Legendre quadrature. The Gauss–Legendre method of order four has Butcher tableau:

\begin{array}{c|cc} 1-
2
\sqrt3
6

&

1
4

&

1-
4
\sqrt3\\
6
1+
2
\sqrt3
6

&

1+
4
\sqrt3&
6
1
4

\\ \hline&

1
2

&

1
2

\\ &

12+\sqrt3
2
&
12-\sqrt3
2
\\ \end{array}

The Gauss–Legendre method of order six has Butcher tableau:

\begin{array}{c|ccc} 1
2

-

\sqrt{15
} & \frac & \frac- \frac & \frac - \frac \\\frac & \frac + \frac & \frac & \frac - \frac\\\frac + \frac & \frac + \frac & \frac + \frac & \frac \\\hline & \frac & \frac & \frac \\ & -\frac56 & \frac83 & -\frac56\end

Diagonally Implicit Runge–Kutta methods

Diagonally Implicit Runge–Kutta (DIRK) formulae have been widely used for the numerical solution of stiff initial value problems;[5] the advantage of this approach is that here the solution may be found sequentially as opposed to simultaneously.

The simplest method from this class is the order 2 implicit midpoint method.

Kraaijevanger and Spijker's two-stage Diagonally Implicit Runge–Kutta method:

\begin{array}{c|cc} 1/2&1/2&0\\ 3/2&-1/2&2\\ \hline&-1/2&3/2\\ \end{array}

Qin and Zhang's two-stage, 2nd order, symplectic Diagonally Implicit Runge–Kutta method:

\begin{array}{c|cc} 1/4&1/4&0\\ 3/4&1/2&1/4\\ \hline&1/2&1/2\\ \end{array}

Pareschi and Russo's two-stage 2nd order Diagonally Implicit Runge–Kutta method:

\begin{array}{c|cc} x&x&0\\ 1-x&1-2x&x\\ \hline&

1
2

&

1
2

\\ \end{array}

This Diagonally Implicit Runge–Kutta method is A-stable if and only if x \ge \frac. Moreover, this method is L-stable if and only if

x

equals one of the roots of the polynomial x^2 - 2x + \frac, i.e. if x = 1 \pm \frac.Qin and Zhang's Diagonally Implicit Runge–Kutta method corresponds to Pareschi and Russo's Diagonally Implicit Runge–Kutta method with

x=1/4

.

Two-stage 2nd order Diagonally Implicit Runge–Kutta method:

\begin{array}{c|cc} x&x&0\\ 1&1-x&x\\ \hline&1-x&x\\ \end{array}

Again, this Diagonally Implicit Runge–Kutta method is A-stable if and only if x \ge \frac. As the previous method, this method is again L-stable if and only if

x

equals one of the roots of the polynomial x^2 - 2x + \frac, i.e. if x = 1 \pm \frac. This condition is also necessary for 2nd order accuracy.

Crouzeix's two-stage, 3rd order Diagonally Implicit Runge–Kutta method:

\begin{array}{c|cc} 1+
2
\sqrt3
6

&

1+
2
\sqrt3
6

&0\\

1-
2
\sqrt3
6

&-

\sqrt3
3

&

1+
2
\sqrt3
6

\\ \hline&

1
2

&

1
2

\\ \end{array}

Crouzeix's three-stage, 4th order Diagonally Implicit Runge–Kutta method:

\begin{array}{c|ccc} 1+\alpha
2

&

1+\alpha
2

&0&0\\

1
2

&-

\alpha
2

&

1+\alpha
2

&0\\

1-\alpha
2

&1+\alpha&-(1+2\alpha)&

1+\alpha
2

\\\hline&

1
6\alpha2

&1-

1
3\alpha2

&

1
6\alpha2

\\ \end{array}

with \alpha = \frac\cos.

Three-stage, 3rd order, L-stable Diagonally Implicit Runge–Kutta method:

\begin{array}{c|ccc} x&x&0&0\\

1+x
2

&

1-x
2

&x&0\\ 1&-3x2/2+4x-1/4&3x2/2-5x+5/4&x\\ \hline&-3x2/2+4x-1/4&3x2/2-5x+5/4&x\\ \end{array}

with

x=0.4358665215

Nørsett's three-stage, 4th order Diagonally Implicit Runge–Kutta method has the following Butcher tableau:

\begin{array}{c|ccc} x&x&0&0\\ 1/2&1/2-x&x&0\\ 1-x&2x&1-4x&x\\ \hline &

1
6(1-2x)2

&

3(1-2x)2-1
3(1-2x)2

&

1
6(1-2x)2

\\ \end{array}

with

x

one of the three roots of the cubic equation

x3-3x2/2+x/2-1/24=0

. The three roots of this cubic equation are approximately

x1=1.06858

,

x2=0.30254

, and

x3=0.12889

. The root

x1

gives the best stability properties for initial value problems.

Four-stage, 3rd order, L-stable Diagonally Implicit Runge–Kutta method

\begin{array}{c|cccc} 1/2&1/2&0&0&0\\ 2/3&1/6&1/2&0&0\\ 1/2&-1/2&1/2&1/2&0\\ 1&3/2&-3/2&1/2&1/2\\ \hline &3/2&-3/2&1/2&1/2\\ \end{array}

Lobatto methods

There are three main families of Lobatto methods, called IIIA, IIIB and IIIC (in classical mathematical literature, the symbols I and II are reserved for two types of Radau methods). These are named after Rehuel Lobatto as a reference to the Lobatto quadrature rule, but were introduced by Byron L. Ehle in his thesis. All are implicit methods, have order 2s - 2 and they all have c1 = 0 and cs = 1. Unlike any explicit method, it's possible for these methods to have the order greater than the number of stages. Lobatto lived before the classic fourth-order method was popularized by Runge and Kutta.

Lobatto IIIA methods

The Lobatto IIIA methods are collocation methods. The second-order method is known as the trapezoidal rule:

\begin{array}{c|cc} 0&0&0\\ 1&1/2&1/2\\ \hline &1/2&1/2\\ &1&0\\ \end{array}

The fourth-order method is given by

\begin{array}{c|ccc} 0&0&0&0\\ 1/2&5/24&1/3&-1/24\\ 1&1/6&2/3&1/6\\ \hline &1/6&2/3&1/6\\ &-

12
&

2&-

12
\\ \end{array}

These methods are A-stable, but not L-stable and B-stable.

Lobatto IIIB methods

The Lobatto IIIB methods are not collocation methods, but they can be viewed as discontinuous collocation methods . The second-order method is given by

\begin{array}{c|cc} 0&1/2&0\\ 1&1/2&0\\ \hline &1/2&1/2\\ &1&0\\ \end{array}

The fourth-order method is given by

\begin{array}{c|ccc} 0&1/6&-1/6&0\\ 1/2&1/6&1/3&0\\ 1&1/6&5/6&0\\ \hline &1/6&2/3&1/6\\ &-

12
&

2&-

12
\\ \end{array}

Lobatto IIIB methods are A-stable, but not L-stable and B-stable.

Lobatto IIIC methods

The Lobatto IIIC methods also are discontinuous collocation methods. The second-order method is given by

\begin{array}{c|cc} 0&1/2&-1/2\\ 1&1/2&1/2\\ \hline &1/2&1/2\\ &1&0\\ \end{array}

The fourth-order method is given by

\begin{array}{c|ccc} 0&1/6&-1/3&1/6\\ 1/2&1/6&5/12&-1/12\\ 1&1/6&2/3&1/6\\ \hline &1/6&2/3&1/6\\ &-

12
&

2&-

12
\\ \end{array}

They are L-stable. They are also algebraically stable and thus B-stable, that makes them suitable for stiff problems.

Lobatto IIIC* methods

The Lobatto IIIC* methods are also known as Lobatto III methods (Butcher, 2008), Butcher's Lobatto methods (Hairer et al., 1993), and Lobatto IIIC methods (Sun, 2000) in the literature.[6] The second-order method is given by

\begin{array}{c|cc} 0&0&0\\ 1&1&0\\ \hline &1/2&1/2\\ \end{array}

Butcher's three-stage, fourth-order method is given by

\begin{array}{c|ccc} 0&0&0&0\\ 1/2&1/4&1/4&0\\ 1&0&1&0\\ \hline &1/6&2/3&1/6\\ \end{array}

These methods are not A-stable, B-stable or L-stable. The Lobatto IIIC* method for

s=2

is sometimes called the explicit trapezoidal rule.

Generalized Lobatto methods

One can consider a very general family of methods with three real parameters

(\alphaA,\alphaB,\alphaC)

by considering Lobatto coefficients of the form

ai,j(\alphaA,\alphaB,\alphaC)=\alphaA

A
a
i,j

+\alphaB

B
a
i,j

+\alphaC

C
a
i,j

+\alphaC*

C*
a
i,j

,where

\alphaC*=1-\alphaA-\alphaB-\alphaC

.For example, Lobatto IIID family introduced in (Nørsett and Wanner, 1981), also called Lobatto IIINW, are given by

\begin{array}{c|cc} 0&1/2&1/2\\ 1&-1/2&1/2\\ \hline &1/2&1/2\\ \end{array}

and

\begin{array}{c|ccc} 0&1/6&0&-1/6\\ 1/2&1/12&5/12&0\\ 1&1/2&1/3&1/6\\ \hline &1/6&2/3&1/6\\ \end{array}

These methods correspond to

\alphaA=2

,

\alphaB=2

,

\alphaC=-1

, and

\alphaC*=-2

. The methods are L-stable. They are algebraically stable and thus B-stable.

Radau methods

Radau methods are fully implicit methods (matrix A of such methods can have any structure). Radau methods attain order 2s - 1 for s stages. Radau methods are A-stable, but expensive to implement. Also they can suffer from order reduction.The first order Radau method is similar to backward Euler method.

Radau IA methods

The third-order method is given by

\begin{array}{c|cc} 0&1/4&-1/4\\ 2/3&1/4&5/12\\ \hline &1/4&3/4\\ \end{array}

The fifth-order method is given by

\begin{array}{c|ccc} 0&

1
9

&

-1-\sqrt{6
} & \frac \\\frac - \frac & \frac & \frac + \frac & \frac - \frac\\\frac + \frac & \frac & \frac + \frac & \frac - \frac \\\hline & \frac & \frac + \frac & \frac - \frac \\\end

Radau IIA methods

The ci of this method are zeros of

ds-1
dxs-1

(xs-1(x-1)s)

. The third-order method is given by

\begin{array}{c|cc} 1/3&5/12&-1/12\\ 1&3/4&1/4\\ \hline &3/4&1/4\\ \end{array}

The fifth-order method is given by

\begin{array}{c|ccc} 2
5

-

\sqrt{6
} & \frac - \frac & \frac - \frac & -\frac + \frac \\\frac + \frac & \frac + \frac & \frac + \frac & -\frac - \frac\\1 & \frac - \frac & \frac + \frac & \frac \\\hline & \frac - \frac & \frac + \frac & \frac \\\end

References

Notes and References

  1. Ralston . Anthony . Runge-Kutta Methods with Minimum Error Bounds . Math. Comput. . 1962 . 16 . 80 . 431–437. 10.1090/S0025-5718-1962-0150954-0 . free .
  2. Sanderse . Benjamin . Veldman . Arthur . Constraint-consistent Runge–Kutta methods for one-dimensional incompressible multiphase flow . . 2019. 384 . 170 . 10.1016/j.jcp.2019.02.001 . 1809.06114 . 2019JCoPh.384..170S . 73590909 .
  3. Kutta . Martin . Martin Kutta . Beitrag zur näherungsweisen Integration totaler Differentialgleichungen . Zeitschrift für Mathematik und Physik . 46 . 435–453 . 1901.
  4. Fehlberg. E.. July 1969. Low-order classical Runge-Kutta formulas with stepsize control and their application to some heat transfer problems. NASA Technical Report R-315.
  5. For discussion see: Christopher A. Kennedy. Mark H. Carpenter. Diagonally Implicit Runge-Kutta Methods for Ordinary Differential Equations. A Review . Technical Memorandum, NASA STI Program . 2016.
  6. See Laurent O. Jay (N.D.). "Lobatto methods". University of Iowa