next up previous contents
Next: 4.2 A Simple Leapfrog Up: 4. Exploring with a Previous: 4. Exploring with a

4.1 Two Ways to Write the Leapfrog

The name leapfrog comes from one of the ways to write this algorithm, where positions and velocities `leap over' each other. Positions are defined at times $t_i, t_{i+1}, t_{i+2}, \dots $, spaced at constant intervals $dt$, while the velocities are defined at times halfway in between, indicated by $t_{i-1/2}, t_{i+1/2}, t_{i+3/2}, \dots $, where $t_{i+1} - t_{i + 1/2} = t_{i + 1/2} - t_i = dt / 2$. The leapfrog integration scheme then reads:


$\displaystyle {\bf r}_{i}$ $\textstyle =$ $\displaystyle {\bf r}_{i-1} + {\bf v}_{i-1/2} dt$ (4.1)
$\displaystyle {\bf v}_{i+1/2}$ $\textstyle =$ $\displaystyle {\bf v}_{i-1/2} + {\bf a}_i dt$ (4.2)

Note that the accelerations ${\bf a}$ are defined only on integer times, just like the positions, while the velocities are defined only on half-integer times. This makes sense, given that ${\bf a}({\bf r}, {\bf v}) = {\bf a}({\bf r})$: the acceleration on one particle depends only on its position with respect to all other particles, and not on its or their velocities. Only at the beginning of the integration do we have to set up the velocity at its first half-integer time step. Starting with initial conditions ${\bf r}_0$ and ${\bf v}_0$, we take the first term in the Taylor series expansion to compute the first leap value for ${\bf v}$:


\begin{displaymath}
{\bf v}_{1/2} = {\bf v}_0 + {\bf a}_0 dt / 2.
\end{displaymath} (4.3)

We are then ready to apply Eq. 4.1 to compute the new position ${\bf r}_1$, using the first leap value for ${\bf v}_{1/2}$. Next we compute the acceleration ${\bf a}_1$, which enables us to compute the second leap value, ${\bf v}_{3/2}$, using Eq. 4.2, and so on.

A second way to write the leapfrog looks quite different at first sight. Defining all quantities only at integer times, we can write:


$\displaystyle {\bf r}_{i+1}$ $\textstyle =$ $\displaystyle {\bf r}_i + {\bf v}_{i} dt + {\bf a}_{i} (dt)^2/2$ (4.4)
$\displaystyle {\bf v}_{i+1}$ $\textstyle =$ $\displaystyle {\bf v}_i + ({\bf a}_i + {\bf a}_{i+1})dt / 2$ (4.5)

This is still the same leapfrog scheme, although represented in a different way. Notice that the increment in ${\bf r}$ is given by the time step multiplied by ${\bf v}_{i} dt + {\bf a}_{i} / 2$, effectively equal to ${\bf v}_{i+ 1/2}$. Similarly, the increment in ${\bf v}$ is given by the time step multiplied by $({\bf a}_i + {\bf a}_{i+1}) / 2$, effectively equal to the intermediate value ${\bf a}_{i+1/2}$. In conclusion, although both positions and velocities are defined at integer times, their increments are governed by quantities approximately defined at half-integer values of time.

A most interesting way to see the equivalence of Eqs. 4.1, 4.2 and Eqs. 4.4, 4.5 is to note the fact that the first two equations are explicitly time-reversible, while it is not at all obvious whether the last two equations are time-reversible. For the two systems to be equivalent, they'd better share this property. Let us inspect.

Starting with Eqs. 4.1, 4.2, even though it may be obvious, let us write out the time reversibility. We will take one step forward, taking a time step $+dt$, to evolve $\{{\bf r}_i, {\bf v}_{i-1/2}\}$ to $\{{\bf r}_{i+1}, {\bf v}_{i+1/2}\}$, and then we will take one step backwards, using the same scheme, taking a time step $-dt$. Clearly, the time will return to the same value since $+dt-dt=0$, but we have to inspect where the final positions and velocities $\{{\bf r}_f(t=i), {\bf v}_f(t=i-1/2)\}$ are indeed equal to their initial values $\{{\bf r}_i, {\bf v}_{i-1/2}\}$. Here is the calculation, resulting from applying Eqs. 4.1, 4.2 twice.


$\displaystyle {\bf r}_f$ $\textstyle =$ $\displaystyle {\bf r}_{i+1} - {\bf v}_{i+1/2} dt$  
  $\textstyle =$ $\displaystyle \left[ {\bf r}_i + {\bf v}_{i+1/2} dt \right]
- {\bf v}_{i+1/2} dt$  
  $\textstyle =$ $\displaystyle {\bf r}_i$ (4.6)
       
$\displaystyle {\bf v}_f$ $\textstyle =$ $\displaystyle {\bf v}_{i+1/2} - {\bf r}_i dt$  
  $\textstyle =$ $\displaystyle \left[ {\bf v}_{i-1/2} + {\bf a}_i dt \right]
- {\bf a}_i dt$  
  $\textstyle =$ $\displaystyle {\bf v}_{i-1/2}$ (4.7)

In an almost trivial way, we can see clearly that time reversal causes both positions and velocities to return to their old values, not only in an approximate way, but exactly. In a computer application, this means that we can evolve forward a thousand time steps and then evolve backward for the same length of time. Although we will make integration errors (remember, leapfrog is only second-order, and thus not very precise), those errors will exactly cancel each other, apart from possible round-off effects, due to limited machine accuracy.

Now the real fun comes in, when we inspect the equal-time Eqs. 4.4, 4.5:


$\displaystyle {\bf r}_f$ $\textstyle =$ $\displaystyle {\bf r}_{i+1} - {\bf v}_{i+1} dt + {\bf a}_{i+1} (dt)^2/2$  
  $\textstyle =$ $\displaystyle \left[ {\bf r}_i + {\bf v}_i dt + {\bf a}_i (dt)^2/2 \right]
- \l...
...bf v}_i + ({\bf a}_i + {\bf a}_{i+1})dt / 2 \right] dt
+ {\bf a}_{i+1} (dt)^2/2$  
  $\textstyle =$ $\displaystyle {\bf r}_i$ (4.8)
       
$\displaystyle {\bf v}_f$ $\textstyle =$ $\displaystyle {\bf v}_{i+1} - ({\bf a}_{i+1} + {\bf a}_i)dt / 2$  
  $\textstyle =$ $\displaystyle \left[ {\bf v}_i + ({\bf a}_i + {\bf a}_{i+1})dt / 2 \right]
- ({\bf a}_{i+1} + {\bf a}_i)dt / 2$  
  $\textstyle =$ $\displaystyle {\bf v}_i$ (4.9)

In this case, too, we have exact time reversibility. Even though not immediately obvious from an inspection of Eqs. 4.4, 4.5, as soon as we write out the effects of stepping forward and backward, the cancellations become manifest.


next up previous contents
Next: 4.2 A Simple Leapfrog Up: 4. Exploring with a Previous: 4. Exploring with a
The Art of Computational Science
2004/01/25