Leapfrog integration

Short description: Mathematics concept

In numerical analysis, leapfrog integration is a method for numerically integrating differential equations of the form x¨=d2xdt2=A(x), or equivalently of the form v˙=dvdt=A(x),x˙=dxdt=v, particularly in the case of a dynamical system of classical mechanics.

The method is known by different names in different disciplines. In particular, it is similar to the velocity Verlet method, which is a variant of Verlet integration. Leapfrog integration is equivalent to updating positions x(t) and velocities v(t)=x˙(t) at different interleaved time points, staggered in such a way that they "leapfrog" over each other.

Leapfrog integration is a second-order method, in contrast to Euler integration, which is only first-order, yet requires the same number of function evaluations per step. Unlike Euler integration, it is stable for oscillatory motion, as long as the time-step Δt is constant, and Δt≤2/ω.[1]

Using Yoshida coefficients, applying the leapfrog integrator multiple times with the correct timesteps, a much higher order integrator can be generated.

## Contents

* 1 Algorithm
* 2 Yoshida algorithms
* 2.1 4th order Yoshida integrator
* 3 See also
* 4 References
* 5 External links

## Algorithm

In leapfrog integration, the equations for updating position and velocity are

ai=A(xi),vi+1/2=vi−1/2+aiΔt,xi+1=xi+vi+1/2Δt,

where xi is position at step i, vi+1/2 is the velocity, or first derivative of x, at step i+1/2, ai=A(xi) is the acceleration, or second derivative of x, at step i, and Δt is the size of each time step. These equations can be expressed in a form that gives velocity at integer steps as well:[2]

xi+1=xi+viΔt+12aiΔt2,vi+1=vi+12(ai+ai+1)Δt.

However, in this synchronized form, the time-step Δt must be constant to maintain stability.[3]

The synchronised form can be re-arranged to the 'kick-drift-kick' form;

vi+1/2=vi+aiΔt2,xi+1=xi+vi+1/2Δt,vi+1=vi+1/2+ai+1Δt2,

which is primarily used where variable time-steps are required. The separation of the acceleration calculation onto the beginning and end of a step means that if time resolution is increased by a factor of two (Δt->Δt/2), then only one extra (computationally expensive) acceleration calculation is required.

One use of this equation is in gravity simulations, since in that case the acceleration depends only on the positions of the gravitating masses (and not on their velocities), although higher-order integrators (such as Runge–Kutta methods) are more frequently used.

There are two primary strengths to leapfrog integration when applied to mechanics problems. The first is the time-reversibility of the Leapfrog method. One can integrate forward n steps, and then reverse the direction of integration and integrate backwards n steps to arrive at the same starting position. The second strength is its symplectic nature, which sometimes allows for the conservation of a (slightly modified) energy of a dynamical system (only true for certain simple systems). This is especially useful when computing orbital dynamics, as many other integration schemes, such as the (order-4) Runge–Kutta method, do not conserve energy and allow the system to drift substantially over time.

Because of its time-reversibility, and because it is a symplectic integrator, leapfrog integration is also used in Hamiltonian Monte Carlo, a method for drawing random samples from a probability distribution whose overall normalization is unknown.[4]

## Yoshida algorithms

The leapfrog integrator can be converted into higher order integrators using techniques due to Haruo Yoshida. In this approach, the leapfrog is applied over a number of different timesteps. It turns out that when the correct timesteps are used in sequence, the errors cancel and far higher order integrators can be easily produced.[5][6]

### 4th order Yoshida integrator

One step under the 4th order Yoshida integrator requires four intermediary steps. The position and velocity are computed at different times. Only three (computationally expensive) acceleration calculations are required.

The equations for the 4th order integrator to update position and velocity are

xi1=xi+c1viΔt,vi1=vi+d1a(xi1)Δt,xi2=xi1+c2vi1Δt,vi2=vi1+d2a(xi2)Δt,xi3=xi2+c3vi2Δt,vi3=vi2+d3a(xi3)Δt,xi+1≡xi4=xi3+c4vi3Δt,vi+1≡vi4=vi3

where xi,vi are the starting position and velocity, xin,vin are intermediary position and velocity at intermediary step n, a(xin) is the acceleration at the position xin, and xi+1,vi+1 are the final position and velocity under one 4th order Yoshida step.

Coefficients (c1,c2,c3,c4) and (d1,d2,d3) are derived in [6] (see the equation (4.6))

w0≡−232−23,w1≡12−23,c1=c4≡w12,c2=c3≡w0+w12,d1=d3≡w1,d2≡w0

All intermediary steps form one Δt step which implies that coefficients sum up to one: ∑i=14ci=1 and ∑i=13di=1. Please note that position and velocity are computed at different times and some intermediary steps are backwards in time. To illustrate this, we give the numerical values of cn coefficients: c1=0.6756, c2=−0.1756, c3=−0.1756, c4=0.6756.

## See also

* Numerical methods for ordinary differential equations
* Symplectic integration
* Euler integration
* Verlet integration
* Runge–Kutta integration

## References

1. ↑ C. K. Birdsall and A. B. Langdon, Plasma Physics via Computer Simulations, McGraw-Hill Book Company, 1985, p. 56.
2. ↑ 4.1 Two Ways to Write the Leapfrog
3. ↑ Skeel, R. D., "Variable Step Size Destabilizes the Stömer/Leapfrog/Verlet Method", BIT Numerical Mathematics, Vol. 33, 1993, p. 172–175.
4. ↑ Bishop, Christopher (2006). Pattern Recognition and Machine Learning. New York: Springer-Verlag. pp. 548–554. ISBN 978-0-387-31073-2.
5. ↑ "./Ch07.HTML". http://www.artcompsci.org/kali/vol/two_body_problem_2/ch07.html#rdocsect46.
6. ↑ 6.0 6.1 Yoshida, Haruo (1990). "Construction of higher order symplectic integrators". Physics Letters A 150 (5–7): 262–268. doi:10.1016/0375-9601(90)90092-3.

## External links

* [1], Drexel University Physics

* v
* t
* e

Numerical methods for integration

First-order methods|

* Euler method
* Backward Euler
* Semi-implicit Euler
* Exponential Euler

Second-order methods|

* Verlet integration
* Velocity Verlet
* Trapezoidal rule
* Beeman's algorithm
* Midpoint method
* Heun's method
* Newmark-beta method
* Leapfrog integration

Higher-order methods|

* Exponential integrator
* Runge–Kutta methods
* List of Runge–Kutta methods
* Linear multistep method
* General linear methods
* Backward differentiation formula
* Yoshida

Theory|

* Symplectic integrator

0.00

(0 votes)

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Leapfrog_integration&oldid=4203700"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template