Verlet integration (French pronunciation:[vɛʁˈlɛ]) is a numerical method used tointegrateNewton'sequations of motion.^[1] It is frequently used to calculatetrajectories of particles inmolecular dynamics simulations andcomputer graphics. The algorithm was first used in 1791 byJean Baptiste Delambre and has been rediscovered many times since then, most recently byLoup Verlet in the 1960s for use in molecular dynamics. It was also used byP. H. Cowell andA. C. C. Crommelin in 1909 to compute the orbit ofHalley's Comet, and byCarl Størmer in 1907 to study the trajectories of electrical particles in amagnetic field (hence it is also calledStørmer's method).^[2]The Verlet integrator provides goodnumerical stability, as well as other properties that are important inphysical systems such astime reversibility andpreservation of the symplectic form on phase space, at no significant additional computational cost over the simpleEuler method.

For asecond-order differential equation of the type${\displaystyle \ddot{\mathbf{x}}(t)=\mathbf{A}(\mathbf{x}(t))}$ with initial conditions${\displaystyle \mathbf{x}(t_0)={\mathbf{x}}_0}$ and${\displaystyle \dot{\mathbf{x}}(t_0)={\mathbf{v}}_0}$, an approximate numerical solution${\displaystyle {\mathbf{x}}_n\approx \mathbf{x}(t_n)}$ at the times${\displaystyle t_n=t_0+n\mathrm{\Delta }t}$ with step size${\displaystyle \mathrm{\Delta }t>0}$ can be obtained by the following method:

1. set${\mathbf{x}}_1={\mathbf{x}}_0+{\mathbf{v}}_0\mathrm{\Delta }t+\frac{1}{2}\mathbf{A}({\mathbf{x}}_0)\mathrm{\Delta }{t}^2$,
2. forn = 1, 2, ... iterate$${\displaystyle {\mathbf{x}}_{n+1}=2{\mathbf{x}}_n-{\mathbf{x}}_{n-1}+\mathbf{A}({\mathbf{x}}_n)\mathrm{\Delta }{t}^2.}$$

Newton's equation of motion for conservative physical systems is$${\displaystyle \mathit{M}\ddot{\mathbf{x}}(t)=F(\mathbf{x}(t))=-\mathrm{\nabla }V(\mathbf{x}(t)),}$$or individually$${\displaystyle m_k{\ddot{\mathbf{x}}}_k(t)=F_k(\mathbf{x}(t))=-{\mathrm{\nabla }}_{{\mathbf{x}}_k}V\left(\mathbf{x}(t)\right),}$$where

• ${\displaystyle t}$ is the time,
• ${\displaystyle \mathbf{x}(t)=({\mathbf{x}}_1(t),\dots ,{\mathbf{x}}_N(t))}$ is the ensemble of the position vector of${\displaystyle N}$ objects,
• ${\displaystyle V}$ is thescalar potential function,
• ${\displaystyle F}$ is the negativegradient of the potential, giving the ensemble of forces on the particles,
• ${\displaystyle \mathit{M}}$ is themass matrix, typically diagonal with blocks with mass${\displaystyle m_k}$ for every particle.

This equation, for various choices of the potential function${\displaystyle V}$, can be used to describe the evolution of diverse physical systems, from the motion ofinteracting molecules to theorbit 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$${\displaystyle \ddot{\mathbf{x}}(t)=\mathbf{A}(\mathbf{x}(t))}$$with some suitable vector-valued function${\displaystyle \mathbf{A}(\mathbf{x})}$ representing the position-dependent acceleration. Typically, an initial position${\displaystyle \mathbf{x}(0)={\mathbf{x}}_0}$ and an initial velocity${\displaystyle \mathbf{v}(0)=\dot{\mathbf{x}}(0)={\mathbf{v}}_0}$ are also given.

To discretize and numerically solve thisinitial value problem, a time step${\displaystyle \mathrm{\Delta }t>0}$ is chosen, and the sampling-point sequence${\displaystyle t_n=n\mathrm{\Delta }t}$ considered. The task is to construct a sequence of points${\displaystyle {\mathbf{x}}_n}$ that closely follow the points${\displaystyle \mathbf{x}(t_n)}$ on the trajectory of the exact solution.

WhereEuler's method uses theforward difference approximation to the first derivative in differential equations of order one, Verlet integration can be seen as using thecentral difference approximation to the second derivative:

Verlet integration in the form used as theStørmer method^[3] uses this equation to obtain the next position vector from the previous two without using the velocity as

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${\displaystyle \mathrm{\Delta }t}$ of degree three. The local error is quantified by inserting the exact values${\displaystyle \mathbf{x}(t_{n-1}),\mathbf{x}(t_n),\mathbf{x}(t_{n+1})}$ into the iteration and computing theTaylor expansions at time${\displaystyle t=t_n}$ of the position vector${\displaystyle \mathbf{x}(t\pm \mathrm{\Delta }t)}$ in different time directions:where${\displaystyle \mathbf{x}}$ is the position,${\displaystyle \mathbf{v}=\dot{\mathbf{x}}}$ the velocity,${\displaystyle \mathbf{a}=\ddot{\mathbf{x}}}$ the acceleration, and${\displaystyle \mathbf{b}=\dot{\mathbf{a}}=\stackrel{\dots }{\mathbf{x}}}$ thejerk (third derivative of the position with respect to the time).

Adding these two expansions gives$${\displaystyle \mathbf{x}(t+\mathrm{\Delta }t)=2\mathbf{x}(t)-\mathbf{x}(t-\mathrm{\Delta }t)+\mathbf{a}(t)\mathrm{\Delta }{t}^2+\mathcal{O}\left(\mathrm{\Delta }{t}^4\right).}$$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,${\displaystyle \mathbf{a}(t)=\mathbf{A}(\mathbf{x}(t))}$, whereas in the iteration it is computed at the central iteration point,${\displaystyle {\mathbf{a}}_n=\mathbf{A}({\mathbf{x}}_n)}$. In computing the global error, that is the distance between exact solution and approximation sequence, those two terms do not cancel exactly, influencing the order of the global error.

To gain insight into the relation of local and global errors, it is helpful to examine simple examples where the exact solution, as well as the approximate solution, can be expressed in explicit formulas. The standard example for this task is theexponential function.

Consider the linear differential equation${\displaystyle \ddot{x}(t)=w^{2}x(t)}$ with a constant${\displaystyle w}$. Its exact basis solutions are${\displaystyle e^{wt}}$ and${\displaystyle e^{-wt}}$.

The Størmer method applied to this differential equation leads to a linearrecurrence relation$${\displaystyle x_{n+1}-2x_n+x_{n-1}=h^2{w}^2{x}_n,}$$or$${\displaystyle x_{n+1}-2\left(1+\frac{1}{2}{\left(wh\right)}^2\right)x_n+x_{n-1}=0.}$$It can be solved by finding the roots of its characteristic polynomial${\displaystyle q^2-2\left(1+\frac{1}{2}(wh{)}^2\right)q+1=0}$. These are$${\displaystyle q_{\pm }=1+\frac{1}{2}{\left(wh\right)}^2\pm wh\sqrt{1+\frac{1}{4}{\left(wh\right)}^2}.}$$The basis solutions of the linear recurrence are${\displaystyle x_n=q_{+}^n}$ and${\displaystyle x_n=q_{-}^n}$. To compare them with the exact solutions, Taylor expansions are computed:The quotient of this series with the exponential${\displaystyle e^{wh}}$ starts with${\displaystyle 1-\frac{1}{24}(wh{)}^3+\mathcal{O}\left(h^5\right)}$, soFrom there it follows that for the first basis solution the error can be computed asThat is, although the localdiscretization 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.

Note that at the start of the Verlet iteration at step${\displaystyle n=1}$, time${\displaystyle t=t_1=\mathrm{\Delta }t}$, computing${\displaystyle {\mathbf{x}}_2}$, one already needs the position vector${\displaystyle {\mathbf{x}}_1}$ at time${\displaystyle t=t_1}$. At first sight, this could give problems, because the initial conditions are known only at the initial time${\displaystyle t_0=0}$. However, from these the acceleration${\displaystyle {\mathbf{a}}_0=\mathbf{A}({\mathbf{x}}_0)}$ is known, and a suitable approximation for the position at the first time step can be obtained using theTaylor polynomial of degree two:

The error on the first time step then is of order${\displaystyle \mathcal{O}\left(\mathrm{\Delta }{t}^3\right)}$. This is not considered a problem because on a simulation over a large number of time steps, the error on the first time step is only a negligibly small amount of the total error, which at time${\displaystyle t_n}$ is of the order${\displaystyle \mathcal{O}\left(e^{L{t}_n}\mathrm{\Delta }{t}^2\right)}$, both for the distance of the position vectors${\displaystyle {\mathbf{x}}_n}$ to${\displaystyle \mathbf{x}(t_n)}$ as for the distance of the divided differences${\displaystyle \frac{{\mathbf{x}}_{n+1}-{\mathbf{x}}_n}{\mathrm{\Delta }t}}$ to${\displaystyle \frac{\mathbf{x}(t_{n+1})-\mathbf{x}(t_n)}{\mathrm{\Delta }t}}$. Moreover, to obtain this second-order global error, the initial error needs to be of at least third order.

A disadvantage of the Størmer–Verlet method is that if the time step (${\displaystyle \mathrm{\Delta }t}$) changes, the method does not approximate the solution to the differential equation. This can be corrected using the formula^[4]$${\displaystyle {\mathbf{x}}_{i+1}={\mathbf{x}}_i+\left({\mathbf{x}}_i-{\mathbf{x}}_{i-1}\right)\frac{\mathrm{\Delta }{t}_i}{\mathrm{\Delta }{t}_{i-1}}+{\mathbf{a}}_i\mathrm{\Delta }{t}_i^2.}$$

A more exact derivation uses the Taylor series (to second order) at${\displaystyle t_i}$ for times${\displaystyle t_{i+1}=t_i+\mathrm{\Delta }{t}_i}$ and${\displaystyle t_{i-1}=t_i-\mathrm{\Delta }{t}_{i-1}}$ to obtain after elimination of${\displaystyle {\mathbf{v}}_i}$$${\displaystyle \frac{{\mathbf{x}}_{i+1}-{\mathbf{x}}_i}{\mathrm{\Delta }{t}_i}+\frac{{\mathbf{x}}_{i-1}-{\mathbf{x}}_i}{\mathrm{\Delta }{t}_{i-1}}={\mathbf{a}}_i\frac{\mathrm{\Delta }{t}_i+\mathrm{\Delta }{t}_{i-1}}{2},}$$so that the iteration formula becomes$${\displaystyle {\mathbf{x}}_{i+1}={\mathbf{x}}_i+({\mathbf{x}}_i-{\mathbf{x}}_{i-1})\frac{\mathrm{\Delta }{t}_i}{\mathrm{\Delta }{t}_{i-1}}+{\mathbf{a}}_i\frac{\mathrm{\Delta }{t}_i+\mathrm{\Delta }{t}_{i-1}}{2}\mathrm{\Delta }{t}_i.}$$

The velocities are not explicitly given in the basic Størmer equation, but often they are necessary for the calculation of certainphysical quantities like thekinetic energy. This can create technical challenges inmolecular dynamics simulations, because kinetic energy and instantaneous temperatures at time${\displaystyle t}$ cannot be calculated for a system until the positions are known at time${\displaystyle t+\mathrm{\Delta }t}$. This deficiency can either be dealt with using thevelocity Verlet algorithm or by estimating the velocity using the position terms and themean value theorem:$${\displaystyle \mathbf{v}(t)=\frac{\mathbf{x}(t+\mathrm{\Delta }t)-\mathbf{x}(t-\mathrm{\Delta }t)}{2\mathrm{\Delta }t}+\mathcal{O}\left(\mathrm{\Delta }{t}^2\right).}$$

Note that this velocity term is a step behind the position term, since this is for the velocity at time${\displaystyle t}$, not${\displaystyle t+\mathrm{\Delta }t}$, meaning that${\displaystyle {\mathbf{v}}_n=\frac{{\mathbf{x}}_{n+1}-{\mathbf{x}}_{n-1}}{2\mathrm{\Delta }t}}$ is a second-order approximation to${\displaystyle \mathbf{v}(t_n)}$. With the same argument, but halving the time step,${\displaystyle {\mathbf{v}}_{n+\frac{1}{2}}=\frac{{\mathbf{x}}_{n+1}-{\mathbf{x}}_n}{\mathrm{\Delta }t}}$ is a second-order approximation to${\displaystyle \mathbf{v}\left(t_{n+1/2}\right)}$, with${\displaystyle t_{n+\frac{1}{2}}=t_n+\frac{1}{2}\mathrm{\Delta }t}$.

One can shorten the interval to approximate the velocity at time${\displaystyle t+\mathrm{\Delta }t}$ at the cost of accuracy:$${\displaystyle \mathbf{v}(t+\mathrm{\Delta }t)=\frac{\mathbf{x}(t+\mathrm{\Delta }t)-\mathbf{x}(t)}{\mathrm{\Delta }t}+\mathcal{O}(\mathrm{\Delta }t).}$$

A related, and more commonly used algorithm is the velocity Verlet algorithm,^[5] similar to theleapfrog 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 problem of the first time step in the basic Verlet algorithm:

It can be shown that the error in the velocity Verlet is of the same order as in the basic Verlet. Note that the velocity algorithm is not necessarily more memory-consuming, because, in basic Verlet, we keep track of two vectors of position, while in velocity Verlet, we keep track of one vector of position and one vector of velocity. The standard implementation scheme of this algorithm is:

1. Calculate${\displaystyle \mathbf{v}\left(t+\frac{1}{2}\mathrm{\Delta }t\right)=\mathbf{v}(t)+\frac{1}{2}\mathbf{a}(t)\mathrm{\Delta }t}$.
2. Calculate${\displaystyle \mathbf{x}(t+\mathrm{\Delta }t)=\mathbf{x}(t)+\mathbf{v}\left(t+\frac{1}{2}\mathrm{\Delta }t\right)\mathrm{\Delta }t}$.
3. Derive${\displaystyle \mathbf{a}(t+\mathrm{\Delta }t)}$ from the interaction potential using${\displaystyle \mathbf{x}(t+\mathrm{\Delta }t)}$.
4. Calculate${\displaystyle \mathbf{v}(t+\mathrm{\Delta }t)=\mathbf{v}\left(t+\frac{1}{2}\mathrm{\Delta }t\right)+\frac{1}{2}\mathbf{a}(t+\mathrm{\Delta }t)\mathrm{\Delta }t}$.

This algorithm also works with variable time steps, and is identical to the 'kick-drift-kick' form ofleapfrog method integration.

Eliminating the half-step velocity, this algorithm may be shortened to

1. Calculate${\displaystyle \mathbf{x}(t+\mathrm{\Delta }t)=\mathbf{x}(t)+\mathbf{v}(t)\mathrm{\Delta }t+\frac{1}{2}\mathbf{a}(t)\mathrm{\Delta }{t}^2}$.
2. Derive${\displaystyle \mathbf{a}(t+\mathrm{\Delta }t)}$ from the interaction potential using${\displaystyle \mathbf{x}(t+\mathrm{\Delta }t)}$.
3. Calculate${\displaystyle \mathbf{v}(t+\mathrm{\Delta }t)=\mathbf{v}(t)+\frac{1}{2}(\mathbf{a}(t)+\mathbf{a}(t+\mathrm{\Delta }t))\mathrm{\Delta }t}$.

Note, however, that this algorithm assumes that acceleration${\displaystyle \mathbf{a}(t+\mathrm{\Delta }t)}$ only depends on position${\displaystyle \mathbf{x}(t+\mathrm{\Delta }t)}$ and does not depend on velocity${\displaystyle \mathbf{v}(t+\mathrm{\Delta }t)}$.

One might note that the long-term results of velocity Verlet, and similarly of leapfrog are one order better than thesemi-implicit Euler method. The algorithms are almost identical up to a shift by half a time step in the velocity. This can be 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 themidpoint method, of order two. Additionally, if the acceleration indeed results from the forces in a conservative mechanical orHamiltonian 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 conserved quantities of the system like linear orangular momentum, that are always preserved or nearly preserved in asymplectic integrator.^[6]

The velocity Verlet method is a special case of theNewmark-beta method with${\displaystyle \beta =0}$ and$\gamma =\frac{1}{2}$.

Sincevelocity Verlet is a generally useful algorithm in 3D applications, a solution written in C++ could look like below. This type of position integration will significantly increase accuracy in 3D simulations and games when compared with the regular Euler method.

structBody{Vec3dpos{0.0,0.0,0.0};Vec3dvel{2.0,0.0,0.0};// 2 m/s along x-axisVec3dacc{0.0,0.0,0.0};// no acceleration at firstdoublemass=1.0;// 1kg/**     * Updates pos and vel using "Velocity Verlet" integration     * @param dt DeltaTime / time step [eg: 0.01]     */voidupdate(doubledt){Vec3dnew_pos=pos+vel*dt+acc*(dt*dt*0.5);Vec3dnew_acc=apply_forces();Vec3dnew_vel=vel+(acc+new_acc)*(dt*0.5);pos=new_pos;vel=new_vel;acc=new_acc;}/**     * To apply velocity to your objects, calculate the required Force vector instead     * and apply the accumulated forces here.     */Vec3dapply_forces()const{Vec3dnew_acc=Vec3d{0.0,0.0,-9.81};// 9.81 m/s² down in the z-axis// Apply any other forces here...// NOTE: Avoid depending on `vel` because Velocity Verlet assumes acceleration depends on position.returnnew_acc;}};

The global truncation error of the Verlet method is${\displaystyle \mathcal{O}\left(\mathrm{\Delta }{t}^2\right)}$, both for position and velocity.This is in contrast with the fact that the local error in position is only${\displaystyle \mathcal{O}\left(\mathrm{\Delta }{t}^4\right)}$ as described above. The difference is due to the accumulation of the local truncation error over all of the iterations.

The global error can be derived by noting the following:

$${\displaystyle \mathrm{error}(x(t_0+\mathrm{\Delta }t))=\mathcal{O}\left(\mathrm{\Delta }{t}^4\right)}$$

and

$${\displaystyle x(t_0+2\mathrm{\Delta }t)=2x(t_0+\mathrm{\Delta }t)-x(t_0)+\mathrm{\Delta }{t}^2\ddot{x}(t_0+\mathrm{\Delta }t)+\mathcal{O}\left(\mathrm{\Delta }{t}^4\right).}$$

Therefore

$${\displaystyle \mathrm{error}(x(t_0+2\mathrm{\Delta }t))=2\cdot \mathrm{error}(x(t_0+\mathrm{\Delta }t))+\mathcal{O}\left(\mathrm{\Delta }{t}^4\right)=3\mathcal{O}\left(\mathrm{\Delta }{t}^4\right).}$$

Similarly:

which can be generalized to (it can be shown by induction, but it is given here without proof):

$${\displaystyle \mathrm{error}(x(t_0+n\mathrm{\Delta }t))=\frac{n(n+1)}{2}\mathcal{O}\left(\mathrm{\Delta }{t}^4\right).}$$

If we consider the global error in position between${\displaystyle x(t)}$ and${\displaystyle x(t+T)}$, where${\displaystyle T=n\mathrm{\Delta }t}$, it is clear that^{[citation needed]}

$${\displaystyle \mathrm{error}(x(t_0+T))=\left(\frac{T^2}{2\mathrm{\Delta }{t}^2}+\frac{T}{2\mathrm{\Delta }t}\right)\mathcal{O}\left(\mathrm{\Delta }{t}^4\right),}$$

and therefore, the global (cumulative) error over a constant interval of time is given by

$${\displaystyle \mathrm{error}(x(t_0+T))=\mathcal{O}\left(\mathrm{\Delta }{t}^2\right).}$$

Because the velocity is determined in a non-cumulative way from the positions in the Verlet integrator, the global error in velocity is also${\displaystyle \mathcal{O}\left(\mathrm{\Delta }{t}^2\right)}$.

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.

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 assprings 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${\displaystyle {\tilde{x}}_i^{(t)}}$ and the actual positions${\displaystyle x_i^{(t)}}$ of points${\displaystyle i}$ at time${\displaystyle t}$, given a desired constraint distance of${\displaystyle r}$, can be found with the algorithm

Verlet integration is useful because it directly relates the force to the position, rather than solving the problem using 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 theGauss–Seidel method. For smallmatrices it is known thatLU decomposition is faster. Large systems can be divided into clusters (for example, eachragdoll = cluster). Inside clusters the LU method is used, between clusters theGauss–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^[7] 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 asound wave.^[8]

Another way to solveholonomic constraints is to useconstraint algorithms.

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 by the collision in the latter case; however, note that this is not guaranteed to do so in a way that is consistent withcollision 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 perfectlyelastic andinelastic collisions. A slightly more complicated strategy that offers more control would involve using thecoefficient of restitution.

• Courant–Friedrichs–Lewy condition
• Energy drift
• Symplectic integrator
• Leapfrog integration
• Beeman's algorithm

• Verlet Integration Demo and Code as a Java Applet
• Advanced Character Physics by Thomas Jakobsen
• Theory of Molecular Dynamics SimulationsArchived 2006-04-26 at theWayback Machine – bottom of page
• Verlet integration implemented in modern JavaScript – bottom of page

• Time reversible numerical differential equations
• Computational physics
• Molecular dynamics

• Webarchive template wayback links
• CS1: long volume value
• Articles with short description
• Short description is different from Wikidata
• Pages with French IPA
• All articles with unsourced statements
• Articles with unsourced statements from July 2018
• Articles with example C++ code