In
numerical analysis
Numerical analysis is the study of algorithms that use numerical approximation (as opposed to symbolic computation, symbolic manipulations) for the problems of mathematical analysis (as distinguished from discrete mathematics). It is the study of ...
, the Runge–Kutta methods ( ) are a family of
implicit and explicit iterative methods, which include the
Euler method
In mathematics and computational science, the Euler method (also called forward Euler method) is a first-order numerical procedure for solving ordinary differential equations (ODEs) with a given initial value. It is the most basic explicit met ...
, used in
temporal discretization
Temporal discretization is a mathematical technique applied to transient problems that occur in the fields of applied physics and engineering.
Transient problems are often solved by conducting simulations using computer-aided engineering (CAE) pa ...
for the approximate solutions of
simultaneous nonlinear equations. These methods were developed around 1900 by the German mathematicians
Carl Runge
Carl David Tolmé Runge (; 30 August 1856 – 3 January 1927) was a German mathematician, physicist, and spectroscopist.
He was co-developer and co-eponym of the Runge–Kutta method (German pronunciation: ), in the field of what is today known a ...
and
Wilhelm Kutta.
The 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
In multivariable calculus, an initial value problem (IVP) is an ordinary differential equation together with an initial condition which specifies the value of the unknown function at a given point in the domain. Modeling a system in physics or oth ...
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
In mathematics and particularly in dynamic systems, an initial condition, in some contexts called a seed value, is a value of an evolving variable at some point in time designated as the initial time (typically denoted ''t'' = 0). For ...
,
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
The weighted arithmetic mean is similar to an ordinary arithmetic mean (the most common type of average), except that instead of each of the data points contributing equally to the final average, some data points contribute more than others. The ...
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
In mathematics and computational science, the Euler method (also called forward Euler method) is a first-order numerical procedure for solving ordinary differential equations (ODEs) with a given initial value. It is the most basic explicit met ...
);
*
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
In numerical integration, Simpson's rules are several approximations for definite integrals, named after Thomas Simpson (1710–1761).
The most basic of these rules, called Simpson's 1/3 rule, or just Simpson's rule, reads
\int_a^b f(x) \, ...
.
The RK4 method is a fourth-order method, meaning that the
local truncation error
Truncation errors in numerical integration are of two kinds:
* ''local truncation errors'' – the error caused by one iteration, and
* ''global truncation errors'' – the cumulative error caused by many iterations.
Definitions
Suppose we have ...
is
on the order of
An order of magnitude is an approximation of the logarithm of a value relative to some contextually understood reference value, usually 10, interpreted as the base of the logarithm and the representative of values of magnitude one. Logarithmic dis ...
, 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
Explicit refers to something that is specific, clear, or detailed. It can also mean:
* Explicit knowledge, knowledge that can be readily articulated, codified and transmitted to others
* Explicit (text) The explicit (from Latin ''explicitus est'', ...
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 ''a
ij'' (for 1 ≤ ''j'' < ''i'' ≤ ''s''), ''b
i'' (for ''i'' = 1, 2, ..., ''s'') and ''c
i'' (for ''i'' = 2, 3, ..., ''s''). The matrix
ij''">'aij''is called the ''Runge–Kutta matrix'', while the ''b
i'' and ''c
i'' 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
John Charles Butcher (born 31 March 1933) is a New Zealand mathematician who specialises in numerical methods for the solution of ordinary differential equations..
Butcher works on multistage methods for initial value problems, such as Runge- ...
):
:
A
Taylor series
In mathematics, the Taylor series or Taylor expansion of a function is an infinite sum of terms that are expressed in terms of the function's derivatives at a single point. For most common functions, the function and the sum of its Taylor serie ...
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(''h
p''
+1). These can be derived from the definition of the truncation error itself. For example, a two-stage method has order 2 if ''b''
1 + ''b''
2 = 1, ''b''
2''c''
2 = 1/2, and ''b''
2''a''
21 = 1/2. Note that a popular condition for determining coefficients is
:
This condition alone, however, is neither sufficient, nor necessary for consistency.
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; for example, all known methods of order 8 have at least 11 stages, though it is possible that there are methods with fewer stages. (The bound above suggests that there could be a method with 9 stages; but it could also be that the bound is simply not sharp.) Indeed, it is an open problem
what the precise minimum number of stages
is for an explicit Runge–Kutta method to have order
in those cases where no methods have yet been discovered that satisfy the bounds above with equality. Some values which are known are:
:
The provable bounds above then imply that we can not find methods of orders
that require fewer stages than the methods we already know for these orders. However, it is conceivable that we might find a method of order
that has only 8 stages, whereas the only ones known today have at least 9 stages as shown in the table.
Examples
The RK4 method falls in this framework. Its tableau is
:
A slight variation of "the" Runge–Kutta method is also due to Kutta in 1901 and is called the 3/8-rule. 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 FLOPs (floating-point operations) per time step. Its Butcher tableau is
:
However, the simplest Runge–Kutta method is the (forward)
Euler method
In mathematics and computational science, the Euler method (also called forward Euler method) is a first-order numerical procedure for solving ordinary differential equations (ODEs) with a given initial value. It is the most basic explicit met ...
, given by the formula
. This is the only consistent explicit Runge–Kutta method with one stage. The corresponding tableau is
:
Second-order methods with two stages
An example of a second-order method with two stages is provided by the
midpoint method
In numerical analysis, a branch of applied mathematics, the midpoint method is a one-step method for numerically solving the differential equation,
: y'(t) = f(t, y(t)), \quad y(t_0) = y_0 .
The explicit midpoint method is given by the formula
...
:
:
The corresponding tableau is
:
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
:
In this family,
gives the midpoint method,
is
Heun's method In mathematics and computational science, Heun's method may refer to the improved or modified Euler's method (that is, the explicit trapezoidal rule), or a similar two-stage Runge–Kutta method. It is named after Karl Heun and is a numerical p ...
,
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
with the corresponding equations
:
This method is used to solve the initial-value problem
: