Variable Step Size N-Body ODE Integration Methods
June 9, 1996
As was shown in the discussion of the Gragg-Bulirsch-Store method in Section
38, decreasing the step size generally increases the accuracy of the result. The
basic idea is you can take just about any method discussed in section 2.0 and evaluate each
interval twice, once with a step size of
, and once with a step size of
. The difference
between the answers can give us an estimate of the error term.
While it might seem awfully expensive to evaluate each interval twice, just to see
if step size needs to be changed, there are several mitigating factors that make this method
very practical. First, as has already been mentioned, the savings you get by making a very
large step size when the stars are making smooth paths can pay for a lot of overhead. Sec-
ondly, the initial evaluation of
can be used for both the movement with step size
for the first half of the two steps of size
. Lastly, you can usually take the results of the
error estimate and use it as a correction factor and come up with an answer that is more
accurate than either of the two trial movements.
Many methods, such as the Runge-Kutta and the Adam-Bashford methods, can
have implementations of almost any order you could want. Another way of estimating the
error is to take a movement step once with a method of
and once with the same
method only using an order of
. Like the method of changing step sizes, the differ-
ence between these two steps can give you an estimate of the error for that step.
The multi-step formulas are particularly applicable to this method since all you
have to do is keep a slightly longer history of the star movements. No additional evalua-
are required. The coefficients to the multi-step formulas are fairly easy to cal-
culate and you can even create a table of them and vary the order of the formula as you
change the step size.
The Runge-Kutta is harder to make efficient, but by carefully selecting the points
that are probed, it is often possible to find ways of combining terms in two different ways
to give two different orders. Fehlberg found six k-terms that could be evaluated two differ-
ent ways, one gives a 4
order method and the other gives a 5
order method. Verner
created a set of 8 k-terms that creates a 5
By using two different ODE integration methods with different error terms, you
can also get an estimate of the error. As an example, the Euler method and the Mid-point
method can both be evaluated at the same point without having to evaluate the force func-
tion an additional time. Comparing the results will give you an estimate of the error term.
A more useful example is with the predictor-corrector methods. The difference in the
results between the predictor and the corrector can also give you an estimate of the error
This document is best viewed as n-body.pdf because the translation to html was buggy.