11
$\begingroup$

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?

$\endgroup$

migrated from stackoverflow.com Feb 23 '12 at 13:49

This question came from our site for professional and enthusiast programmers.

  • $\begingroup$ Research "memorization". You can easily "wrap" your f(x,y) so that the results are memoized. $\endgroup$ – S.Lott Jan 23 '12 at 15:11
  • 2
    $\begingroup$ @S.Lott: The term is "memoization", without the "r". $\endgroup$ – Dietrich Epp Jan 23 '12 at 15:17
  • 1
    $\begingroup$ @DietrichEpp: Totally Correct. Mac OS X has a new, aggressive spell-checker with no technical savvy at all. $\endgroup$ – S.Lott Jan 23 '12 at 15:59
  • $\begingroup$ Is this a 2nd order system simulated with a 4th order method? $\endgroup$ – ja72 Jan 23 '12 at 16:41
  • $\begingroup$ Here's a huge list of alternative solutions: google.com/… Any one of them is probably going to be helpful. $\endgroup$ – S.Lott Jan 23 '12 at 17:04
8
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I should probably be a little more specific. See Butcher for more details: Butcher, J.C., and J. Wiley. Numerical Methods for Ordinary Differential Equations. Wiley Online Library, 2008. Excellent reference for ODE solutions, and also provides lots of nonexistence proofs for RK methods (e.g. there does not exist order 5 Runge-Kutta method which uses only 4 function evaluations.) $\endgroup$ – Reid.Atcheson Feb 23 '12 at 21:23
  • 1
    $\begingroup$ For completeness: your claims are not true for "general Runge-Kutta methods" but only for explicit Runge-Kutta methods. $\endgroup$ – David Ketcheson Feb 24 '12 at 8:54
  • $\begingroup$ Whoops! You're right, sorry about that. $\endgroup$ – Reid.Atcheson Feb 25 '12 at 0:59
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.