Variable Step Size N-Body ODE Integration Methods

June 9, 1996

41

As was shown in the discussion of the Gragg-Bulirsch-Store method in Section
2.5

on page
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

*h*

, and once with a step size of

*2h*

. 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

*f()*

can be used for both the movement with step size

*2h*

and

for the first half of the two steps of size

*h*

. 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

*O(n*

*a*

*)*

and once with the same

method only using an order of

*O(n*

*a+1*

*)*

. 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-

tions of

*f()*

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

th

order method and the other gives a 5

th

order method. Verner

created a set of 8 k-terms that creates a 5

th

and 6

th

order pair.

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

term.

This document is best viewed as n-body.pdf because the translation to html was buggy.