next up previous
Next: Accuracy Up: The Dynamics of Runge--Kutta Previous: Introduction

Derivation of Runge--Kutta methods

RUNGE--KUTTA methods compute approximations to , with initial values , where , , using the Taylor series expansion 

 

so if we term etc. :

 

h is a non-negative real constant called the step length  of the method.

To obtain a q-stage Runge--Kutta method  (q function evaluations per step) we let

where

 

so that

 

with

 

and for an explicit method,  or

 

for an implicit method.  For an explicit method, Eq.(9) can be solved for each in turn, but for an implicit method, Eq.(10) requires the solution of a nonlinear system of s at each step. The set of explicit methods may be regarded as a subset of the set of implicit methods with , . Explicit methods are obviously more efficient to use, but we shall see that implicit methods do have advantages in certain circumstances.

For convenience, the coefficients , , and of the Runge--Kutta method can be written in the form of a Butcher array: 

 

where , and .

Runge--Kutta schemes are one-step  or self-starting  methods; they give in terms of only, and thus they produce a one-dimensional map if they are dealing with a single differential equation. This may be contrasted with other popular schemes (the Adams--Bashforth--Moulton and Backward Differentiation Formulae methods), which are multistep methods; is given in terms of down to . Multistep methods give rise to multi-dimensional maps from single differential equations. 

A method is said to have order  p if p is the largest integer for which

 

For a method of order p, we wish to find values for , and with so that Eq.(8) matches the first p+1 terms in Eq.(4). To do this we Taylor expand Eq.(8) about under the assumption that , so that all previous values are exact, and compare this with Eq.(4) in order to equate coefficients.

For example, the (unique) first-order explicit method is the well-known Euler scheme  

Let us derive an explicit method with p=q=2, that is, a two-stage, second-order method. From Eq.(5) we have

so expanding this,

 

From Eq.(8), and assuming previous exactness,

 

We can choose so

and Eq.(16) becomes

 

We can now equate coefficients in Eqs.(15) and (21) to give:

   

This is a system with three equations in four unknowns, so we can solve in terms of (say) to give a one-parameter family of explicit two-stage, second-order Runge--Kutta methods: 

 

Well-known second-order methods are obtained with , and 1. When , the equation collapses to the first-order Euler method.

It is easy to see that we could not have obtained a third-order method with two stages, and in fact it is a general result that an explicit q-stage method cannot have order greater than q, but this is an upper bound that is realized only for . The minimum number of stages necessary for an explicit method to attain order p is still an open problem. Calling this , the present knowledge [Butcher1987,Lambert1991] is:

  One can see from the table above the reason why fourth-order  methods are so popular, because after that, one has to add two more stages to the method to obtain any increase in the order. It is not known exactly how many stages are required to obtain a ninth-order or tenth-order explicit method. We only know that somewhere between twelve and seventeen stages will give us a ninth-order explicit method, and somewhere between that number and seventeen stages will give us a tenth-order explicit method. Nothing is known for explicit methods of order higher than ten. In contrast to explicit Runge--Kutta methods, it is known that for an implicit q-stage Runge--Kutta method, the maximum possible order for any q.  It should be noted that the order of a method can change depending on whether it is being applied to a single equation or a system, and depending on whether or not the problem is autonomous (see, for example, Lambert lambert).

Derivation of higher-order Runge--Kutta methods using the technique above is a process involving a large amount of tedious algebraic manipulation which is both time consuming and error prone. Using computer algebra removes the latter problem, but not the former, since finding higher-order methods involves solving larger and larger coupled systems of polynomial equations. This defeats Maple running on a modern workstation at q=5. To overcome this problem a very elegant theory has been developed by Butcher  which enables one to establish the conditions for a Runge--Kutta method, either explicit or implicit, to have a given order (for example the conditions given in Eqs.(22)--(24)). We shall merely mention here that the theory is based on the algebraic concept of rooted trees,  and we refer you to books by Butcher butcher, and Lambert lambert for further details.gif



next up previous
Next: Accuracy Up: The Dynamics of Runge--Kutta Previous: Introduction



Julyan Cartwright
Wed Sep 27 17:21:22 MET 1995