Runge-Kutta method

A one-step method for numerically solving the Cauchy problem for a system of ordinary differential equations of the form

$$ \tag{1 } u^\prime = f ( t , u ) . $$

The principal idea of the Runge–Kutta method was proposed by C. Runge [1] and developed later by W. Kutta [2] and others. Originally, this idea was used only for constructing explicit schemes of the method, which were sought in the form

$$ \tag{2 } y _ {j+ 1} \ = y _ {j} + \theta \sum _ { i= 1} ^ { q } A _ {i} k _ {i} , $$

where

$$ y _ {j +\alpha } \ \cong u ( t _ {j} + \alpha\theta ) ,\ \ k _ {1} \ = f( t _ {j} , y _ {j} ) , $$

$$ k _ {n} \ = \left ( \theta _ {j} + \alpha _ {n} \theta , y _ {j} + \theta \sum_{ m=1} ^ {n-1} \beta _ {nm} k _ {m} \right ) ,\ \ n = 2 \dots q , $$

and, moreover, the values of the constants $ A _ {i} $, $ \alpha _ {n} $, $ \beta _ {nm} $, $ i = 1 \dots q $; $ n = 2 \dots q $; $ m = 1 \dots n - 1 $, were defined from the requirement that the error of equation (2) on the exact solution of (1) should have the highest order (i.e. power of $ \theta $, the stepsize, in the leading term of the expansion).

In contrast to multi-step methods, the Runge–Kutta method, as other one-step methods, only requires the value at the last time point of the approximate solution and allows one to carry out calculations under initial conditions which are natural for equation (1). This allows one to use it directly also for not equally-spaced grids. However, since this method does not make use of information concerning the solution at previous nodes of the grid, it is, in general, less economical than, e.g., the Adams method.

The classical Runge–Kutta method (see, e.g., [3]) is the method

$$ y _ {j+1} \ = y _ {j} + { \frac{1}{6} } \theta( k _ {1} + 2 k _ {2} + 2 k _ {3} + k _ {4} ) , $$

$$ k _ {1} \ = f( t _ {j} , y _ {j} ) ,\ k _ {2} \ =\ f \left ( t _ {j} + { \frac{1}{2} } \theta , y _ {j} + { \frac{1}{2} } \theta k _ {1} \right ) , $$

$$ k _ {3} \ = f \left ( t _ {j} + { \frac{1}{2} } \theta , y _ {j} + { \frac{1}{2} } \theta k _ {2} \right ) ,\ \ k _ {4} \ = f( t _ {j} + \theta , y _ {j} + \theta k _ {3} ) , $$

which belongs to the family of methods with fourth order of accuracy of the form (2) with $ q = 4 $, depending on two free parameters. The simplest explicit Runge–Kutta with first order of accuracy is obtained from (2) when $ q = 1 $; it is also the most widely used. This method is known as Euler's method. From (2) for $ q = 2, 3 $ one can obtain families of Runge–Kutta methods with second and third order of accuracy depending on one and two free parameters, respectively. For $ q > 4 $ the above correspondence between the value of $ q $ and the optimal order of accuracy is no more valid. Runge–Kutta methods of the form (2) with fifth order of accuracy can be realized only for $ q = 6 $, sixth order — for $ q = 7 $, seventh order — for $ q = 9 $, etc. In this case, if one increases $ q $ by one, extension of the set of constants $ A _ {i} $, $ \alpha _ {i} $, $ \beta _ {nm} $ to be chosen in (2) is often insufficient to satisfy the conditions resulting from the requirement to increase the order of accuracy of an explicit Runge–Kutta method by one. To increase the number of parameters to be chosen in (2) one can consider, for example, the following extension of the construction of one-step methods based on the concept of Runge:

$$ \tag{3 } k _ {n} \ = f \left ( t _ {j} + \alpha _ {n} \theta , y _ {j} + \theta \sum _ { m= 1} ^ { q } \beta _ {nm} k _ {m} \right ) , $$

$$ n \ = 1 \dots q . $$

In general, methods of the form (2), (3) are already implicit. This complicates significantly their numerical implementation: The values $ k _ {n} $, $ n = 1 \dots q $, at each step have to be found from the system of, generally speaking, non-linear equations (3). However, due to a considerable increase in the number of constants to be chosen, such methods acquire the following property (see [4]): For any value of $ q $ there exists an implicit Runge–Kutta method of order of accuracy $ 2q $. Moreover, under such extension of the class of Runge–Kutta methods there arise methods well adapted to stiff differential systems (cf. Stiff differential system).

There exists one more modification (see, e.g., [5]) of Runge's concept of constructing one-step methods for numerically solving equations of the form (1). Namely, proceeding from (1) one writes

$$ u( t _ {j} + \theta) - u( t _ {j} ) \ = \theta \int _ { 0 } ^ { 1 } f ( t _ {j} + \alpha \theta , u( t _ {j} + \alpha \theta)) d \alpha . $$

An approximation of the latter integral by a quadrature formula with $ q $ nodes gives

$$ \tag{4 } u( t _ {j} + \theta) \ \cong u( t _ {j} ) + \theta \sum _ { i= 1} ^ { q } A _ {i} f( t _ {j} + \alpha _ {i} \theta , u ( t _ {j} + \alpha _ {i} \theta)) . $$

If the choice of nodes $ \alpha _ {i} $ and coefficients $ A _ {i} $, $ i = 1 \dots q $, of the considered quadrature formula is submitted to the conditions

$$ \tag{5 } \sum _ { i= 1} ^ { q } A _ {i} \ = 1 ,\ \ \sum _ { i= 1} ^ { q } A _ {i} \alpha _ {i} ^ {n} \ = \frac{1}{n+1} , $$

$$ n \ = 1 \dots p - 1 , $$

then the error of the approximate equality (4) will be of order $ \theta ^ {p+1} $. For $ p \leq 2q $ the system of equations (5) is solvable and the approximate equality (4) can be constructed. Similarly, one can write approximate equalities for the unknown values $ u( t _ {j} + \alpha _ {i} \theta) $ in the right-hand side of (4); moreover, restrictions on their accuracy may be in lowering the order, etc.

An example of a one-step method constructed in the way mentioned above is the following method with third order of accuracy, of predictor-corrector type (see [6]):

$$ y _ {j+1/4} \ = y _ {j} + \frac{1}{4} \theta f( t _ {j} , y _ {j} ) , $$

$$ y _ {j+1/2} \ = y _ {j} + \frac{1}{2} \theta f \left ( t _ {j} + \frac \theta {4} , y _ {i+ 1/4 } \right ) , $$

$$ y _ {j+1} ^ {*} \ = y _ {j} + \theta f \left ( t _ {j} + \frac{1}{2} \theta , y _ {j+1/2} \right ) , $$

$$ y _ {j+1} \ = y _ {j} + \frac{1}{6} \theta \left ( f( t _ {j} , y _ {j)} + 4 f \left ( t _ {j} + \frac{1}{2} \theta , y _ {j+1/2} \right ) \right . + $$

$$ + \left . f( t _ {j} + \theta , y _ {j+1} ^ {*} ) \right ) . $$

If one assumes that in (4) one of $ \alpha _ {i} $ is $ 1 $, then in the same way one can also construct implicit methods, e.g., the method

$$ y _ {j+1} \ = y _ {j} + \frac{1}{2} \theta ( f( t _ {j} , y _ {j+1} - \theta f( t _ {j} + \theta , y _ {j+1} )) + $$

$$ + {} f( t _ {j} + \theta , y _ {j+1} )) $$

with second order of accuracy.

The approaches to the construction of numerical methods considered above for equations of type (1) can be extended to ordinary differential equations of higher orders (see [6], [7]) and are also used when constructing difference schemes in the case of partial differential equations.

References

[1]	C. Runge, "Ueber die numerische Auflösung von Differentialgleichungen" Math. Ann. , 46 (1895) pp. 167–178
[2]	W. Kutta, "Beitrag zur naherungsweisen Integration von Differentialgleichungen" Z. Math. und Phys. , 46 (1901) pp. 435–453
[3]	N.S. Bakhvalov, "Numerical methods: analysis, algebra, ordinary differential equations" , MIR (1977) (Translated from Russian)
[4]	J.C. Butcher, "Implicit Runge–Kutta processes" Math. Comp. , 18 (1964) pp. 50–64
[5]	V.V. Bobkov, "A method for constructing one-step rules for the approximate solution of differential equations" Vestsi Akad. Navuk BSSR. Ser. Fiz. Mat. Navuk : 4 (1967) pp. 27–35 (In Russian)
[6]	V.I. Krylov, V.V. Bobkov, P.I. Monastyrnyi, "Numerical methods" , 2 , Moscow (1977) (In Russian)
[7]	L. Collatz, "Numerical treatment of differential equations" , Springer (1966) (Translated from German)

References

[a1]	J.C. Butcher, "The numerical analysis of ordinary differential equations. Runge–Kutta and general linear methods" , Wiley (1987)