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.

Wed Sep 27 17:21:22 MET 1995