Euler, Runge-Kutta and stability


uutee
07-07-2003, 08:05 PM
Hiya folks,

I have a little interactive physics simulator with springs (stiff ones) up and running. At the moment I'm using Euler's (or Euler's-Cromer's) method.

I'm doing several (4 to 8) small Euler steps per frame to ensure stability.

So I thought, why not just take 2 to 4 midpoint method iterations or 1 to 2 RK4 iterations instead?

Clearly this would give much better results considering *accuracy*, but what about *stability*?

So here is __The__Main__Question__ of this post: Is taking one RK4 step generally more stable than taking four small Euler steps? (Notice that I'm considering systems of connected springs, not just a single pendulum).

I know that in some problems, diffusion and advection problems for example, the time step limit on the Euler method can be understood intuitively (ie. values can't propagate over one neighbor). In this light, using RK4 instead of Euler doesn't seem that big a boost, because RK4 can be understood as several averaged Euler steps: so is the time step limit still the same?

OK buddies, thanks in advance. Btw, I'm not interested in hearing about Verlet integration or implicit methods (I've tried them both and would eagerly like to try something new).

- Mikko Kauppila

hernlund
07-18-2003, 02:43 AM
It's always good to remember that "order" and stability are two different things. For example, implicit schemes get you unconditional stability, but the accuracy can be very limited.

The stability criterion of most explicit grid based schemes usually leads right back to the Courant-Friedrichs-Levy limit, where information should not be transfered at a rate higher than the grid may represent.
You can some times explain it best by considering numerical diffusion. Numerical diffusion can be seen by doing a truncation analysis, i.e. expanding the terms in your numerical scheme in a Taylor series to higher order and looking at the first several truncated terms. These show you what equation you are actually solving, and what sorts of terms are creeping in to the solution. These are often diffusive in nature, and have coefficients that depend (of course) on the time and space discretization. If the time step is too large (i.e. larger than the CFL limit) then you'll see negative diffusion terms showing up in the truncation errors. Negative diffusion is quite unstable, growing all sorts of modes at an exponential rate. This is why things blow up.

Don't be afraid to do some truncation or stability analyses...they actually are fairly simple to do, and you can learn a lot about each scheme by doing so.

The best thing to do is to think about ways to estimate the truncation error, and use that as a threshold, along with an adaptive time step size, to control the errors in your calculations. For decent accuracy in such a simple code, you shouldn't be anywhere near the CFL limit. Runge-Kutta is very inexpensive computationally, exceptionally easy to program, and these days you can choose your time steps to be of the same order as the machine precision without making the CPU work very hard.

Good luck!
John

movax
09-03-2005, 04:22 PM
Originally posted by uutee
So here is __The__Main__Question__ of this post: Is taking one RK4 step generally more stable than taking four small Euler steps? (Notice that I'm considering systems of connected springs, not just a single pendulum).

I know that in some problems, diffusion and advection problems for example, the time step limit on the Euler method can be understood intuitively (ie. values can't propagate over one neighbor). In this light, using RK4 instead of Euler doesn't seem that big a boost, because RK4 can be understood as several averaged Euler steps: so is the time step limit still the same?

No, no, no!!!!

Four Euler h/4 step in not equal to one RK4 h step.

If you want to have same accuracy as in 1 RK4 h step , you need about 30 h^4 steps in Euler. RK4 have error about o(h^4), Euler o(h). See RK4 evaluates functions f 4 times, it takes the same time that 4 Euler smaller steps, but error in RK4 is MUCH much smaller.

Ie. step 0.01 in RK4 will give the same (aproximetly) error as 0.00000001 step in Euler.

http://smp.if.uj.edu.pl/~baryluk/mn/projekt6.pdf
Page 5, Picture 1.

Even when we will decres step in Euler method about 4000 times (from 1/80, to 1/327680), we will dont have better accuracy than RK4 with 1/80 step.
You can also see next tables 1 and 2, for comparision. Ie. RK4

Sorry for my english, and mistakes.

hernlund
09-04-2005, 04:41 PM
I believe he was asking about stability, not accuracy.

You are correct to note that order and accuracy are not the same thing.

Cheers!
John