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.
