Stable Simulation: Avoiding Overshoot
CS 480 Lecture,
Almost all interesting simulations involve some sort of closed-loop
feedback, where a change in A causes a change in B which in turn
affects A again.
For example, consider the velocity of an object including drag forces from air resistance.
F = -k * V
A = F/m (from F = mA)
dV / dt = A
Here F is the net force on the object, V is the object's velocity, k is
the object's wind resistance (newtons of resistance per meter per
second of velocity), A is the object's acceleration, and m is the mass.
If drag is the only force involved, and discretizing to first order, we get:
dV = (-k*dt/m) * V
V = V + (-k*dt/m) * V = V + speed * V
where we've defined speed = (-k*dt/m).
That is, the change in V itself varies with V. If that speed term
(-k*dt/m) is positive, then V will feed back on itself leading to
exponential growth. Luckily, speed is always negative because
real drag constants, timesteps, and masses are all positive. In
the theoretical non-discretized equations, a negative speed term causes
V to drop exponentially, though possibly with a managably small
exponent. A small negative speed term causes the discrete V to
also drop exponentially.
But weird stuff starts happening if the speed term gets negative enough:
Anytime speed<-2.0, V is going to spiral out of control fairly
quickly. This is similar to an inexperienced driver skidding on
ice: they steer too hard, overcorrecting the car's orientation, and end
up making the skid worse instead of better. The effect is that
the simulation "blows up", where the points have vanished off the
screen, or hit floating-point infinity or not-a-number. Not good.
- At speed=0, V doesn't change at all.
- At speed=-0.1, V shrinks by 10% per timestep.
- At speed=-0.5, V shrinks by 50% per timestep.
- At speed=-1.0, V = 0 after the first timestep.
- At speed=-1.5, V overshoots zero every timestep, ending each step 50% shorter but facing the other way.
- At speed=-2.0, V overshoots zero completely, and ends up facing exactly the opposite direction with the same magnitude.
- At speed=-2.1, V overshoots zero and gains 10% per timestep!
Note that speed = -k*dt/m, so speed is going to get out of control if:
Many simulations have
a stability limitation on the timestep. If your steps get bigger
than this, you can expect the simulation to explode.
- k, the drag coefficient, gets too big. It'd be weird that
you could simulate air, but not the slower movements expected in water
or tar, but it's quite possible.
- m, the object mass, gets too small. The drag coefficient for small objects should probably get small as well.
- dt, the timestep, gets too big. This is common, but luckily we can
adjust the simulation timestep easily, as long as our computer is fast