Runge-Kutta and Reusing Datapoints

Question

I am trying to implement the fourth order Runge-Kutta method for solving a first order ODE in Python i.e. $\frac{dy}{dx} = f(x,y)$. I understand how the method works, but am trying to write an efficient algorithm that minimises the number of times $f(x,y)$ is calculated as this is quite costly. I have been told that it is possible to reuse data points that were previously calculated as you increment over the steps but can’t see how. Does anyone know how to do this or is it not possible?

Answer 1

If you are going from yp_1 = f(x_1, y_1) to yp_2 = f(x_1+h, y_2) you are going to need the intermediate points:

K1 = f(x_1+h/2, y_1+h/2*yp_1)
K2 = f(x_1+h/2, y_1+h/2*K1)
K3 = f(x_1+h, y_1+h*K2)

x_2 = x_1 + h
y_2 = y_1 + h/6*(yp_1+2*K1+2*K2+K3)
yp_2 = f(x_2, y_2)

In general none of the intermediate points are useful in the next step. Because K1<>K2 and K3<>yp_2.

Answer 2

In general explicit Runge-Kutta methods of order $N$ require at least $N$ function evaluations, and there is absolutely no way to avoid this. Past $N=4$ they require more than $N$ function evaluations.

If you want to re-use past function evaluations, you need to use a multistep method like Adams-Bashforth.

In any case you pay for each strategy. Single step methods requires largest number of function evaluations, but multistep methods have the largest memory requirement.

Edit: Correction. My statement is true only for explicit methods. The situation is less clear for implicit methods since the number of stages doesn't translate directly to number of function evaluations.

Answer 3

I know that you are using Runge-Kutta Methods to solve your ODE, but if you want to reuse old calculated values of your f(x,y), you may want to consider multistep methods, like the Adams-Bashforth or Adams-Moulton methods. Of course, the disadvantage to these methods is that you cannot use adaptive time-stepping very easily.

Answer 4

Please check on "embedded" methods: the aim in this type of RK methods is to have two methods with different orders, where the high order method uses the same function evaluations as the low order method. This allows for very efficient error estimation. See p.165 and further of "Solving Ordinary Differential Equations I: Nonstiff problems" by Hairer, Norsett and Wanner. Typical examples are Fehlberg methods of order 7(8).

Also, if you are looking at solving ODEs in PYTHON, check out assimulo. I've been playing with this package for a couple of weeks and am quite happy.