14.6 Acoustics & Wave Propagation ended on a grid where each cell talks only to its neighbours, so the work per step grows with the number of cells. Gravity has no such mercy: every body pulls on every other one, from any distance. This last problem of the module reuses 12.7 Orbital Mechanics, 4.7 Energy & Symplectic Integrators and the sensitivity of 7.10 Chaos & the Lorenz System. What is new is the scale.
Transcript
- Gravity has no mercy: every body pulls on every other one. Newton's laws for N bodies are 6N first-order equations in 3D, 4N in the plane, with G equal to 1. Momentum, angular momentum and energy are conserved, and each is a test. They are among the ten classical integrals, from memory, and there is no closed form, so we simulate.
- Subtract the two equations and the relative position obeys the one-body problem, with a conic orbit. Take two unit masses, GM equal to 2, a equal to 1, eccentricity 0.5, started at periapsis. Then r p is 0.5 and the relative speed is root 6, 2.449. Kinetic energy 1.5, potential minus 2, total minus one half; the period is 4.4429. Every integrator must reproduce these.
- In the figure eight, three equal masses chase one another along one curve shaped like an 8: Moore 1993, Chenciner and Montgomery 2000, from memory. The energy is minus 1.28714, and RK4 with h equal to T over 1000, T equal to 6.32591398, returns every body to within 3.4 times 10 to the minus 8 of its start. Kick body 3 by 0.1 percent and the distance after one, two and ten periods is 0.011, 0.033 and 0.153: roughly linear, a stable orbit, from memory.
- A fixed step fails on a close encounter: the crossing time is 1000 times shorter at 0.01. Plummer softening replaces r squared by r squared plus epsilon squared. The force peaks at epsilon over root 2 with value 0.385 G m over epsilon squared, and is bounded; but inside epsilon gravity is wrong, and only the softened energy is conserved. In the lab galaxy at epsilon 0.05 the error is of order 0.1, about 1.2 times 10 to the minus 3 at half the step. For the e equals 0.9 pair, 0.683 becomes 0.062.
- Now the three integrators, 100 steps per orbit. Euler spirals out of the frame, with an energy error of 1.14 over 100 orbits; RK4 and leapfrog stay on the ellipse.
- Over 100 orbits the largest energy error is 1.14 for Euler, 2.98 times 10 to the minus 3 for RK4 and 1.08 times 10 to the minus 2 for leapfrog. Angular momentum errors are 0.58, 4.6 times 10 to the minus 4 and 1.4 times 10 to the minus 14. Over 1000 orbits RK4 reaches 2.99 times 10 to the minus 2 while leapfrog stays put; the lines cross near 360 orbits. But bounded energy is not accurate phase: leapfrog's return time is off by plus 1.7 percent at 100 steps and plus 0.10 at 400.
- The same story in a galaxy: N equal to 302, two cores of mass 1 with 150 light particles each, epsilon 0.1, step 0.01. The energy error at t equal to 5 and 20 is plus 2.28 and plus 2.43 for Euler, minus 1.7 times 10 to the minus 3 and minus 3.9 times 10 to the minus 3 for RK4, and plus 1.1 times 10 to the minus 4 and plus 5.4 times 10 to the minus 4 for leapfrog. Late-time numbers differ between my two codes, because the motion is chaotic.
- A million bodies mean 5 times 10 to the 11 pairs per force evaluation. Barnes and Hut, 1986, from memory, treat a distant crowd as one body. Divide the square into four quadrants, and any quadrant holding more than one body again, storing each cell's mass and centre of mass. Accept a cell of side s at distance d when s over d is less than theta, otherwise open it. The error is of relative order s over d squared, and the cost is order N log N.
- For N equal to 1000, theta 0.5 uses 91.8 terms per body with a median force error of 1.1 times 10 to the minus 3; theta 0.3 uses 169.5 for 3.4 times 10 to the minus 4, theta 1 uses 37.0 for 4.1 times 10 to the minus 3. Speed is another matter: in this lab's JavaScript the ratio of direct over tree is roughly 0.3 at 250 bodies, 1.1 at 2000 and 5.5 at 16000, one machine, rough. The tree wins only beyond about 2000 bodies.
- What does the tree break? Total momentum, exactly 0 at the start, is 3.6 times 10 to the minus 3 at t equal to 5 with theta 0.5, against 10 to the minus 15 for the direct sum. The energy error sits near 2 times 10 to the minus 3, twenty times the direct sum's. Cell approximations are not symmetric, so the third law fails. Softening conserves the softened energy, not the Newtonian one. Beyond the tree, from memory: fast multipole and particle-mesh.
- That closes Module 14. The toolkit was the same each time: write the model, find what it conserves, choose an integrator that respects that, check against an exact case, and know what each approximation breaks. Population models leave mechanics. An N-body system conserves energy, while a population is dissipative and settles toward an equilibrium. Module 15 turns to dissipative growth.
The equations
Bodies have masses , positions and velocities . Newton’s laws give
That is first-order equations in 3D, or in a plane, which is what the lab simulates (with the 3D inverse-square law). We set . This is the Hamiltonian system of 4.7 Energy & Symplectic Integrators.
Three things are conserved, and each is a test. Momentum: the pull of on is minus the pull of on , so . Angular momentum: each force acts along the line between its two bodies. Energy: the kinetic plus potential energy is constant. With the centre-of-mass motion these are the ten classical integrals (from memory), and for no more are known. There is no closed form, so we simulate.
Two bodies: the exact check
Subtract the two equations of motion. The relative position obeys , the one-body problem of 12.7 Orbital Mechanics with . The relative orbit is a conic, the period is , and the energy is .
Worked example. Two unit masses, , , , started at periapsis (the lab’s setup). Then and the relative speed is , so each body moves at . The kinetic energy is , the potential energy is , and the total is as promised. The period is . Every integrator must reproduce these.
Three bodies: a figure eight
For three bodies there is no formula, but there are special solutions. In the figure eight (Moore, 1993, and Chenciner and Montgomery, 2000, from memory) three equal masses chase one another along one curve shaped like an 8. The initial data as I remember them are , , , , with . We can check them. The energy is , and RK4 with returns every body to within of its start after one period (numpy agrees), so the data are right to about eight digits.
Leapfrog at closes to , and at to (a factor : second order); after ten periods the error is .
Now kick it. Raise the speed of body 3 by (and remove the centre-of-mass drift). With RK4 at the largest distance of a body from its start after one, two and ten periods is , and . A kick gives after one period and after ten. That is roughly linear growth, not the exponential growth of 14.3 Pendulums: Linear, Nonlinear, Driven & Double, because the figure eight is a stable orbit (from memory: linearly stable). Generic three-body motion is not so kind (Poincare found chaos, from memory).
Softening
Why does a fixed step fail on a close encounter? A pair at separation crosses it in time about , which shrinks like . A step fine at is hopeless at , where the time is times shorter, and in a galaxy some pair is always passing close.
The standard remedy is Plummer softening (from memory, after Plummer’s 1911 cluster model). Replace by :
The force is still the gradient of the softened potential, so the softened energy is conserved by the true flow, with momentum and angular momentum intact. The pair force is zero at , acts like a spring while , peaks at with value , then falls like . The acceleration is bounded, so the step need only resolve a time of order .
The cost is honest: inside gravity is wrong, which one justifies by letting each particle stand for a cloud of stars.
What it buys, in the lab’s galaxy (, , leapfrog, largest among the values at ; a single step can spike higher, and the direct run touches at on one close pass, then relaxes): at the error is of order , and at my two codes disagree by orders of magnitude, since one chaotic encounter decides. At it is in the lab’s JavaScript and in numpy (only the order is robust), and at in both. At and it is between and . For the eccentric Kepler pair (, steps per orbit, orbits) it is unsoftened and with .
Euler, RK4 or leapfrog
4.7 Energy & Symplectic Integrators compared these methods on a pendulum and a Kepler orbit. Here is the test on the two-body orbit above (, steps per orbit), with the largest relative errors over orbits and, for the energy, orbits:
| method | , 100 orbits | 1000 orbits | angular momentum, 100 orbits |
|---|---|---|---|
| Euler | |||
| RK4 | |||
| leapfrog |
Euler spirals out; RK4 loses per orbit: ten times the orbits, ten times the error. Leapfrog’s error does not grow at all, which is the shadow-Hamiltonian guarantee, so the lines cross near orbits (an estimate from these numbers). Leapfrog keeps angular momentum to rounding.
Bounded energy is not accurate phase. The orbit’s return time is off by for leapfrog at steps per orbit, at and at , a factor of four per halving. RK4’s is only at .
Close encounters again. Set , so . At , , and steps per orbit the leapfrog energy error over orbits is , , and . The factor appears only once the periapsis pass is resolved. Softening () gives , , and , for a different orbit. The other cure is individual or adaptive time steps that shrink near periapsis (from memory, production codes use block steps in powers of two), but a step chosen from the state breaks the symplectic argument.
The cost of all pairs
Each of the bodies needs a sum over the other . The third law lets us visit only pairs, each costing a square root and a division. A million bodies mean pairs per force evaluation. Doubling quadruples the work. The lab’s JavaScript direct sum takes (rough, one machine) , and ms per force evaluation for , and .
Barnes-Hut: treat a distant crowd as one body
A star far from a cluster feels only its total pull. Let masses sit at relative to their centre of mass, so , with the group at distance from the target. Expanding for ,
The first-order term vanishes by the choice of centre. So replacing the group by one body at its centre of mass is wrong only at relative order .
The Barnes-Hut tree (1986, from memory) applies this recursively. Put the bodies in a square, divide it into four quadrants, divide any quadrant holding more than one body, and so on (an octree in 3D). Each cell stores its total mass and centre of mass. For the force on a body, start at the root. If a cell of side has its centre of mass at distance with
use it as one point mass; otherwise open it and look at its four children. My implementation also opens every cell containing the target. At nothing is accepted and the result is the direct sum. A body meets cells, so the cost is .
Measurements. For bodies (two disks, seed , ), the error is the relative against the direct sum. An independent numpy tree reproduces every entry.
| terms per body | median error | 99th percentile | rms | |
|---|---|---|---|---|
A few bodies have relative errors of to , where the true force nearly cancels. Typical errors are far below the worst case: Problem 3 shows a two-body cell at can be wrong, yet the median at is , because real cells have bodies at all positions and the errors average out.
The logarithm is visible: terms per body at are at , at and at , about more per doubling. Speed is another matter. In this lab’s JavaScript, which rebuilds the tree at every evaluation, the ratio direct over tree at is roughly at , at , at , at and at (one machine, rough). The tree wins here only beyond about bodies.
What the tree and softening break
Run the galaxy with the tree (leapfrog, , , ). The total momentum, exactly at the start, is at and at for , against for the direct sum. It is for and for . At the energy error sits near , twenty times the direct sum’s (both runs spike for one step near , to and ). The cell approximation is not symmetric: body may see as part of a far cell while sees individually, so the third law fails pair by pair. The tree force is also not the gradient of any potential, so the shadow-Hamiltonian argument of 4.7 Energy & Symplectic Integrators no longer applies.
Softening is subtler. The softened energy is conserved by leapfrog to bounded error, which is what the lab reports. The Newtonian energy with is not conserved, because you are simulating a smoother system. Know which quantity your code actually conserves.
Beyond the tree
Two further ideas, both from memory. The fast multipole method (Greengard and Rokhlin, 1987) keeps the tree but expands each cell’s far field to higher order, and lets groups of bodies interact with groups. The cost is at fixed accuracy, raised through the expansion order. The particle-mesh method deposits mass on a grid, solves with the FFT (the Poisson solve of 10.12 Spectral Methods & the FFT), differentiates, and interpolates the force back: for cells, but with no resolution below a cell.
The lab
- Defaults (leapfrog, direct, , ): the disks interact and shed tails. The energy error stays near and at rounding.
- Choose Euler: the energy error jumps by order one. RK4 looks fine but its error creeps downward.
- Set at : the error becomes about . Halve and it falls to about .
- Choose the Barnes-Hut tree and watch leave zero; lower and it shrinks.
The exercise: leapfrog for two bodies
The playground runs the figure eight with a numpy direct sum and leapfrog, then compares the eccentric pair with and without softening. In the exercise you write the pairwise acceleration, the energy and the leapfrog step yourself, and the tests check the energy, the period and the symmetries against the exact two-body values.
Concept checks
Problems
Two bodies of mass , , . (a) At what separation is the pair force largest, and how large is it? (b) For show the relative motion is harmonic and find its period.
Show worked solution
(a) With , gives , where , so the force is .
(b) For , and the separation obeys . So , , and the period is : about steps of .
Bodies of mass and () have a relative orbit with . Find the period, the energy, and each body’s semi-major axis about the centre of mass.
Show worked solution
, so . The energy is . Since , and , so the heavy body has and the light one , both with period .
Two bodies of mass sit at on a line, and a target on the line is at distance from the centre with . Compare the exact force with the monopole force . Why is the measured median error at so much smaller?
Show worked solution
With the exact force is , so the monopole is low by the factor (). The expansion has leading error , as the argument says. The measured median is because real cells hold bodies spread through the cell, and their quadrupole terms have no common sign.
What comes next
That closes Module 14. Oscillators gave eigenmodes, pendulums brought nonlinearity and chaos, heat and beams were boundary-value problems, and acoustics derived a wave equation. This lesson ran a many-body system. The toolkit was the same each time: write the model, find what it conserves, choose an integrator that respects that, check against an exact special case, and know what each approximation breaks. Here the approximations broke energy and momentum, and three-body chaos limits prediction whatever the integrator.
15.1 Population Models leaves mechanics. The syllabus lists exponential, logistic and Gompertz growth, harvesting, the Allee effect, least-squares fitting and a glimpse of delay equations. The contrast is the point: an N-body system conserves energy, while a population is dissipative and settles toward an equilibrium.
Key Takeaways
- Newton’s gravity is first-order equations ( in a plane) with conserved energy, momentum and angular momentum; the two-body orbit is the exact check, and the figure eight closes to with RK4 at .
- A close encounter demands a step shrinking like ; Plummer softening bounds the force at the price of changing the physics inside .
- On the Kepler orbit (, steps per orbit) Euler gains energy (), RK4 loses per orbit, and leapfrog stays within with angular momentum exact.
- Barnes-Hut accepts a cell when , an error of relative order , giving . At the median force error is , and it beat the direct sum in my code only above about bodies.
- The tree breaks the third law, so momentum ( at against ) and the energy guarantee are lost; softening conserves only the softened energy.
- Fast multipole and particle-mesh methods are the next steps; Module 15 turns to dissipative growth.