THERE are two types of error involved in a Runge--Kutta step:
* round-off*
error and * truncation*
error (also known as
* discretization*
error). Round-off error is due to the finite-precision (floating-point)
arithmetic
usually used when the method is implemented on a computer.
It depends on the number and type of arithmetical operations used in a step.
Round-off error thus increases in proportion to the total number of integration
steps used, and so prevents one from taking a very small step length.
Normally, round-off error is not considered in the numerical
analysis of the algorithm, since it depends on the computer on which the
algorithm is implemented, and thus is external to the numerical algorithm.
Truncation error is present even with infinite-precision arithmetic, because
it is caused by truncation of the infinite Taylor
series
to form the algorithm. It depends on the step size used, the order of the
method, and the problem being solved.

An obvious requirement for a successful numerical algorithm is that it be
possible to make the truncation error involved as small as is desired by using
a sufficiently small step length: this concept is known as
* convergence*.
A method is said to be convergent if

Notice that **nh** is kept constant, so that is always the same point and
a sequence of approximations converges to the analytic answer
as the step length is successively decreased. This is called a
* fixed-station* limit.
A concept closely related to convergence is known as
* consistency*;
a method is said to be consistent (with the initial value problem) if

where is as defined in Eq.(7). Inserting the consistency condition of Eq.(29) into Eq.(7) we obtain

as the necessary and sufficient condition for Runge--Kutta methods to be consistent. Looking back at Eq.(22), we can see that we satisfied this condition in deriving the family of second-order explicit methods, and in fact it turns out to be automatically satisfied when the method has order one or higher. It is known that consistency is necessary and sufficient for convergence of Runge--Kutta methods, so all Runge--Kutta methods are convergent. We provide a proof of this in Appendix A.1.

The two crucial concepts in the analysis of numerical error are
* local* error and
* global* error.
Local error is the error introduced in a single step of the integration
routine, while global error is the overall error caused by repeated application
of the integration formula. It is obviously the global error that we wish to
know about when integrating a trajectory, however it is not possible to
estimate anything other than bounds which are usually orders of magnitude too
large, and so we must content ourselves with estimating the local
error. Local and global error are sometimes defined to include round-off error
and sometimes not. We do not include round-off error and to avoid any
ambiguity we term the local and global error thus defined local and global
truncation error.

while local truncation error is

If we assume that , i.e., no previous truncation errors have
occurred, then . So if the previous truncation
error is zero, the local truncation error and the global truncation error are
the same. Comparing Eq.(32) with Eq.(12), we can see that a
**p**th-order method has local truncation error .
We can write Eq.(31) as

Thus

since . As , we can now see that the global truncation error is .

We can write the local truncation error as

The term in is the * principal*
local truncation
error, and
is a function of the
* elementary differentials* of order
**p+1**, evaluated at . Elementary differentials are the building blocks
of the Butcher theory mentioned earlier. (The coefficients of in
Eq.(15) are elementary differentials of order **p**.)

Practical codes based on Runge--Kutta or other numerical techniques rely on
error estimates to exercise control of the step length
in order to produce good results.
This * step control* to maintain accuracy requirements may be based on
* step doubling*, otherwise known as
* Richardson extrapolation*.
Each step is taken twice, once with step length **h**, and then again with two
steps of step length .
The difference between the two new **Y**s gives an estimate of the principal
local truncation error of the form

A new step length can then be used for the next step to keep the principal
local truncation error within the required bounds.
A better technique, because it is less computationally expensive,
is to use a Runge--Kutta method that has been specially
developed to provide an estimate of the principal local truncation error at
each step.
This may be done by embedding a **q**-stage, **p**th-order method within a
-stage, th-order method. Runge--Kutta--Merson and
Runge--Kutta--Fehlberg are examples of algorithms using this
* embedding estimate* technique.
It should however be noted that the error estimates provided by some of the
commonly used algorithms are not valid when integrating nonlinear equations.
For example,
Runge--Kutta--Merson
was constructed for the special case of a linear differential system with
constant coefficients, and the error estimates it provides are only valid
in that rare case. It usually overestimates the error, which is safe but
inefficient, but sometimes it underestimates the error, which could be
disastrous. Thus some care has to be taken to ensure that the
embedding algorithm used will provide suitable error estimates.
As well as varying the step length, some codes based on Runge--Kutta methods
may also change between methods of different orders depending on the
error estimates being obtained. These * variable-step, variable-order*
(VSVO) Runge--Kutta based codes are at
present the last word in numerical integration.

The fact that codes based on Runge--Kutta methods use estimates of the
principal local truncation error, which is proportional to ,
rather than estimates of the local truncation error, which is ,
can be significant. The principal local truncation error is usually large in
comparison with the other parts of the local truncation error, in which case
we are justified in using principal local truncation error estimates to set
the step length. However, this is not always the case, and so one should be
wary. The phenomenon of * B-convergence*
[Lambert1991]
shows that the
other elements in the local truncation error can sometimes overwhelm the
principal local truncation error, and the code could then produce incorrect
results without informing the user.

Wed Sep 27 17:21:22 MET 1995