Runge-Kutta method

Some Runge-Kutta procedures in comparison.

The -step Runge-Kutta methods named after Carl Runge and Martin Wilhelm Kutta are one-step methods for the approximate solution of initial value problems in numerical mathematics . When speaking of the Runge-Kutta procedure, the classic Runge-Kutta procedure is usually meant; however, this is only a special case of this family of proceedings. ${\displaystyle s}$

General formulation

An initial value problem is given:

${\displaystyle y'(t)=f\left(t,y(t)\right),\quad y(t_{0})=y_{0},\quad y\colon \mathbb {R} \to \mathbb {R} ^{d}}$

with exact solution . In general, the exact solution cannot be specified or cannot be specified efficiently, which is why one is content with an approximation at discrete points . There are various methods for calculating this approximation, for example one-step methods such as these Runge-Kutta methods, or multi-step methods . ${\displaystyle y(t)}$ ${\displaystyle y_{n}}$ ${\displaystyle t_{n}}$

The -step Runge-Kutta methods are one-step methods which are given by expressions of the following kind: ${\displaystyle s}$

${\displaystyle y_{n+1}=y_{n}+h\sum _{j=1}^{s}b_{j}k_{j}.}$

In this case, referred to the pitch between the successive support points and . The coefficients define the respective method and can be interpreted as weights of the quadrature formula for the integral . The sizes are called intermediate steps, they correspond to evaluations of the right side at certain nodes: ${\displaystyle h}$ ${\displaystyle t_{n}}$ ${\displaystyle t_{n+1}}$ ${\displaystyle b_{j}}$ ${\displaystyle \int _{t_{n}}^{t_{n+1}}f(t,y(t))\mathrm {d} t}$ ${\displaystyle k_{j}}$ ${\displaystyle f}$

${\displaystyle k_{j}=f\left(t_{n}+hc_{j},y_{n}+h\sum _{l=1}^{s}a_{jl}k_{l}\right),\,j=1,...,s.}$

The and are further coefficients characteristic of the method and can be understood as nodes and weights of the quadrature formulas for calculating the . ${\displaystyle c_{j}}$ ${\displaystyle a_{jl}}$ ${\displaystyle k_{j}}$

A general Runge-Kutta method is implicit, so to determine the (linear or non-linear, depending on the structure of ) equation systems have to be solved, because all appear in the formula for both left and right . But if it applies to all , then the procedure is explicit, i. H. Loosen you have no system of equations: Because then you can each of the predetermined to be determined. ${\displaystyle k_{j}}$ ${\displaystyle f}$ ${\displaystyle k_{j}}$ ${\displaystyle k_{.}}$ ${\displaystyle a_{jl}=0}$ ${\displaystyle l\geq j}$ ${\displaystyle k_{j}}$ ${\displaystyle k_{l}}$ ${\displaystyle l<j}$

The control of the step size is of particular interest. One can easily imagine that the function requires fewer calculation steps in areas in which there are only minor changes between and than in areas in which there are rapid changes. ${\displaystyle h}$ ${\displaystyle y_{n+1}}$ ${\displaystyle y_{n}}$

example

One example is the three-stage Runge-Kutta process: with the intermediate stages ${\displaystyle y_{n+1}=y_{n}+h\cdot {\bigg (}{\frac {1}{6}}k_{1}+{\frac {4}{6}}k_{2}+{\frac {1}{6}}k_{3}{\bigg )}}$

${\displaystyle k_{1}=f(t_{n},y_{n})\quad }$

${\displaystyle k_{2}=f\left(t_{n}+{\frac {h}{2}},y_{n}+{\frac {h}{2}}k_{1}\right)\quad }$

${\displaystyle k_{3}=f(t_{n}+h,y_{n}-hk_{1}+2hk_{2})\quad }$

Butcher tableau

You can see the characteristic coefficient , , clearly in Runge-Kutta panel (also Butcher scheme, -Tableau or English. Butcher array arrange called). Here the matrix A is a strict lower triangular matrix ( Nilpotent triangular matrix ) in an explicit procedure . ${\displaystyle c_{j}}$ ${\displaystyle b_{j}}$ ${\displaystyle a_{jl}}$

${\displaystyle {\begin{array}{c|c}\mathbf {c} &A\\\hline &\mathbf {b^{T}} \\\end{array}}={\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}}\;,}$   ${\displaystyle c={\begin{bmatrix}c_{1}\\\vdots \\c_{j}\\\vdots \\c_{s}\end{bmatrix}}\;,\quad b={\begin{bmatrix}b_{1}\\\vdots \\b_{j}\\\vdots \\b_{s}\end{bmatrix}}\;,\quad A={\begin{bmatrix}a_{11}&\dots &a_{1l}&\dots &a_{1s}\\\vdots &\ddots &\vdots &\ddots &\vdots \\a_{j1}&\dots &a_{jl}&\dots &a_{js}\\\vdots &\ddots &\vdots &\ddots &\vdots \\a_{s1}&\dots &a_{sl}&\dots &a_{ss}\\\end{bmatrix}}\;.}$

Order of consistency and order of convergence

An important property for comparing methods is the order of consistency , which is based on the concept of the local discretization error. Here, the numerical solution by one step, and the exact solution. A one-step procedure is called consistent of the order (has consistency order ) if the following applies to the local discretization error: ${\displaystyle \tau =y_{n+1}-y(t_{n+1})}$ ${\displaystyle y_{n+1}}$ ${\displaystyle y(t_{n+1})}$ ${\displaystyle p}$ ${\displaystyle p}$

${\displaystyle \tau \leq {\mathcal {O}}(h^{p+1})}$ (For notation see Landau symbols ) .

The order of consistency can be determined by Taylor expansion of or the exact and numerical solution. In general: ${\displaystyle \tau }$

Order of consistency and stability Order of convergence ${\displaystyle p}$ ${\displaystyle \Rightarrow }$ ${\displaystyle p}$

In the case of one-step processes such as the Runge-Kutta process, the following applies even if and the process specification is Lipschitz continuous: ${\displaystyle f}$

Consistency order Convergence order ${\displaystyle p}$ ${\displaystyle \Rightarrow }$ ${\displaystyle p}$

Consistency equations (conditions) for the coefficients of the Runge-Kutta method result from the consistency condition (e.g. the method should have order 4). The equations and their number can be determined using Taylor expansion or the theory of Butcher trees . With increasing order, the number of non-linear consistency equations to be solved increases rapidly. Setting up the consistency equations is already not easy, but it can be done with the help of the Butcher trees of computer algebra systems. However, solving them is even more difficult and requires experience and a sure instinct in order to obtain “good” coefficients.

An explicit -step Runge-Kutta method has at most a convergence order , while an implicit one has up to . ${\displaystyle s}$ ${\displaystyle s}$ ${\displaystyle 2s}$

There are two ways to improve the accuracy of a result:

1. You can reduce the step size, that is, you increase the number of discretization points.
2. One can choose methods of higher order of convergence.

Which strategy is better depends on the specific problem, but increasing the convergence order only makes sense up to a certain limit, since the number of stages grows faster than the order because of the Butcher's bounds . For example, there is no explicit-stage RKV of the convergence order . ${\displaystyle s}$ ${\displaystyle p}$ ${\displaystyle s\geq 5}$ ${\displaystyle s}$ ${\displaystyle q=s}$

Implicit Runge-Kutta procedures

Explicit methods have the advantage that the steps can be calculated through successive insertion, with the implicit method, on the other hand, depending on the shape of the right-hand side, a linear or non-linear system of equations with unknowns has to be solved, which represents a significantly higher effort per time step. The reason why implicit methods are taken into account at all is that explicit Runge-Kutta methods always have a limited stability region , while implicit Runge-Kutta methods can be A-stable for practically arbitrarily high orders and thus restrictions on the time step are only necessary because of accuracy considerations and not because of stability limitations. This is of particular interest in the case of rigid initial value problems and differential algebraic equations . ${\displaystyle f\in \mathbb {R} ^{d}}$ ${\displaystyle s\cdot d}$

The maximum order of a -step Runge-Kutta method is . This is achieved exclusively by the Gauss-Legendre method, in which the quadrature formulas for the construction of the Runge-Kutta method correspond to the Gauss-Legendre formulas . Order is achieved by means of Radau formulas, the Runge-Kutta methods are then called Radau methods, while order is achieved using Lobatto formulas, the methods are then called Lobatto methods. ${\displaystyle s}$ ${\displaystyle 2s}$ ${\displaystyle 2s-1}$ ${\displaystyle 2s-2}$

Diagonally Implicit Runge-Kutta methods (DIRK for short) are often used to avoid solving a system of equations with unknowns. The matrix in the Butcher array is triangular, so all entries to the right above the diagonal are zero. This decouples the large system of equations into a sequence of systems of equations. If the coefficient is also constant on the diagonal, one speaks of an SDIRK method (for singly diagonal ). If the coefficients in the last line of are identical to those of the vector , some effort is saved, but in particular the methods are then also L-stable . This simplification occurs at the expense of the maximum order: -step DIRK methods have a maximum order , whereby this maximum cannot be reached for any steps. The procedures used in practice are generally in order or less. ${\displaystyle s\cdot d}$ ${\displaystyle A}$ ${\displaystyle s}$ ${\displaystyle A}$ ${\displaystyle b}$ ${\displaystyle s}$ ${\displaystyle s+1}$ ${\displaystyle s}$

As an alternative to DIRK methods, the linear implicit methods have established themselves, in particular the Rosenbrock-Wanner methods , in which the non-linear equations are approximated by linear ones.

Time step size control: Embedded processes

In order to increase the efficiency of the method, it makes sense to adapt the time step to an error tolerance. Runge-Kutta methods offer a relatively simple option for this via embedded methods. These consist of a second set of coefficients for a second procedure: ${\displaystyle {\hat {b}}}$

${\displaystyle {\hat {y}}_{n+1}=y_{n}+h\sum _{j=1}^{s}{\hat {b}}_{j}k_{j},}$

whereby the coefficients are chosen in such a way that a worse method, specifically a method of lower order than the original one, results. Then the difference is

${\displaystyle y_{n+1}-{\hat {y}}_{n+1}=h\sum _{j=1}^{s}(b_{j}-{\hat {b}}_{j})k_{j}}$

an estimate of the local error of the original method from the order as the embedded method. No new function evaluations are necessary for the calculation, only linear combinations of those already calculated . A new time step size can be determined from the error estimator using various step size controls . ${\displaystyle k_{j}}$

In the explicit case, the best-known embedded methods are the Runge-Kutta-Fehlberg and Dormand-Prince formulas (DOPRI).

history

The first Runge-Kutta methods were developed by Karl Heun , Martin Wilhelm Kutta , and Carl Runge around 1900 . In the 1960s, John C. Butcher developed tools using the simplifying conditions and the Butcher tableau to develop higher-order processes. In 1978 Ernst Hairer found an 8th order procedure with ten steps.

Examples

The explicit Euler method (order 1):

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

The implicit Euler method (order 1):

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

The Heun method (order 2):

${\displaystyle {\begin{array}{c|cc}0\\1&1\\\hline &{\frac {1}{2}}&{\frac {1}{2}}\end{array}}}$

The Runge-Kutta method of order 2:

${\displaystyle {\begin{array}{c|cc}0\\{\frac {1}{2}}&{\frac {1}{2}}\\\hline &0&1\end{array}}}$

The implicit trapezoidal method of order 2:

${\displaystyle {\begin{array}{c|cc}0\\1&{\frac {1}{2}}&{\frac {1}{2}}\\\hline &{\frac {1}{2}}&{\frac {1}{2}}\end{array}}}$

The Runge-Kutta method of order 3 (see Simpson's rule ):

${\displaystyle {\begin{array}{c|ccc}0\\{\frac {1}{2}}&{\frac {1}{2}}\\1&-1&2\\\hline &{\frac {1}{6}}&{\frac {4}{6}}&{\frac {1}{6}}\end{array}}}$

The 3rd order Heun method:

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

The classic Runge-Kutta method (order 4):

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

literature

• Peter Albrecht: The Runge-Kutta Theory in a Nutshell . In: SIAM Journal on Numerical Analysis . 33, 5, October 1996, ISSN  0036-1429 , pp. 1712-1735.
• John C. Butcher : The Numerical Analysis of Ordinary Differential Equations. Runge-Kutta and General Linear Methods . Wiley, Chichester et al. 1987, ISBN 0-471-91046-5 ( A Wiley-Interscience publication ).
• Peter Deuflhard , Folkmar Bornemann : Numerical Mathematics . Volume 2: Ordinary Differential Equations . 2nd completely revised and enlarged edition. de Gruyter, Berlin 2002, ISBN 3-11-017181-3 .
• Ernst Hairer, Gerhard Wanner: Solving Ordinary Differential Equations . Volume 1: Nonstiff Problems . 2nd revised edition. Springer Verlag, Berlin et al. 1993, ISBN 3-540-56670-8 ( Springer series in computational mathematics 8), (also reprint: ibid 2008, ISBN 978-3-642-05163-0 ).
• E. Hairer, G. Wanner: Solving Ordinary Differential Equations . Volume 2: Stiff and differential-algebraic problems . 2nd revised edition. Corrected 2nd print. Springer Verlag, Berlin et al. 2002, ISBN 3-540-60452-9 ( Springer series in computational mathematics 14), (also reprint: ibid 2010, ISBN 978-3-642-05220-0 ).
• Martin Hermann : Numerics of ordinary differential equations. Initial and boundary value problems . Oldenbourg, Munich et al. 2004, ISBN 3-486-27606-9 .
• M. Sofroniou: Symbolic Derivation of Runge-Kutta Methods . In: Journal of Symbolic Computation . 18, 3, September 1994, ISSN  0747-7171 , pp. 265-296.
• Karl Strehmel, Rüdiger Weiner: Linear-implicit Runge-Kutta methods and their application . Teubner, Stuttgart et al. 1992, ISBN 3-8154-2027-X ( Teubner texts on mathematics 127).

Web links

• Holistic Numerical Methods Institute: fourth-order Runge-Kutta method
• Runge-Kutta methods on Scholarpedia.com by John C. Butcher
• Accuracy of numerical integration processes on beltoforion.de

Individual evidence

1. ↑ Heun: New methods for the approximate integration of the differential equations of an independent variable, Z. Math. Phys., Volume 45, 1900, pp. 23–38 ( Heun method )
2. ^ W. Kutta: Contribution to the approximate integration of total differential equations, Z. Math. Phys., Volume 46, 1901, pp. 435–453
3. ↑ C. Runge: About the numerical resolution of differential equations, Math. Annalen, Volume 46, 1895, pp. 167-178, online