In numerical analysis, the Runge–Kutta methods ([1]) are a family of implicit and explicit iterative methods, which include the Euler method, used in temporal discretization for the approximate solutions of simultaneous nonlinear equations.[2] These methods were developed around 1900 by the German mathematicians Carl Runge and Wilhelm Kutta.
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:
dy | |
dt |
=f(t,y), y(t0)=y0.
Here
y
t
dy | |
dt |
y
t
y
t0
y
y0
f
t0
y0
Now we pick a step-size h > 0 and define:
\begin{align} yn+1&=yn+
h | |
6 |
\left(k1+2k2+2k3+k4\right),\\ tn+1&=tn+h\\ \end{align}
for n = 0, 1, 2, 3, ..., using
\begin{align} k1&= f(tn,yn),\\ k2&= f\left(tn+
h | |
2 |
,yn+h
k1 | |
2 |
\right),\ k3&= f\left(tn+
h | |
2 |
,yn+h
k2 | |
2 |
\right),\\ k4&= f\left(tn+h,yn+hk3\right). \end{align}
Here
yn+1
y(tn+1)
yn+1
yn
k1
y
k2
y
k1
k3
y
k2
k4
y
k3
In averaging the four slopes, greater weight is given to the slopes at the midpoint. If
f
y
O(h5)
O(h4)
In many practical applications the function
f
t
f
tn+1
The family of explicit Runge–Kutta methods is a generalization of the RK4 method mentioned above. It is given by
yn+1=yn+h
s | |
\sum | |
i=1 |
biki,
\begin{align} k1&=f(tn,yn),\\ k2&=f(tn+c2h,yn+(a21k1)h),\\ k3&=f(tn+c3h,yn+(a31k1+a32k2)h),\\ & \vdots\\ ks&=f(tn+csh,yn+(as1k1+as2k2+ … +as,s-1ks-1)h). \end{align}
(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 [''a<sub>ij</sub>''] 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):
0 | ||||||
c2 | a21 | |||||
c3 | a31 | a32 | ||||
\vdots | \vdots | \ddots | ||||
cs | as1 | as2 | … | as,s-1 | ||
b1 | b2 | … | bs-1 | bs |
A Taylor series expansion shows that the Runge–Kutta method is consistent if and only if
s | |
\sum | |
i=1 |
bi=1.
i-1 | |
\sum | |
j=1 |
aij=cifori=2,\ldots,s.
In general, if an explicit
s
p
s\gep
p\ge5
s\gep+1
p>6
s=p+1
p>7
p+2
s
p
\begin{array}{c|cccccccc} p&1&2&3&4&5&6&7&8\\ \hline mins&1&2&3&4&6&7&9&11 \end{array}
p=1,2,\ldots,6
The RK4 method falls in this framework. Its tableau is
0 | |||||
1/2 | 1/2 | ||||
1/2 | 0 | 1/2 | |||
1 | 0 | 0 | 1 | ||
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.[5] 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
0 | |||||
1/3 | 1/3 | ||||
2/3 | -1/3 | 1 | |||
1 | 1 | −1 | 1 | ||
1/8 | 3/8 | 3/8 | 1/8 |
However, the simplest Runge–Kutta method is the (forward) Euler method, given by the formula
yn+1=yn+hf(tn,yn)
0 | ||
1 |
An example of a second-order method with two stages is provided by the explicit midpoint method:
yn+1=yn+
hf\left(t | ||||
|
h,
y | ||||
|
hf(tn, yn)\right).
0 | |||
1/2 | 1/2 | ||
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
yn+1=yn+hl((1-\tfrac1{2\alpha})f(tn,yn)+\tfrac1{2\alpha}f(tn+\alphah,yn+\alphahf(tn,yn))r).
Its Butcher tableau is
0 | |||
\alpha | \alpha | ||
(1-\tfrac1{2\alpha}) | \tfrac1{2\alpha} |
In this family,
\alpha=\tfrac12
\alpha=1
\alpha=\tfrac23
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
\begin{align} k1&=f(tn, yn),\\ k2&=f(tn+\tfrac{2}{3}h, yn+\tfrac{2}{3}hk1),\\ yn+1&=yn+h\left(\tfrac{1}{4}k1+\tfrac{3}{4}k2\right). \end{align}
This method is used to solve the initial-value problem
dy | |
dt |
=\tan(y)+1, y0=1, t\in[1,1.1]
The method proceeds as follows:
t0=1\colon | ||||
y0=1 | ||||
t1=1.025\colon | ||||
y0=1 | k1=2.557407725 | k2=f(t0+\tfrac23h, y0+\tfrac23hk1)=2.7138981400 | ||
y1=y0+h(\tfrac14k1+\tfrac34k2)=\underline{1.066869388} | ||||
t2=1.05\colon | ||||
y1=1.066869388 | k1=2.813524695 | k2=f(t1+\tfrac23h, y1+\tfrac23hk1) | ||
y2=y1+h(\tfrac14k1+\tfrac34k2)=\underline{1.141332181} | ||||
t3=1.075\colon | ||||
y2=1.141332181 | k1=3.183536647 | k2=f(t2+\tfrac23h, y2+\tfrac23hk1) | ||
y3=y2+h(\tfrac14k1+\tfrac34k2)=\underline{1.227417567} | ||||
t4=1.1\colon | ||||
y3=1.227417567 | k1=3.796866512 | k2=f(t3+\tfrac23h, y3+\tfrac23hk1) | ||
y4=y3+h(\tfrac14k1+\tfrac34k2)=\underline{1.335079087}. |
The numerical solutions correspond to the underlined values.
Adaptive methods are designed to produce an estimate of the local truncation error of a single Runge–Kutta step. This is done by having two methods, one with order
p
p-1
During the integration, the step size is adapted such that the estimated error stays below a user-defined threshold: If the error is too high, a step is repeated with a lower step size; if the error is much smaller, the step size is increased to save time. This results in an (almost) optimal step size, which saves computation time. Moreover, the user does not have to spend time on finding an appropriate step size.
The lower-order step is given by
* | |
y | |
n+1 |
=yn+
s | |
h\sum | |
i=1 |
* | |
b | |
i |
ki,
ki
en+1=yn+1-
* | |
y | |
n+1 |
=
s | |
h\sum | |
i=1 |
(bi-
* | |
b | |
i) |
ki,
O(hp)
* | |
b | |
i |
0 | |||||||||||||||||||||||||||||||
c2 | a21 | ||||||||||||||||||||||||||||||
c3 | a31 | a32 | |||||||||||||||||||||||||||||
\vdots | \vdots | \ddots | |||||||||||||||||||||||||||||
cs | as1 | as2 | … | as,s-1 | |||||||||||||||||||||||||||
b1 | b2 | … | bs-1 | bs | |||||||||||||||||||||||||||
|
| … |
|
|
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 | |||
16/135 | 0 | 6656/12825 | 28561/56430 | −9/50 | 2/55 | |||
25/216 | 0 | 1408/2565 | 2197/4104 | −1/5 | 0 |
However, the simplest adaptive Runge–Kutta method involves combining Heun's method, which is order 2, with the Euler method, which is order 1. Its extended Butcher tableau is:
0 | ||||
1 | 1 | |||
1/2 | 1/2 | |||
1 | 0 |
Other adaptive Runge–Kutta methods are the Bogacki–Shampine method (orders 3 and 2), the Cash–Karp method and the Dormand–Prince method (both with orders 5 and 4).
A Runge–Kutta method is said to be nonconfluent if all the
ci,i=1,2,\ldots,s
Runge–Kutta–Nyström methods are specialized Runge–Kutta methods that are optimized for second-order differential equations.[6] [7]
All Runge–Kutta methods mentioned up to now are explicit 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
yn+1=yn+h
s | |
\sum | |
i=1 |
biki,
ki=f\left(tn+cih, yn+h
s | |
\sum | |
j=1 |
aijkj\right), i=1,\ldots,s.
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
aij
\begin{array}{c|cccc} c1&a11&a12&...&a1s\\ c2&a21&a22&...&a2s\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ cs&as1&as2&...&ass\\ \hline &b1&b2&...&bs\\ &
* | |
b | |
1 |
&
* | |
b | |
2 |
&...&
* | |
b | |
s\\ \end{array} |
= \begin{array}{c|c} c&A\\ \hline &
bT |
\\ \end{array}
b*
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.
The simplest example of an implicit Runge–Kutta method is the backward Euler method:
yn=yn+hf(tn+h, yn).
The Butcher tableau for this is simply:
\begin{array}{c|c} 1&1\\ \hline &1\\ \end{array}
This Butcher tableau corresponds to the formulae
k1=f(tn+h, yn+hk1) and yn+1=yn+hk1,
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:
\begin{array}{c|cc} 0&0&0\\ 1&
1 | |
2 |
&
1 | |
2 |
\\ \hline &
1 | & | |
2 |
1 | |
2 |
\\ &1&0\\ \end{array}
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:
\begin{array}{c|cc} | 12 |
- |
16 | |
\sqrt3 |
&
14 | |
& |
14 | |
- |
16 | \\ | |
\sqrt3 |
12 | |
+ |
16 | |
\sqrt3 |
&
14 | |
+ |
16 | |
\sqrt3 |
&
14 | |
\\ \hline |
&
12 | |
& |
12 | |
\\ |
&
| ||||
& |
| ||||
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
y'=λy
yn+1=r(hλ)yn
r(z)=1+zbT(I-zA)-1e=
\det(I-zA+zebT) | |
\det(I-zA) |
,
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.
The numerical solution to the linear test equation decays to zero if | r(z) | < 1 with z = hλ. The set of such z is called the domain of absolute stability. In particular, the method is said to be absolute stable if all z with Re(z) < 0 are in the domain of absolute stability. The stability function of an explicit Runge–Kutta method is a polynomial, so explicit Runge–Kutta methods can never be A-stable.
If the method has order p, then the stability function satisfies
r(z)=rm{e}z+O(zp+1)
z\to0
The Gauss–Legendre method with s stages has order 2s, so its stability function is the Padé approximant with m = n = s. It follows that the method is A-stable. This shows that A-stable Runge–Kutta can have arbitrarily high order. In contrast, the order of A-stable linear multistep methods cannot exceed two.[8]
The A-stability concept for the solution of differential equations is related to the linear autonomous equation
y'=λy
y'=f(y)
\langlef(y)-f(z), y-z\rangle\leq0
\|yn+1-zn+1\|\leq\|yn-zn\|
Let
B
M
Q
s x s
B
M
B
Q
In general a Runge–Kutta method of order
s
yt=yt+h ⋅
s | |
\sum | |
i=1 |
aiki+l{O}(hs+1),
ki
s | |
=\sum | |
j=1 |
\betaijf\left(kj, tn+\alphaih\right)
yt
i
We develop the derivation[9] for the Runge–Kutta fourth-order method using the general formula with
s=4
(t, t+h)
\begin{align} &\alphai&&\betaij\\ \alpha1&=0&\beta21&=
1 | |
2 |
\\ \alpha2&=
1 | |
2 |
&\beta32&=
1 | |
2 |
\\ \alpha3&=
1 | |
2 |
&\beta43&=1\\ \alpha4&=1&&\\ \end{align}
and
\betaij=0
1 | |
\begin{align} y | |
t+h |
&=yt+hf\left(yt, t\right)
2 | |
\\ y | |
t+h |
&=yt+
1 | ||
hf\left(y | , t+ | |
t+h/2 |
h | |
2 |
\right)
3 | |
\\ y | |
t+h |
&=yt+
2 | ||
hf\left(y | , t+ | |
t+h/2 |
h | |
2 |
\right) \end{align}
1 | |
y | |
t+h/2 |
=\dfrac{yt+
1 | |
y | |
t+h |
2 | |
y | |
t+h/2 |
=\dfrac{yt+
2 | |
y | |
t+h |
\begin{align} k1&=f(yt, t)\\ k2&=
1 | |
f\left(y | |
t+h/2 |
, t+
h | |
2 |
\right)=f\left(yt+
h | |
2 |
k1, t+
h | |
2 |
\right)\\ k3&=
2 | |
f\left(y | |
t+h/2 |
, t+
h | |
2 |
\right)=f\left(yt+
h | |
2 |
k2, t+
h | |
2 |
\right)\\ k4&=
3 | |
f\left(y | |
t+h |
, t+h\right)=f\left(yt+hk3, t+h\right) \end{align}
l{O}(h2)
f
If we now express the general formula using what we just derived we obtain:
and comparing this with the Taylor series of
yt+h
t
we obtain a system of constraints on the coefficients:
\begin{cases} &a+b+c+d=1\\[6pt] &
1 | |
2 |
b+
1 | |
2 |
c+d=
1 | |
2 |
\\[6pt] &
1 | |
4 |
c+
1 | |
2 |
d=
1 | |
6 |
\\[6pt] &
1 | |
4 |
d=
1 | |
24 |
\end{cases}
a=
1 | |
6 |
,b=
1 | |
3 |
,c=
1 | |
3 |
,d=
1 | |
6 |
RungeKStep
, 24 embedded Runge-Kutta Nyström algorithms in RungeKNystroemSStep
and 4 general Runge-Kutta Nyström algorithms in RungeKNystroemGStep
.b1=b2=1/2
c1
a21
b1=1/2
i-1 | |
\sum | |
j=1 |
aij=cifori=2,\ldots,s.