At the end of 4.3 Runge–Kutta Methods & Butcher Tableaux RK4 on a pendulum lost energy slowly and steadily, and in 4.6 Multistep Methods AB2 gained it. A game, a molecular-dynamics code, an SPH solver or an N-body integrator takes millions of steps at a step size far too coarse for RK4, and what it needs is that the energy does not drift, even when the individual steps are not very accurate. A family of methods gives exactly that. They are old (Verlet 1967, from memory), cheap (one force evaluation per step) and the reason they work is an area-preservation property you can check with the determinant of 1.4 Determinants as Volume Scaling.
Transcript
- Run a pendulum from one radian to time one thousand, step one half. RK4 loses energy steadily, minus 0.123. Symplectic Euler and Verlet wobble but never drift; Verlet stays within 0.0266. At step 0.1, though, RK4 still wins: 4.59 times ten to the minus 5 against 1.06 times ten to the minus 3.
- In Hamiltonian form, q prime is dH by dp and p prime is minus dH by dq. Symplectic Euler is a kick, which changes the momentum, then a drift, which moves the position using the new momentum. Drift first gives the other variant.
- Why does this keep area? A kick shears a blob of states vertically, a drift shears it horizontally. A shear keeps area: its determinant is one. Determinants multiply, so any chain of kicks and drifts preserves area.
- One step on the oscillator, applied to a blob of area one. Euler inflates it to 1.25; RK4 shrinks it by 2.1 times ten to the minus 4, which is its energy loss; both symplectic methods give one. On the pendulum, Euler is plus 0.135, RK4 minus 1.76 times ten to the minus 5, the others zero.
- To time ten times two pi, 126 steps: the product of determinants is 0.345 for Euler, 0.9857 for RK4, one for the symplectic pair. A polygon of 240 states agrees. But at step 0.1 Euler's polygon claims 2730 while the product says 1.14: trust the product.
- Half a kick, a drift, half a kick: velocity Verlet, second order. Merging half kicks gives leapfrog; drift first gives position Verlet, agreeing to about ten to the minus 14. Run a thousand steps, flip the momentum, run back: Verlet returns to a few times ten to the minus 14, RK4 misses by 7.3 times ten to the minus 5, symplectic Euler by 0.555.
- On the oscillator, symplectic Euler exactly conserves a nearby energy, p squared plus q squared minus h p q, over two: to about ten to the minus 14 over a hundred thousand steps, while the true energy ranges from 0.4 to 0.6667. Verlet's was checked by code, not derived. The general theory is from memory.
- Kepler, eccentricity 0.6. RK4's worst energy error grows steadily: 3.5 times ten to the minus 4 at ten orbits, 3.55 times ten to the minus 2 at a thousand. Verlet stays at 9.49 times ten to the minus 3. RK4 leads for about a hundred orbits; extending its line, they meet near 270 orbits, an extrapolation.
- But bounded energy is not accurate position. After ten orbits RK4 is 0.073 from the truth, Verlet 1.77 and symplectic Euler 1.99, about the orbit's size. The orbit precesses.
- Verlet needs a fixed step. With h equal to 0.05 r to the three halves, 12 percent more steps, the energy drifts in a straight line: minus 0.0246 after a thousand orbits, against a fixed-step bound of 0.0095. Random steps wander to nearly 0.09.
- Damping breaks the premise: a damped oscillator is not Hamiltonian. At step one half, to time 50, Verlet's energy is 8.55 percent low and RK4's 0.23 percent high, ordinary accuracy, not a symplectic failure. Ge and Marsden: no fixed-step symplectic method conserves energy exactly, from memory.
- Leapfrog on y prime equals minus y has a second root of modulus 1.105, and 1.105 to the fiftieth is 147: unstable on decay. On y prime equals i y both moduli are exactly one up to s of one; at 1.1 they split to 1.558 and 0.642. Verlet's step is twice s, so h is at most two.
- So: kicks and drifts are shears, area survives, energy stays bounded. Use a fixed step and velocity Verlet for game physics; games, molecular dynamics, N-body and SPH do, from memory. Avoid variable steps and damping. Next, Module 5: second-order equations.
What a long run does to RK4
Block A of the lab at the end runs the pendulum from rad at rest to with energy , (the example of 4.3 Runge–Kutta Methods & Butcher Tableaux). The columns are at the end and the largest seen. Euler, symplectic Euler and Verlet are defined below; Euler is included so you can see the problem.
| method | : end | max | : end | max |
|---|---|---|---|---|
| Euler | ||||
| RK4 | ||||
| symplectic Euler | ||||
| Verlet |
The RK4 column only ever grows (the loss per step is , 4.3 Runge–Kutta Methods & Butcher Tableaux), while the symplectic columns wobble. At RK4 is still ahead of Verlet by a factor at . A harder case is a Kepler orbit, , eccentricity , period , steps per orbit (block B; ):
| method | after 10 orbits | 100 orbits | 1000 orbits |
|---|---|---|---|
| RK4 | |||
| symplectic Euler | |||
| Verlet |
RK4 is better for the first hundred orbits and then loses, because its error grows by about per orbit while Verlet’s does not grow at all. Extrapolating that straight line, the two meet near orbits (an estimate from these three columns, not a computed crossing). Honesty about the other side: bounded energy is not accurate position. Ten orbits in, the distance from the true position is for RK4 but for Verlet and for symplectic Euler (block B). The orbit precesses, it does not lose its energy. What the symplectic methods buy is the right qualitative long-time behavior, not a smaller error at any step.
Hamiltonian form
Take a mass with position and momentum in a potential (unit mass), force , and Hamiltonian . Then
Along a solution : energy is conserved. The pendulum is ; the harmonic oscillator is ; with vectors and you get Kepler, and particles with pair potentials give N-body, molecular dynamics and (without viscosity) SPH.
There is a second conservation law, geometric. The velocity field in the plane has divergence , so by 2.7 Divergence: Sources & Sinks the flow neither compresses nor expands area: a blob of initial conditions is carried to a blob of the same area (Liouville’s theorem, from memory in this form). For a step map the area factor is the Jacobian determinant of 2.2 Linearization, the Chain Rule & the Jacobian, and a method whose is exactly is called symplectic (in one degree of freedom; in higher dimensions it preserves the 2-form , from memory).
Symplectic Euler: kick, then drift
Euler’s method on this system uses old values in both updates: , . Its Jacobian is with determinant , which is on the oscillator (): every step inflates area by , and also energy, since . That is the energy gain Euler shows in the table.
The cure is to use the newest value:
This is symplectic Euler, “kick then drift”. The other variant drifts first, , . Both come from splitting with : the Hamiltonian alone has the exact flow , , a kick ; the Hamiltonian alone has , , a drift . Both flows are explicit, and applying them in turn ( or ) is one step. The error is first order: the splitting is wrong by the commutator of the two flows, per step.
Why the determinant is 1: shears
The Jacobians of the pieces are
Each is a shear (1.2 Matrices as Transformations): it slides rows or columns of the plane without changing the area of a parallelogram, and has determinant . A product has determinant (1.4 Determinants as Volume Scaling), so any composition of kicks and drifts, with any step sizes and at any point, preserves area exactly. That is the entire proof; the nonlinearity of hides in the entry and does not matter. Block E multiplies these matrices and, for RK4, differentiates the step by running RK4 on with (the derivative of the RK4 map). It prints at and :
| method | oscillator | pendulum at |
|---|---|---|
| Euler | ||
| RK4 | ||
| symplectic Euler | ||
| Verlet | (rounding) |
The Euler entries are and . The RK4 oscillator entry is , which is of 4.3 Runge–Kutta Methods & Butcher Tableaux: the amplitude factor you met there. So RK4’s energy loss and its shrinking of area are the same fact. The sim below measures them on a blob.
Velocity Verlet, leapfrog and position Verlet
One kick-drift pair has only first order, but a symmetric composition does better. Velocity Verlet is half a kick, a full drift, half a kick,
i.e. . That a palindromic splitting has even order is a standard fact (from memory); the data agree: the largest energy error over is for , ratios (block A): second order. Counting force evaluations, the last half kick of one step and the first of the next share the same , so a run costs one evaluation per step.
Glue consecutive half kicks into full kicks and you get leapfrog, with living at half steps: , . Do the drift first and you get position Verlet, . Block C verifies, over steps at on the pendulum, that leapfrog and velocity Verlet agree to about (rounding; the last digits depend on the platform’s math library), and that position Verlet is velocity Verlet seen through a half-step change of variables. With maps applied right to left, : both sides are the same kicks and drifts regrouped. The code finds the two sides equal to the same . They are one method viewed from different places.
Reversibility
Let flip the momentum. Then (a kick changes by , and does not see ) and . For the palindrome, : run forward steps, flip , run steps, and you are back at the start. For symplectic Euler, , the other variant’s inverse, so it is not reversible. Block D runs the pendulum from with for steps, flips, and returns steps:
| method | distance from the start |
|---|---|
| Verlet | (rounding) |
| RK4 | |
| symplectic Euler |
Verlet comes back to rounding; RK4 does not, since its error is not symmetric. Reversibility matters for the long run as well (it keeps the energy error from drifting in typical cases; from memory), but the main account is the next section.
The shadow Hamiltonian
On the oscillator, symplectic Euler is , . Claim: is conserved exactly. With the new values, . Now , and . The sum is . So the numerical orbit lies on an ellipse of and does not spiral. The true energy moves along that ellipse. On the product ranges from to , so at , ranges over . Block F runs steps and finds and . For Verlet the same code finds conserved to over steps, with (not derived here).
The general statement is backward error analysis (from memory): a symplectic method of order is, to any chosen order of accuracy, the exact flow of a nearby Hamiltonian , and is conserved up to errors exponentially small in over exponentially long times. So stays within of its starting value for those times, with no drift. For the pendulum with Verlet the bound scales like , as block A’s ratios of show. A related theorem of Ge and Marsden (from memory) says that no symplectic method with a fixed step can conserve the energy exactly for a generic either; the shadow is what you get instead.
The sim advects the center point and a ring of initial conditions with each method. The ring area is the shoelace formula, ; it is shown next to the product of the one-step along the center orbit, which is the area factor of an infinitesimal blob and needs no polygon. A headless run reproduced these:
- Oscillator, (steps of ), : area factor (Euler, per step), (RK4, per step), for symplectic Euler and Verlet. The shadow readout shows and .
- Pendulum, , : the product of is for Euler (below : its determinant is under in the upper half of the swing, where the orbit spirals out), for RK4, for the others; the ring polygon agrees (, , , ). When a ring is stretched too far (long and a large ) the polygon stops following it, the sim marks the number with a star, and the product of is the one to trust.
- Kepler, , orbits: (RK4), (Verlet), (symplectic Euler), (Euler). Drag from to and RK4’s line climbs while the symplectic lines stay flat. At RK4’s is already close to Verlet’s .
Where the guarantee fails
Variable step sizes. Each step of Verlet is symplectic for any fixed , but the shadow depends on . If the step is chosen from the current state, , the Jacobian of gains terms from , its determinant is no longer , and the argument is lost. Block H runs Verlet on the Kepler orbit for orbits. With a fixed the energy error after orbits is each time, always inside the bound. With (the natural orbital step: smaller near the Sun; at the start of the step) and steps ( more), the error is : a straight-line drift of the kind RK4 shows, already times the fixed run’s bound at the end. Even a state-independent but random in (seeded) wanders to between and ( in the video’s run) against (the digits shift between platforms), since each step has its own . Choosing steps in a way that keeps symmetry (a function of both ends of the step) exists (from memory, Hairer, Lubich and Wanner). It is why adaptive RK45 of 4.4 Adaptive Step Size & RK45 is the wrong tool for a 10-million-step orbit.
Dissipation. Nothing here applies to : a damped system is not Hamiltonian and the true flow shrinks area by per step. Block I runs to with and compares with the exact solution: Verlet (the damping force uses the most recent velocity) is low and RK4 is high. Nothing makes Verlet’s decay rate right; its guarantee concerns conservative problems, and on a dissipative one only the ordinary order of accuracy counts, where RK4 is better.
The lab
The playground reproduces every number in this lesson (blocks A to I) with plain Python; it takes a few seconds.
Leapfrog’s parasitic root
Multistep’s Problem 3 showed that leapfrog on has roots and at , and (block G reproduces both): the second, parasitic root grows and alternates in sign, so the method is unstable on decay. Yet leapfrog is the heart of every code above. The resolution is the test equation. For the roots solve , so , and for the two roots have modulus exactly: block G prints moduli and for . The parasitic mode is a bounded saw-tooth, never amplified, and the physical mode does not decay. Past the roots are purely imaginary with moduli and : unstable. The leapfrog spacing is half a Verlet step ( is updated every other node), so is , the stability limit found in Problem 1. Leapfrog is stable only on oscillations, which is what Hamiltonian systems consist of, and that is the sense in which it is both unstable (on dissipation) and excellent (on waves).
Exercise
For , one step maps to .
- Find and show and .
- Both eigenvalues are on the unit circle exactly when . For which ?
- At find the rotation angle and the number of steps after which the state returns exactly. At find the larger eigenvalue modulus.
Show worked solution
- , , . So , , .
- Eigenvalues solve with product . They are complex conjugates of modulus iff , i.e. .
- At , gives , so : six steps return to the start. At , , : the amplitude grows by per step.
Drift first: , on the oscillator. Show that is conserved exactly, and say how the sign compares with the kick-drift variant.
Show worked solution
With the new values, . Since , this is . Then . The total is . (Run for steps at from the largest change is about , rounding.) The kick-drift variant has and this one . The two are adjoints, , and a step built from half steps of each (Verlet) is palindromic, which cancels the term .
, with . The true flow shrinks area by per time .
- Find the Jacobian of one explicit Euler step and its determinant.
- Evaluate it for and and compare with .
- For which does Euler shrink area at all? What does this say about using it on dissipative flows?
Show worked solution
- , .
- : against . : against .
- iff . For the artificial growth beats the real damping , so the numerical solution spirals out although the true one decays. For the area grows by per step. The same is why Euler fails on the undamped oscillator; stability regions for dissipative problems are the subject of 4.5 Stability Regions & Stiffness.
Key Takeaways
- RK4’s energy error on an oscillator grows linearly (the loss per step is built in), so a long run eventually loses to a second-order symplectic method with a worse error per step; for the Kepler orbit at steps per orbit the crossover estimate is about orbits.
- A Hamiltonian system , conserves and preserves phase-space area; a method is symplectic when its step has Jacobian determinant .
- Kick () and drift () are shears with determinant . Any composition is area-preserving: symplectic Euler is kick then drift, velocity Verlet is half-kick, drift, half-kick, with one force evaluation per step and second order.
- Leapfrog, velocity Verlet and position Verlet are the same method up to relabelling (checked to about ); the symmetric one is time reversible (forward, flip , back returns to within a few ) while RK4 is not ().
- On the oscillator the numerical orbit exactly conserves a shadow Hamiltonian ( for symplectic Euler); in general this holds to exponentially small terms (from memory), so oscillates by instead of drifting.
- The guarantee is lost with a step that depends on the state (Kepler energy drift after orbits against a bounded ), with random step sizes, and for dissipative systems (Verlet off on a damped oscillator).
- Bounded energy is not small position error: the symplectic orbit precesses. Use a fixed step in games, molecular dynamics and N-body; do not expect help for viscous fluids.
- Leapfrog’s parasitic root has modulus exactly on oscillations () and is unstable on decay: stable for waves only.