Verlet integration ([vɛʁˈlɛ]) is a numerical method used to integrate Newton's equations of motion. It is frequently used to calculate trajectories of particles in molecular dynamics simulations and computer graphics. The algorithm was first used in 1791 by Delambre, and has been rediscovered many times since then, most recently by Loup Verlet in the 1960s for use in molecular dynamics. It was also used by Cowell and Crommelin in 1909 to compute the orbit of Halley's Comet, and by Carl Størmer in 1907 to study the trajectories of electrical particles in a magnetic field (hence it is also called Störmer's method). The Verlet integrator provides good numerical stability, as well as other properties that are important in physical systems such as time-reversibility and preservation of the symplectic form on phase space, at no significant additional computational cost over the simple Euler method.
Contents
Basic Störmer–Verlet
For a differential equation of second order of the type
Equations of motion
Newton's equation of motion for conservative physical systems is
or individually
where
This equation, for various choices of the potential function V, can be used to describe the evolution of diverse physical systems, from the motion of interacting molecules to the orbit of the planets.
After a transformation to bring the mass to the right side and forgetting the structure of multiple particles, the equation may be simplified to
with some suitable vector valued function A representing the position dependent acceleration. Typically, an initial position
Verlet integration (without velocities)
To discretize and numerically solve this initial value problem, a time step
Where Euler's method uses the forward difference approximation to the first derivative in differential equations of order one, Verlet Integration can be seen as using the central difference approximation to the second derivative:
Verlet integration in the form used as the Störmer method uses this equation to obtain the next position vector from the previous two without using the velocity as
Discretization error
The time symmetry inherent in the method reduces the level of local errors introduced into the integration by the discretization by removing all odd degree terms, here the terms in
where
Adding these two expansions gives
We can see that the first and third-order terms from the Taylor expansion cancel out, thus making the Verlet integrator an order more accurate than integration by simple Taylor expansion alone.
Caution should be applied to the fact that the acceleration here is computed from the exact solution,
A simple example
To gain insight into the relation of local and global errors it is helpful to examine simple examples where the exact as well as the approximative solution can be expressed in explicit formulas. The standard example for this task is the exponential function.
Consider the linear differential equation
The Störmer method applied to this differential equation leads to a linear recurrence relation
It can be solved by finding the roots of its characteristic polynomial
The basis solutions of the linear recurrence are
The quotient of this series with the one of the exponential
From there it follows that for the first basis solution the error can be computed as
That is, although the local discretization error is of order 4, due to the second order of the differential equation the global error is of order 2, with a constant that grows exponentially in time.
Starting the iteration
Note that at the start of the Verlet-iteration at step
The error on the first time step calculation then is of order
Non-constant time differences
A disadvantage of the Störmer–Verlet method is that if the time-step (
A more exact derivation uses the Taylor series (to second order) at
so that the iteration formula becomes
Computing velocities – Störmer–Verlet method
The velocities are not explicitly given in the basic Störmer equation, but often they are necessary for the calculation of certain physical quantities like the kinetic energy. This can create technical challenges in molecular dynamics simulations, because kinetic energy and instantaneous temperatures at time
Note that this velocity term is a step behind the position term, since this is for the velocity at time
One can shorten the interval to approximate the velocity at time
Velocity Verlet
A related, and more commonly used, algorithm is the Velocity Verlet algorithm, similar to the leapfrog method, except that the velocity and position are calculated at the same value of the time variable (Leapfrog does not, as the name suggests). This uses a similar approach but explicitly incorporates velocity, solving the first-timestep problem in the Basic Verlet algorithm:
It can be shown that the error on the Velocity Verlet is of the same order as the Basic Verlet. Note that the Velocity algorithm is not necessarily more memory consuming, because it's not necessary to keep track of the velocity at every timestep during the simulation. The standard implementation scheme of this algorithm is:
- Calculate:
v → ( t + 1 2 Δ t ) = v → ( t ) + 1 2 a → ( t ) Δ t . - Calculate:
x → ( t + Δ t ) = x → ( t ) + v → ( t + 1 2 Δ t ) Δ t . - Derive
a → ( t + Δ t ) from the interaction potential usingx → ( t + Δ t ) . - Calculate:
v → ( t + Δ t ) = v → ( t + 1 2 Δ t ) + 1 2 a → ( t + Δ t ) Δ t .
Eliminating the half-step velocity, this algorithm may be shortened to
- Calculate:
x → ( t + Δ t ) = x → ( t ) + v → ( t ) Δ t + 1 2 a → ( t ) Δ t 2 - Derive
a → ( t + Δ t ) from the interaction potential usingx → ( t + Δ t ) . - Calculate:
v → ( t + Δ t ) = v → ( t ) + 1 2 ( a → ( t ) + a → ( t + Δ t ) ) Δ t .
Note, however, that this algorithm assumes that acceleration
One might note that the long-term results of Velocity Verlet, and similarly of Leapfrog are one order better than the semi-implicit Euler method. The algorithms are almost identical up to a shifted by half of a timestep in the velocity. This is easily proven by rotating the above loop to start at Step 3 and then noticing that the acceleration term in Step 1 could be eliminated by combining Steps 2 and 4. The only difference is that the midpoint velocity in velocity Verlet is considered the final velocity in semi-implicit Euler method.
The global error of all Euler methods is of order one, whereas the global error of this method is, similar to the midpoint method, of order two. Additionally, if the acceleration indeed results from the forces in a conservative mechanical or Hamiltonian system, the energy of the approximation essentially oscillates around the constant energy of the exactly solved system, with a global error bound again of order one for semi-explicit Euler and order two for Verlet-leapfrog. The same goes for all other conservered quantities of the system like linear or angular momentum, that are always preserved or nearly preserved in a symplectic integrator.
The Velocity Verlet method is a special case of the Newmark-beta method with
Error terms
The local error in position of the Verlet integrator is
The global error in position, in contrast, is
and
Therefore:
Similarly:
Which can be generalized to (it can be shown by induction, but it is given here without proof):
If we consider the global error in position between
And therefore, the global (cumulative) error over a constant interval of time is given by:
Because the velocity is determined in a non-cumulative way from the positions in the Verlet integrator, the global error in velocity is also
In molecular dynamics simulations, the global error is typically far more important than the local error, and the Verlet integrator is therefore known as a second-order integrator.
Constraints
Systems of multiple particles with constraints are simpler to solve with Verlet integration than with Euler methods. Constraints between points may be for example potentials constraining them to a specific distance or attractive forces. They may be modeled as springs connecting the particles. Using springs of infinite stiffness, the model may then be solved with a Verlet algorithm.
In one dimension, the relationship between the unconstrained positions
Verlet integration is useful because it directly relates the force to the position, rather than solving the problem via velocities.
Problems, however, arise when multiple constraining forces act on each particle. One way to solve this is to loop through every point in a simulation, so that at every point the constraint relaxation of the last is already used to speed up the spread of the information. In a simulation this may be implemented by using small time steps for the simulation, using a fixed number of constraint solving steps per time step, or solving constraints until they are met by a specific deviation.
When approximating the constraints locally to first order this is the same as the Gauss–Seidel method. For small matrices it is known that LU decomposition is faster. Large systems can be divided into clusters (for example: each ragdoll = cluster). Inside clusters the LU method is used, between clusters the Gauss–Seidel method is used. The matrix code can be reused: The dependency of the forces on the positions can be approximated locally to first order, and the Verlet integration can be made more implicit.
Sophisticated software, such as SuperLU [1] exists to solve complex problems using sparse matrices. Specific techniques, such as using (clusters of) matrices, may be used to address the specific problem, such as that of force propagating through a sheet of cloth without forming a sound wave.
Another way to solve holonomic constraints is to use constraint algorithms.
Collision reactions
One way of reacting to collisions is to use a penalty-based system which basically applies a set force to a point upon contact. The problem with this is that it is very difficult to choose the force imparted. Use too strong a force and objects will become unstable, too weak and the objects will penetrate each other. Another way is to use projection collision reactions which takes the offending point and attempts to move it the shortest distance possible to move it out of the other object.
The Verlet integration would automatically handle the velocity imparted via the collision in the latter case, however note that this is not guaranteed to do so in a way that is consistent with collision physics (that is, changes in momentum are not guaranteed to be realistic). Instead of implicitly changing the velocity term, one would need to explicitly control the final velocities of the objects colliding (by changing the recorded position from the previous time step).
The two simplest methods for deciding on a new velocity are perfectly elastic collisions and inelastic collisions. A slightly more complicated strategy that offers more control would involve using the coefficient of restitution.