List of Runge–Kutta methods

From Wikipedia, the free encyclopedia

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

\frac{d y}{d t} = f(t, y)\,

which take the form

y_{n+1} = y_n + h \sum_{i=1}^s b_i k_i\,
k_i = f\left(t_n + c_i h, y_n + h \sum_{j = 1}^s a_{ij} k_j\right).

The methods listed on this page are each defined by its Butcher Tableau, which puts the coefficients of the method in a table as follows:

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

Contents

[edit] Explicit methods

The explicit methods are those where the matrix [aij] is lower triangular.

[edit] Forward Euler

This method is first order. The lack of stability and accuracy makes this popular primarily as a simple first introduction to numeric solution.

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

[edit] 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} [citation needed]

[edit] Classic fourth-order method

The "original" Runge–Kutta method.

\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}

[edit] 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} = y_n + h\sum_{i=1}^s b^*_i k_i,

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

e_{n+1} = y_{n+1} - y^*_{n+1} = h\sum_{i=1}^s (b_i - b^*_i) k_i,

which is O(h p). The Butcher Tableau for this kind of method is extended to give the values of b^*_i

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

[edit] Heun-Euler

The simplest adaptive Runge-Kutta method involves combining the Heun 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.

[edit] Fehlberg

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

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
25/216 0 1408/2565 2197/4104 −1/5 0
16/135 0 6656/12825 28561/56430 −9/50 2/55

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

[edit] 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.

[edit] 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
5179/57600 0 7571/16695 393/640 −92097/339200 187/2100 1/40
35/384 0 500/1113 125/192 −2187/6784 11/84 0

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


[edit] Implicit methods

[edit] Backward Euler

This method is first order. Unconditionally stable and non-oscillatory for linear diffusion problems.

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

[edit] Lobatto methods

There are three families of Lobatto methods, called IIIA, IIIB and IIIC. 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.

[edit] Lobatto IIIA methods

The Lobatto IIIA methods are collocation methods. The second-order method is closely analogous to the Crank–Nicolson method.

\begin{array}{c|cc} 0 & 0 & 0 \\ 1 & 1/2 & 1/2\\ \hline & 1/2 & 1/2\\ \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 \\ \end{array}

[edit] Lobatto IIIB methods

The Lobatto IIIB methods are not collocation methods, but they can be viewed as discontinuous collocation methods (Hairer, Lubich & Wanner 2006, §II.1.4). The second-order method is given by

\begin{array}{c|cc} 0 & 1/2 & 0 \\ 1 & 1/2 & 0 \\ \hline & 1/2 & 1/2\\ \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 \\ \end{array}

[edit] 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 \\ \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 \\ \end{array}

[edit] References

  • Hairer, Ernst; Nørsett, Syvert Paul & Wanner, Gerhard (1993), Solving ordinary differential equations I: Nonstiff problems, Berlin, New York: Springer-Verlag, ISBN 978-3-540-56670-0 .
  • Hairer, Ernst & Wanner, Gerhard (1996), Solving ordinary differential equations II: Stiff and differential-algebraic problems, Berlin, New York: Springer-Verlag, ISBN 978-3-540-60452-5 .
  • Hairer, Ernst; Lubich, Christian & Wanner, Gerhard (2006), Geometric Numerical Integration: Structure-Preserving Algorithms for Ordinary Differential Equations (2nd ed.), Berlin, New York: Springer-Verlag, ISBN 978-3-540-30663-4 .
v • d • e
Numerical integration
First order methods
Second order methods
Higher order methods
Languages