Runge–Kutta methods

The after Carl Runge and Martin Wilhelm Kutta named -stage Runge- Kutta methods are one-step methods for the approximate solution of initial value problems in numerical mathematics. When speaking of the Runge- Kutta method, the classical Runge -Kutta method is usually meant; However, this is only a special case of this family of methods.

General formulation

Given an initial value problem

With exact solution. The exact solution can not generally be given or not efficient, which is why one is content with an approximation at discrete locations. There are various methods of calculating the approximation, for example, one-step process, as this Runge- Kutta method, or multi-step process.

The -stage Runge- Kutta method is one-step method, which are given by expressions of the following kind:

In this case, h is the step size between the successive nodes and. The coefficients define the particular method and can be interpreted as a quadrature formula for the integral. The sizes are referred to as intermediate steps, they correspond to evaluations of the right-hand side f to specific node:

The and are more for the process characteristic coefficients and can be used as quadrature formulas are understood to calculate.

A general Runge- Kutta method is implicit, so it must be solved to determine linear or non-linear systems of equations. But applies to all, the method is explicit.

Controlling the step size h is of particular interest. One can imagine that the function in areas where only small changes between present and, with less computational steps manages, than in those in which there are rapid changes slightly.

Example

An example is the three-stage Runge- Kutta method: the intermediates

Butcher tableau

It is the characteristic coefficient, clearly in the so-called Runge- Kutta tableau (also Butcher schema tableau or English. Called Butcher array ) order. Here, the matrix A is strictly lower triangular matrix ( nilpotent triangular matrix ) with an explicit method.

Order of consistency and convergence order

An important property for the comparison of process is the consistency order based on the notion of the local discretization error. The numerical solution after one step and the exact solution. A one-step method is called consistent of order ( has consistency order ) if the following holds for the local discretization error:

The order of consistency can be determined by Taylor expansion of the exact and numerical solution or. General:

In step methods such as the Runge- Kutta method even applies provided that f and the rule of procedure are Lipschitz continuous:

From the consistency condition (eg, the process should have order 4 ) result consistency equations (English conditions ) for the coefficients of the Runge- Kutta method. The equations and their number can be determined with the help of Taylor expansion or the theory of Butcher trees. With increasing order of the number of to be solved non-linear consistency equations grows rapidly. The setting up of the consistency equations is already not easy; but can be done with the help of the Butcher Trees of computer algebra systems. The release is even more difficult and requires experience and intuition to get "good" coefficients.

An explicit s -stage Runge- Kutta method has order of convergence at most s, an implicit contrast up to 2s.

In order to improve the accuracy of a result, there are two options:

Which strategy is better depends on the concrete problem, increasing the order of convergence, however, is only useful up to a certain limit, since because of the Butcher - bounds the number of stages s is growing faster than the order p. For example, there is no explicit s -stage RKM order of convergence.

Implicit Runge- Kutta methods

Explicit methods have the advantage that can be calculated to stages by recursive substitution, the implicit method, however, a linear or non-linear system of equations with unknowns must be solved according to the form of the right-hand side, which per time step represents a much higher cost. The reason why implicit methods are considered at all, is that explicit Runge- Kutta methods always have a limited stability field, while implicit Runge- Kutta methods for virtually any high orders can be A-stable and thus restrictions on the time step are only necessary due to accuracy considerations and not due to stability limitations. This is particularly interesting for stiff initial value problems and differential- algebraic equations.

The maximum order of an s-stage Runge- Kutta method is 2s. This is achieved exclusively by the Gauss - Legendre method so called, in which the quadrature formulas for the construction of Runge- Kutta methods correspond to the Gauss - Legendre formulas. Order 2s -1 is obtained for instance by means Radau formulas that Runge- Kutta methods are then called Radau method, while order 2s -2 is achieved on Lobatto formulas, procedures are then called Lobatto method.

To avoid the solution of a system of equations with unknowns, Implicit Runge- Kutta methods are often so-called diagonal (short DIRK ) used. In this case, the matrix A in the Butcher array triangular shape, all entries right above the diagonal are therefore zero. This decouples the large system into a sequence of S equation systems. If, in addition, the coefficient on the diagonal constant, it is called a SDIRK method ( for singly diagonally ). The coefficients in the last line of A are identical to those of the vector b, something cost is saved, and in particular, the processes are then also L- stable. This simplification comes at the expense of the maximum order: s -stage DIRK methods have maximum order s 1, where this maximum can not be achieved for arbitrary levels. The data used in the practice methods have order s or less normally.

As an alternative to DIRK method, nor the so-called linearly implicit methods have become established, in particular the Rosenbrock - Wanner method, in which the non-linear equations are approximated by linear ones.

Time step size control: Embedded method

To increase the efficiency of the process it is useful to adjust the time of a fault tolerance step. Runge- Kutta methods offer this through so-called embedded process has a relatively easy way. These consist of a second set of coefficients for a second method:

Wherein the coefficients are selected so that an inferior process, specifically a method of lower order than the original results. Then, the difference is

An estimate of the local error of the original proceeding the order as the embedded method. To calculate no new function evaluations are necessary, but only linear combinations of the already calculated. The determination of a new time step from the error estimator can be done via various controls.

The explicit case the embedded known methods are the Runga -Kutta - Fehlberg and Dormand -Prince - formulas ( DOPRI ).

History

The first Runge- Kutta methods have been developed around 1900 by Karl Heun, Martin Wilhelm Kutta and Carl Runge. In the 1960s, John C. Butcher developed with the simplifying conditions and the Butcher tableau tools to develop higher-order methods. Ernst Hairer took place in 1978, a method of 8th order with ten levels.

Examples

The explicit Euler method ( order 1):

The Heun method ( order 2 ):

The Runge- Kutta method of order 2:

The Runge- Kutta method of order 3 ( cf. Simpson rule):

The 3rd order Heun method:

The classical Runge -Kutta method ( order 4 ):

The implicit trapezoidal method of order 2: