Runge-Kutta methods

In numerical analysis, the Runge-Kutta methods are an important family of implicit and explicit iterative methods for the approximation of solutions of ordinary differential equations. These techniques were developed around 1900 by the mathematicians C. Runge and M.W. Kutta.

See the article on numerical ordinary differential equations for more background and other methods.

Contents

1 The classical fourth-order Runge-Kutta method 2 Explicit Runge-Kutta methods 2.1 Examples 3 Usage 4 References

The classical fourth-order Runge-Kutta method

One member of the family of Runge-Kutta methods is so commonly used, that it is often refered to as "RK4" or simply as "the Runge-Kutta method".

Let an initial value problem be specified as follows.

<math> y' = f(t, y), \quad y(t_0) = y_0 <math>

Then, the RK4 method for this problem is given by the following equation:

<math> y_{n+1} = y_n + {h \over 6} (k_1 + 2k_2 + 2k_3 + k_4) <math>

where

<math> k_1 = f \left( t_n, y_n \right) <math>

<math> k_2 = f \left( t_n + {h \over 2}, y_n + {h \over 2} k_1 \right) <math>

<math> k_3 = f \left( t_n + {h \over 2}, y_n + {h \over 2} k_2 \right) <math>

<math> k_4 = f \left( t_n + h, y_n + hk_3 \right) <math>

Thus, the next value (y_n+1) is determined by the present value (y_n) plus the product of the size of the interval (h) and an estimated slope. The slope is a weighted average of slopes:

• k₁ is the slope at the beginning of the interval;
• k₂ is the slope at the midpoint of the interval, using slope k₁ to determine the value of y at the point t_n + h/2 using Euler's method;
• k₃ is again the slope at the midpoint, but now using the slope k₂ to determine the y-value;
• k₄ is the slope at the end of the interval, with its y-value determined using k₃.

When the four slopes are averaged, more weight is given to the slopes at the midpoint:

<math>\mbox{slope} = \frac{k_1 + 2k_2 + 2k_3 + k_4}{6}.<math>

The RK4 method is a fourth-order method, meaning that the total accumulated error is on the order of h⁴.

Explicit Runge-Kutta methods

The family of explict Runge-Kutta methods is a generalization of the RK4 method mentioned above. It is given by

<math> y_{n+1} = y_n + h\sum_{i=1}^N b_i k_i, <math>

where

<math> k_1 = f(t_n, y_n), \, <math>

<math> k_2 = f(t_n+c_2h, y_n+a_{21}k_1), \, <math>

<math> k_3 = f(t_n+c_3h, y_n+a_{31}k_1+a_{32}k_2), \, <math>

<math> \vdots <math>

<math> k_s = f(t_n+c_sh, y_n+a_{s1}k_1+a_{s2}k_2+\cdots+a_{s,s-1}k_{s-1}). <math>

(Note: the above equations have different but equivalent definitions in different 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). These data are usually arranged in a mnemonic device, known as a Runge-Kutta tableau:

	0
	<math> c_2 <math>	<math> a_{21} <math>
	<math> c_3 <math>	<math> a_{31} <math>	<math> a_{32} <math>
	<math> \vdots <math>	<math> \vdots <math>		<math> \ddots <math>
	<math> c_s <math>	<math> a_{s1} <math>	<math> a_{s2} <math>	<math> \cdots <math>	<math> a_{s,s-1} <math>
		<math> b_1 <math>	<math> b_2 <math>	<math> \cdots <math>	<math> b_{s-1} <math>	<math> b_s <math>

The Runge-Kutta method is consistent if

<math>\sum_{j=1}^{i-1} a_{ij} = c_i\ \mathrm{for}\ i=2, \ldots, s.<math>

There are also accompanying requirements if we require the method to have a certain order p, meaning that the truncation error is O(h^p+1). These can be derived from the definition of the truncation error itself. For example, a 2-stage method has order 2 if b₁ + b₂ = 1, b₂c₂ = 1/2, and b₂a₂₁ = 1/2.

Examples

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

However, the simplest Runge-Kutta method is the (forward) Euler method, given by the formula <math> y_{n+1} = y_n + hf(t_n,y_n) <math>. This is the only consistent explicit Runge-Kutta method with one stage. The corresponding tableau is:

	0
		1

An example of a second-order method with two stages is provided by the midpoint method

<math> y_{n+1} = y_n + hf\left(t_n+\frac{h}{2},y_n+\frac{h}{2}f(t_n, y_n)\right). <math>

The corresponding tableau is:

	0
	1/2	1/2
		0	1

Usage

What follows is an example usage of a two-stage explicit Runge Kutta method, viz.,

	0
	2/3	2/3
		1/4	3/4

to solve the inital-value problem

<math> y' = (\tan{y})+1,\quad y(1)=1,\ t\in [1, 1.1]<math>

with step size h=0.025.

The tableau above yields the equivalent corresponding equations below defining the method:

<math> u_1 = y_n \,<math>

<math> u_2 = y_n + 2/3hf(t_n, u_1) \,<math>

<math> y_{n+1} = y_n + h(1/4f(t_n,u_1)+3/4f(t_n+2/3h,u_2))\,<math>

<math>t_0=1<math>
	<math>y_0=1<math>
<math>t_1=1.025<math>
	<math>u_1 = y_0 = 1<math>	<math>f(t_0,u_1)=2.557407725<math>	<math>u_2 = y_0 + 2/3hf(t_0,u_1) = 1.042623462<math>
	<math>y_1=y_0+h(1/4 f(t_0, u_1) + 3/4 f(t_0+2/3h,u_2)=1.066869388<math>
<math>t_2=1.05<math>
	<math>u_1 = y_1 = 1.066869388<math>	<math>f(t_1,u_1)=2.813524695<math>	<math>u_2 = y_1 + 2/3hf(t_1,u_1) = 1.113761467<math>
	<math>y_2=y_1+h(1/4 f(t_1, u_1) + 3/4 f(t_1+2/3h,u_2)=1.141332181<math>
<math>t_3=1.075<math>
	<math>u_1 = y_2 = 1.141332181<math>	<math>f(t_2,u_1)=3.183536647<math>	<math>u_2 = y_2 + 2/3hf(t_2,u_1) = 1.194391125<math>
	<math>y_3=y_2+h(1/4 f(t_2, u_1) + 3/4 f(t_2+2/3h,u_2)=1.227417567<math>
<math>t_4=1.1<math>
	<math>u_1 = y_3 = 1.227417567 <math>	<math>f(t_3,u_3)=3.796866512<math>	<math>u_2 = y_3 + 2/3hf(t_3,u_1) = 1.290698676<math>
	<math>y_4=y_3+h(1/4 f(t_3, u_1) + 3/4 f(t_3+2/3h,u_2)=1.335079087<math>

The numerical solutions correspond to the underlined values. Note we calculate <math>f(t_i,u_1)<math> to avoid recalculation in the <math>y_i<math>s.

References

• George E. Forsythe, Michael A. Malcolm, and Cleve B. Moler. Computer Methods for Mathematical Computations. Englewood Cliffs, NJ: Prentice-Hall, 1977. (See Chapter 6.)
• Ernst Hairer, Syvert Paul Nørsett, and Gerhard Wanner. Solving ordinary differential equations I: Nonstiff problems, second edition. Berlin: Springer Verlag, 1993. ISBN 3-540-56670-8.
• William H. Press, Brian P. Flannery, Saul A. Teukolsky, William T. Vetterling. Numerical Recipes in C. Cambridge, UK: Cambridge University Press, 1988. (See Sections 15.1 and 15.2.)de:Runge-Kutta-Verfahren