Btw, I''m not interested in hearing about Verlet or implicit methods
- Mikko Kauppila
Euler, Runge-Kutta and stability
Author
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 (and collision consistency).
So I thought, why not just take 2-4 midpoint method iterations or 1-2 RK4 iterations?
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?
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: but is the time step limit still the same?
OK buddies, thanks in advance Btw, I''m not interested in hearing about Verlet or implicit methods
- Mikko Kauppila
Btw, I''m not interested in hearing about Verlet or implicit methods
- Mikko Kauppila
The Euler method is inherently unstable. So are the RK methods, but the benefits of using RK4 are greater than simply taking four Euler steps of size h/4 - it should be, otherwise there wouldn''t be much point in using it and everyone would just be using Euler''s method with smaller steps
[teamonkey]
[teamonkey]
Author
Hi teamonkey, thanks for your answer.
>it should be, otherwise there wouldn''t be much point in
>using it and everyone would just be using Euler''s method
>with smaller steps
Well, there is point in using RK4 instead of h/4 Euler steps: a greater *accuracy*.
But that doesn''t necessarily imply better *stability*.
In computer graphics the sparse discretizations of mass-spring systems already guarantee that we''re not going to get the exactly correct answer, so the accuracy of RK4 isn''t crucial. What is crucial, however, is the stability.
I was just thinking if it can be shown mathematically that RK4 is generally more stable than h/4 Euler steps. Does anyone know any theory behind this?
- Mikko Kauppila
>it should be, otherwise there wouldn''t be much point in
>using it and everyone would just be using Euler''s method
>with smaller steps
Well, there is point in using RK4 instead of h/4 Euler steps: a greater *accuracy*.
But that doesn''t necessarily imply better *stability*.
In computer graphics the sparse discretizations of mass-spring systems already guarantee that we''re not going to get the exactly correct answer, so the accuracy of RK4 isn''t crucial. What is crucial, however, is the stability.
I was just thinking if it can be shown mathematically that RK4 is generally more stable than h/4 Euler steps. Does anyone know any theory behind this?
- Mikko Kauppila
Check out http://www.cs.unc.edu/~luv/courses/unc/comp259/hw1/
Scroll down to the "Spring-mass system" stuff. Compare plots for time steps of 0.1 s, 0.5 s and 1.0 s. The Euler is unstable in all, the RK4 stable in all.
Note that this certainly isn''t a proof, and might be dependent on the step size being a multiple of a resonant frequency, especially in the 0.1 s case. It does, however, seem to indicate that RK4 is better than 4 smaller euler steps.
Scroll down to the "Spring-mass system" stuff. Compare plots for time steps of 0.1 s, 0.5 s and 1.0 s. The Euler is unstable in all, the RK4 stable in all.
Note that this certainly isn''t a proof, and might be dependent on the step size being a multiple of a resonant frequency, especially in the 0.1 s case. It does, however, seem to indicate that RK4 is better than 4 smaller euler steps.
quote:Original post by teamonkey
The Euler method is inherently unstable. So are the RK methods...
Actually, they are conditionally stable, meaning they work well as long as you don''t exceed the stability limits. The (explicit) Euler method is unstable when there are springs---of ANY stiffness even soft ones unless you also add damping. Even then time step must be small enough to avoid instability.
RK methods are better than (explicit) Euler in two ways. First, they are stable for systems with springs even without damping. But you still have to limit the time step. But the time step is not quite as limited as with (explicit) Euler.
I''ve been writing (explicit) Euler because there is another method called implicit Euler. This method is unconditionally stable for problems which are physically stable. It is an A-stable method, and can even handle physical situations, such as systems where energy is added to the system by external forces, that are naturally unstable---meaning you can stably simulate unstable real-world situations using implicit Euler. Sound weird. But true.
Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
