next up previous
Next: Absolute Stability Up: The Dynamics of Runge--Kutta Previous: Derivation of Runge--Kutta


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.

Global truncation error   at is


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 pth-order method has local truncation error . We can write Eq.(31) as


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 Ys 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, pth-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.

next up previous
Next: Absolute Stability Up: The Dynamics of Runge--Kutta Previous: Derivation of Runge--Kutta

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