Skip to main content
GameDev.net gamedev.net
🔒 Locked

Runge-Kutta unstable in some situations?

Started by cragwolf Apr 13, 2006 at 5:46 AM 6 replies 7.8k views
Original Post
cragwolf
cragwolf
I've been testing out a few integration methods: Standard Euler, Symplectic Euler (or NSV), Velocity Verlet, and Fourth-Order Runge-Kutta. I tested them on the example of the Earth orbiting the Sun. I assumed a circular orbit. I found, as expected, that standard Euler did not fare very well. Its orbits spiralled out very quickly, especially for large timesteps. Enough said about it. Symplectic Euler and Velocity Verlet did very well. At a timestep resolution of 20 steps per year -- in other words a large timestep even on the planetary scale -- I noticed that these methods oscillated with regards to the distance of the Earth from the Sun: Symplectic Euler oscillated between about 0.8 AU and 1.2 AU, while Velocity Verlet oscillated between about 0.96 and 1.04 AU. But they both appeared to remain in stable orbits (slightly elliptical precessing orbits to be more exact). For small timesteps, these oscillations were much smaller, barely detectable. Runge-Kutta on the other hand was weird. It was supremely accurate for small timesteps. But for large timesteps it very slowly and then more rapidly spiralled in towards the Sun, and then of course got ejected from the Solar System! At a timestep resolution of 20 steps per year, the Earth got ejected after about 250 orbits. Probably even for small timesteps this would happen, but only after much more than 250 orbits, but I couldn't be bothered waiting that long. I would have thought that Runge-Kutta would be the most accurate and most stable of these methods. It initially is more accurate but after a while it spirals in towards the Sun. Maybe my initial thought was wrong, and Runge-Kutta is less stable than Symplectic Euler and Velocity Verlet, at least in the example of the periodic motion of planetary orbits. Does anyone know? Here's some screenshots of my experiments. These show all four methods on the one screen. The examples are all with a timestep resolution of 20 steps per year. The first one is the only one that shows Standard Euler Earth in the frame. The second one shows that Runge-Kutta Earth has indeed started to spiral in towards the Sun. The third one has captured Runge-Kutta Earth just before it will get too close to the Sun and get ejected out of the Solar System. Screenshot 1 Screenshot 2 Screenshot 3
Metorical
Metorical
Sorry if you know any/all of this already.

In numerical methods accuracy and stability are too different things. Typically the stability of a method depends on the type of equation you are solving. I don't have my old notes but a bit of digging I found this:

http://www.mast.queensu.ca/~math272/Slides/Week_08/Week_08_ODE_2.pdf

Which has nice sections on the methods and stabilities. Hopefully this is the problem although if you still have issues can you post your equations?

Edit:

In addition you can have accurate but unstable solutions *and* inaccurate but stable solutions.
Trap
Trap
Oscillating systems are prone to such behaviour, especially when they are highly symmetric. The solver always errs in the same direction and errors accumulate over time.
SigKILL
SigKILL
If I remember my physics correct the orbit is determined by kinetic and potential energy (possibly wrong). Since sympletic euler is partly dependent on some implicit solution and verlets are basicly an energy preserving version of euler integration, the result is probably what you might expect (i.e. small loss of kinetic energy using rk4, and no loss in sympletic euler and verlet). Intuitively there is some error in verlet and sympletic euler integration, but the earth is pushed/pulled back into orbit since the energy stays the same.
John Schultz
John Schultz
Given the nature of your simulation, you might enjoy, Geometric Numerical Integration Structure-Preserving Algorithms for Ordinary Differential Equations alot.

For example (from the book), there are symplectic forms of RK as well as other methods that you might find useful (though from your images, velocity Verlet looks pretty good). Thus, with more complexity/work, it's probably possible to increase the accuracy while maintaining stability using the concepts from Hairier et al's book. It would be cool to see the results of your work if you can make that happen (not aware of any game/sim related work in that area).

As stated previously, RK is reasonably stable (unstable typically means "explodes easily", as with explicit Euler), but loses energy, and effectively "low-pass filters" the motion (also requires 4 derivs per step; perhaps not an issue for your problem set).

It is amazing that NSV/Velocity-Verlet work so well given their simplicity.
cragwolf
cragwolf
Thanks for the replies. The method I called "Symplectic Euler" is actually just a reverse or backwards Euler:

v += a(t)*dtx += v*dt


What is the proper terminology for this method? And what is NSV?
John Schultz
John Schultz
Quote:
Original post by cragwolf
Thanks for the replies. The method I called "Symplectic Euler" is actually just a reverse or backwards Euler:

v += a(t)*dtx += v*dt


What is the proper terminology for this method? And what is NSV?


Backwards Euler is an implicit method (must solve a system of equations, very stable, loses (alot of) energy).

NSV = Newton-Störmer-Verlet (named in order of (re)discovery), AKA Semi-Implicit Euler, AKA Symplectic Euler. I now just use NSV (keep in mind there are many variants on the theme, including Velocity Verlet). See the Hairer (NSV) link for more info.
cragwolf
cragwolf
Thanks again for the info and the references. I guess you could view backwards Euler as a kind of simplified NSV method. Isn't it amazing that in 1687 Isaac Newton used a form of NSV in his Principia? We're only 319 years behind. [wink]

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.