In numerical analysis, the Runge–Kutta methods ( ) are a family of explicit and implicit iterative methods, which include the Euler method, used in discretization for the approximate solutions of differential equations.DEVRIES, Paul L.; HASBUN, Javier E. A first course in computational physics. Second edition. Jones and Bartlett Publishers: 2011. p. 215. These methods were developed around 1900 by the German mathematicians Carl Runge and Wilhelm Kutta.
The fourth-order Runge–Kutta method
The most widely known member of the Runge–Kutta family is generally referred to as "RK4", the "classic Runge–Kutta method" or simply as "the Runge–Kutta method".
Let an initial value problem be specified as follows:
Here is an unknown function (scalar or vector) of time , which we would like to approximate; we are told that , the rate at which changes, is a function of and of itself. At the initial time the corresponding value is . The function and the initial conditions , are given.
Now we pick a step-size h > 0 and define:
for n = 0, 1, 2, 3, ..., using;
(Note: the above equations have different but equivalent definitions in different texts., , and leave out the factor h in the definition of the stages. , and use the y values as stages.)
Here is the RK4 approximation of , and the next value () is determined by the present value () plus the weighted average of four increments, where each increment is the product of the size of the interval, h, and an estimated slope specified by function f on the right-hand side of the differential equation. is the slope at the beginning of the interval, using (Euler's method); is the slope at the midpoint of the interval, using and ; is again the slope at the midpoint, but now using and ; is the slope at the end of the interval, using and .
In averaging the four slopes, greater weight is given to the slopes at the midpoint. If is independent of , so that the differential equation is equivalent to a simple integral, then RK4 is Simpson's rule.
The RK4 method is a fourth-order method, meaning that the local truncation error is on the order of , while the total accumulated error is on the order of .
In many practical applications the function is independent of (so called autonomous system, or time-invariant system, especially in physics), and their increments are not computed at all and not passed to function , with only the final formula for used.
Explicit Runge–Kutta methods The family of explicit Runge–Kutta methods is a generalization of the RK4 method mentioned above. It is given by
where
(Note: the above equations may have different but equivalent definitions in some texts.)
To specify a particular method, one needs to provide the integer s (the number of stages), and the coefficients aij (for 1 ≤ j < i ≤ s), bi (for i = 1, 2, ..., s) and ci (for i = 2, 3, ..., s). The matrix [aij] is called the Runge–Kutta matrix, while the bi and ci are known as the weights and the nodes. These data are usually arranged in a mnemonic device, known as a Butcher tableau (after John C. Butcher):
{| style="text-align: center" cellspacing="0" cellpadding="3" | style="border-right:1px solid;" | |- | style="border-right:1px solid;" | || |- | style="border-right:1px solid;" | || || |- | style="border-right:1px solid;" | || || || |- | style="border-right:1px solid; border-bottom:1px solid;" | | style="border-bottom:1px solid;" | | style="border-bottom:1px solid;" | | style="border-bottom:1px solid;" | | style="border-bottom:1px solid;" | || style="border-bottom:1px solid;" | |- | style="border-right:1px solid;" | || || || || ||
A Taylor series expansion shows that the Runge–Kutta method is consistent if and only if
There are also accompanying requirements if one requires the method to have a certain order p, meaning that the local truncation error is O(hp+1). These can be derived from the definition of the truncation error itself. For example, a two-stage method has order 2 if b1 + b2 = 1, b2c2 = 1/2, and b2a21 = 1/2. Note that a popular condition for determining coefficients is
This condition alone, however, is neither sufficient, nor necessary for consistency. As a counterexample, consider any explicit 2-stage Runge-Kutta scheme with and and randomly chosen. This method is consistent and (in general) first-order convergent. On the other hand, the 1-stage method with is inconsistent and fails to converge, even though it trivially holds that .
In general, if an explicit -stage Runge–Kutta method has order , then it can be proven that the number of stages must satisfy and if , then . However, it is not known whether these bounds are sharp in all cases. In some cases, it is proven that the bound cannot be achieved. For instance, Butcher proved that for , there is no explicit method with stages. Butcher also proved that for , there is no explicit Runge-Kutta method with stages. In general, however, it remains an open problem what the precise minimum number of stages is for an explicit Runge–Kutta method to have order . Some values which are known are:
The provable bound above then implies that we cannot find methods of orders that require fewer stages than the methods we already know for these orders. The work of Butcher also proves that 7th and 8th order methods have a minimum of 9 and 11 stages, respectively. An example of an explicit method of order 6 with 7 stages can be found in Ref. Explicit methods of order 7 with 9 stages and explicit methods of order 8 with 11 stages are also known. See Refs. for a summary.
Examples The RK4 method falls in this framework. Its tableau is
{| style="text-align: center" cellspacing="0" cellpadding="3" | style="border-right:1px solid;" | 0 |- | style="border-right:1px solid;" | 1/2 || 1/2 |- | style="border-right:1px solid;" | 1/2 || 0 || 1/2 |- | style="border-right:1px solid; border-bottom:1px solid;" | 1 || style="border-bottom:1px solid;" | 0 | style="border-bottom:1px solid;" | 0 || style="border-bottom:1px solid;" | 1 | style="border-bottom:1px solid;" | |- | style="border-right:1px solid;" | || 1/6 || 1/3 || 1/3 || 1/6
A slight variation of "the" Runge–Kutta method is also due to Kutta in 1901 and is called the 3/8-rule. refer to . The primary advantage this method has is that almost all of the error coefficients are smaller than in the popular method, but it requires slightly more floating-point operations per time step. Its Butcher tableau is
{| style="text-align: center" cellspacing="0" cellpadding="3" | style="border-right:1px solid;" | 0 |- | style="border-right:1px solid;" | 1/3 || 1/3 |- | style="border-right:1px solid;" | 2/3 || −1/3 || 1 |- | style="border-right:1px solid; border-bottom:1px solid;" | 1 || style="border-bottom:1px solid;" | 1 | style="border-bottom:1px solid;" | −1 || style="border-bottom:1px solid;" | 1 | style="border-bottom:1px solid;" | |- | style="border-right:1px solid;" | || 1/8 || 3/8 || 3/8 || 1/8
However, the simplest Runge–Kutta method is the (forward) Euler method, given by the formula . This is the only consistent explicit Runge–Kutta method with one stage. The corresponding tableau is
{| style="text-align: center" cellspacing="0" cellpadding="3" | width="10" style="border-right:1px solid; border-bottom:1px solid;" | 0 | width="10" style="border-bottom:1px solid;" | |- | style="border-right:1px solid;" | || 1
Second-order methods with two stages An example of a second-order method with two stages is provided by the explicit midpoint method:
The corresponding tableau is
{| style="text-align: center" cellspacing="0" cellpadding="3" | style="border-right:1px solid;" | 0 |- | style="border-right:1px solid; border-bottom:1px solid;" | 1/2 || style="border-bottom:1px solid;" | 1/2 || style="border-bottom:1px solid;" | |- | style="border-right:1px solid;" | || 0 || 1
The midpoint method is not the only second-order Runge–Kutta method with two stages; there is a family of such methods, parameterized by α and given by the formula
Its Butcher tableau is
{| style="text-align: center" cellspacing="0" cellpadding="8" | style="border-right:1px solid;" | 0 |- | style="border-right:1px solid; border-bottom:1px solid;" | || style="border-bottom:1px solid; text-align: center;" | || style="border-bottom:1px solid;" | |- | style="border-right:1px solid;" | || ||
In this family, gives the midpoint method, is Heun's method, and is Ralston's method.
Use As an example, consider the two-stage second-order Runge–Kutta method with α = 2/3, also known as Ralston method. It is given by the tableau
0 2/3 2/3 1/4 3/4
with the corresponding equations
This method is used to solve the initial-value problem
with step size h = 0.025, so the method needs to take four steps.
The method proceeds as follows:
The numerical solutions correspond to the underlined values.
Implicit Runge–Kutta methods Explicit Runge–Kutta methods are generally unsuitable for the solution of stiff equations because their region of absolute stability is small; in particular, it is bounded. This issue is especially important in the solution of partial differential equations.
The instability of explicit Runge–Kutta methods motivates the development of implicit methods. An implicit Runge–Kutta method has the form
where
The difference with an explicit method is that in an explicit method, the sum over j only goes up to i − 1. This also shows up in the Butcher tableau: the coefficient matrix of an explicit method is lower triangular. In an implicit method, the sum over j goes up to s and the coefficient matrix is not strictly triangular, yielding a Butcher tableau of the form
The consequence of this difference is that at every step, a system of algebraic equations has to be solved. This increases the computational cost considerably. If a method with s stages is used to solve a differential equation with m components, then the system of algebraic equations has ms components. This can be contrasted with implicit linear multistep methods (the other big family of methods for ODEs): an implicit s-step linear multistep method needs to solve a system of algebraic equations with only m components, so the size of the system does not increase as the number of steps increases.
Examples The simplest example of an implicit Runge–Kutta method is the backward Euler method:
The Butcher tableau for this is simply:
This Butcher tableau corresponds to the formulae
which can be re-arranged to get the formula for the backward Euler method listed above.
Another example for an implicit Runge–Kutta method is the trapezoidal rule. Its Butcher tableau is:
The trapezoidal rule is a collocation method (as discussed in that article). All collocation methods are implicit Runge–Kutta methods, but not all implicit Runge–Kutta methods are collocation methods.
The Gauss–Legendre methods form a family of collocation methods based on Gauss quadrature. A Gauss–Legendre method with s stages has order 2s (thus, methods with arbitrarily high order can be constructed). The method with two stages (and thus order four) has Butcher tableau:
Stability The advantage of implicit Runge–Kutta methods over explicit ones is their greater stability, especially when applied to stiff equations. Consider the linear test equation . A Runge–Kutta method applied to this equation reduces to the iteration , with r given by
where e stands for the vector of ones. The function r is called the stability function. It follows from the formula that r is the quotient of two polynomials of degree s if the method has s stages. Explicit methods have a strictly lower triangular matrix A, which implies that det(I − zA) = 1 and that the stability function is a polynomial.