9.9 Infinite Domains & the Fourier Transform ended on a promise: run the plane-wave test on a finite-difference scheme and out comes a numerical . This lesson keeps it. The leapfrog scheme of 9.4 The Wave Equation & Vibrating Strings was exact at a Courant number , off by at and a blow-up at . Why those three? The plane-wave test answers all of it, and shows something heat never did: a wave packet run through a grid arrives late. For an acoustics simulator, where waves travel many wavelengths, that lateness is the whole game.
Transcript
- Leapfrog replaces both second derivatives of the wave equation by central differences. Try a single plane wave, G to the n times e to the i j theta. Two roots appear, one per direction, and when they have modulus 1, writing G as e to the minus i omega delta t gives the numerical dispersion relation: sine of omega delta t over 2 equals nu times sine of k delta x over 2. The exact relation is omega equals c k, and at nu equal to 1 the two coincide. Otherwise the grid has its own curve.
- The roots have modulus exactly 1 when nu times sine theta over 2 is at most 1, and the worst case is a wave of 2 points per wavelength. So leapfrog is stable if and only if nu is at most 1. At 1.05 the worst mode grows by 1.877 per step, and waves shorter than 2.49 points per wavelength all grow. Geometry agrees: after n steps the grid sees n cells, but the wave needs nu times n. That is the CFL condition. It is necessary, not sufficient: centred advection with Euler satisfies it and is unstable.
- The modified equation has a fourth derivative, which is dispersion. The phase speed, how fast crests move, falls below c by 1 minus nu squared times theta squared over 24. The group speed, how fast a packet's energy moves, falls by three times as much. At nu equal to 0.5 and 10 points per wavelength: slow by 1.24% and 3.74%. At theta equal to pi the group speed is 0. At nu equal to 1 every error vanishes.
- Run a Gaussian packet of 8 points per wavelength to time 0.5. The exact packet sits at 0.7500. At nu equal to 0.5 the numerical one arrives at 0.7205, late by 0.0295; the group-speed deficit times the distance predicts 0.0294. At 16 points the lag is 0.0074, at 4 points 0.1222. At nu equal to 0.8 it is 0.0149, and at nu equal to 1 it is exactly 0: leapfrog simply shifts the data.
- How many points per wavelength? Accept 0.05 cycles of phase error over D wavelengths, and points per wavelength grow like the square root of D. For 10 wavelengths you need 15.7 at nu equal to 0.5 and 11.0 at 0.8; for 100 wavelengths, 49.7. A fourth-order stencil gives a phase ratio of 0.99916 against 0.98363 at 10 points, but the limit tightens to nu at most 0.866.
- In 2D the worst mode is the checkerboard, which needs 2 nu squared at most 1, so nu is at most 0.7071; in 3 dimensions, 0.5774. The geometry agrees: the 5-point stencil reaches a diamond, and the wave must stay inside the circle that fits in it. Past that the checkerboard grows: 1.4643 per step at 0.72, 2.7573 at 0.80. Even below the limit the speed depends on direction: at 10 points and nu 0.7, 0.99147 along an axis, 0.99983 along the diagonal.
- At a Dirichlet end a pulse returns inverted: minus 1.000. At a Neumann end it returns upright, 1.000. An absorbing end uses the characteristic: an outgoing wave obeys u t plus c u x equals zero, discretised one-sidedly. At nu equal to 1 it just copies the neighbour and is exact. For a pulse of width 0.2 the reflection is 0.0050 at nu equal to 0.5, 0.0025 at 0.75, and nothing at 1.
- A worse error hides in the first-order system for pressure p and velocity u: p t equals minus u x, u t equals minus p x. Centred differences on one grid give omega h over c equals sine theta, so the group speed is cosine theta: 0 at 4 points per wavelength and minus 0.5 at 3. Grid-scale energy travels backwards. Leapfrog's group speed only falls to 0, and the staggered grid, pressure at centres and velocity on faces, avoids the reversal.
- In the staggered scheme each field is updated from a difference of the other across half a cell. Eliminate u and you get leapfrog for p, so the dispersion and the limit are identical. What is new is a conservation law: the discrete energy is conserved at walls to round-off, with drift below 1.4 times 10 to the minus 16 on an energy of 0.075 over 300 steps, for nu equal to 0.5, 0.8 and 1. A scheme that can neither amplify nor damp suffers only dispersion error.
- To recap. Plane waves give the dispersion relation, exact at nu equal to 1. Stability needs nu at most 1. Short waves lag, and a packet arrives late by the group deficit times the distance. In 2D the limit drops to 0.7071, and the staggered grid conserves energy. Next, multigrid: relaxation kills rough error quickly and leaves smooth error, so multigrid hands the smooth part to a coarser grid, where it is rough again.
Leapfrog and its plane waves
The scheme for replaces both derivatives by central differences:
It is linear with constant coefficients, so, as in 10.3 Von Neumann Stability Analysis, a single wave is an eigenvector. Try with . Dividing out the common factor, and using :
This quadratic in has root product : one root per direction of travel. If they are complex they have modulus and can be written . Then , and gives the numerical dispersion relation
The exact relation is . Set and the two coincide, because . For any other the grid has its own , and everything below is a reading of it.
Stability: , from two directions
Algebra. The roots are complex conjugates, with exactly, when , that is . This must hold for every , and the worst is (a wave of two points per wavelength, alternating sign from cell to cell). So leapfrog is stable if and only if . Then : no wave decays or grows, and the only error is in phase. For the worst mode has and the larger root is per step. Over steps that is , and 9.5 d'Alembert's Solution & Characteristics measured about from a start with a little grid-scale content: consistent, not a coincidence. Only waves shorter than points per wavelength grow at ; the corner of the plucked string supplies a little of them.
Geometry. After steps depends on data within cells either side. The physical solution depends on data within distance . If the physical interval is wider than the numerical one, so the scheme cannot see data that the answer needs. No scheme with that stencil can converge. That is the CFL condition, and for leapfrog it agrees with the algebra exactly.
Necessary, not sufficient. The domain-of-dependence argument is a necessary condition only. Centred differences for advection, , with Euler in time, satisfy it for any yet are unstable for every step size, with (10.3 Von Neumann Stability Analysis). CFL tells you what a scheme cannot do, never that it works. Leapfrog is a lucky case where the two conditions meet, and in 2D below the geometric argument alone will give the right limit.
Phase error and group error: short waves lag
Expand the truncation error. By Taylor, and . Use for the exact solution:
This modified equation (10.6 Advection Schemes: Upwind, Lax–Wendroff & Beyond) has a fourth derivative, which is dispersion: . It vanishes at . In terms of :
The phase speed is how fast crests move; the group speed is how fast a packet’s envelope, and so the energy, moves (9.9 Infinite Domains & the Fourier Transform). Both are below , so short waves lag, and the group error is three times the phase error. The exact formulas, from the dispersion relation, are
At the group speed is : the grid’s shortest wave goes nowhere. It does not reverse in this scheme. The sim and an independent numpy script give, at and (the reach is how many wavelengths a wave can travel before it is a tenth of a wavelength out of phase):
| points per wavelength | : error, error, reach | : error, error, reach |
|---|---|---|
| 20 | 0.31%, 0.93%, 32 | 0.15%, 0.45%, 67 |
| 10 | 1.24%, 3.74%, 8.1 | 0.61%, 1.85%, 16.5 |
| 5 | 5.05%, 15.4%, 2.0 | 2.61%, 8.33%, 3.8 |
| 4 | 7.98%, 24.4%, 1.3 | 4.31%, 14.3%, 2.3 |
The small-angle formulas give and for the first row. Pushing toward helps every row because the time and space truncation errors cancel, until the error vanishes.
A bigger step is more accurate. With (time exact, space centred) the phase ratio is , which is at points per wavelength, worse than every row above. The time error has the opposite sign to the space error, so a step near the limit is cheaper and more accurate.
The packet experiment
Take a Gaussian envelope of width times a cosine, centred at , with cells on a -cell grid, started as an exactly right-moving wave. The exact solution is the same packet shifted by , undistorted. Run leapfrog to , so the exact packet is centred at , and measure where the numerical packet (the centroid of , over ) has got to. The sim and an independent numpy script agree on every entry:
| points per wavelength | numerical centroid | lag | ||
|---|---|---|---|---|
| 1.0 | 8 | 0.7500 | 0 | 0 |
| 0.8 | 8 | 0.7351 | 0.0149 | 0.0148 |
| 0.5 | 8 | 0.7205 | 0.0295 | 0.0294 |
| 0.5 | 16 | 0.7426 | 0.0074 | 0.0073 |
| 0.5 | 4 | 0.6278 | 0.1222 | 0.1220 |
The measured lag is the group-speed deficit times the distance, to about one percent. At the error is : leapfrog shifts the data. At and eight points per wavelength the packet is late by wavelengths and its pointwise error is for a packet of height : a different wave. Halving the wavelength in cells (from to points) multiplies the lag by , as the law says.
Crests against the envelope. At and points per wavelength, and . The crests outrun their envelope, by , which is of a wavelength over the run: each crest appears at the back of the packet, slides forward through it and dies at the front. The sim shows it.
What to try. Packet at , , ; points per wavelength; . Then the pulse with the three end conditions, and the 2D box at and .
Points per wavelength
A rule of thumb needs a budget: how many wavelengths must the wave travel, and how many cycles of phase error can you accept? The phase lag after wavelengths is cycles. With the small-angle formula and :
Points per wavelength grow like the square root of the distance. For wavelengths and cycles: at ( from the exact formula) and at ; for at it is . In 3D doubling the ppw costs a factor in work (cells times steps), which is why the usual rule for second-order acoustics is only to points per wavelength (from memory).
Higher order. A fourth-order central second difference has symbol in place of , and a phase error of order . In the time-exact limit the phase ratio at points per wavelength is against , and at points against . The price is a stricter limit: with leapfrog (confirmed from the spectrum of the stepping matrix: spectral radius at and at ), a wider stencil that complicates boundaries, and the time error left unchanged. Compact (Padé) stencils buy accuracy per stencil width with a tridiagonal solve, and dispersion-relation-preserving schemes tune weights to the dispersion curve (both from memory). Spectral methods, 10.12 Spectral Methods & the FFT, are the limit of this ladder.
Why is special in 1D and not in 2D
In 1D at the numerical and real characteristics coincide. In 2D, with the 5-point Laplacian and spacing in both directions, the plane-wave test gives
The worst mode is the checkerboard, , which needs :
In dimensions the limit is , so in 3D. The geometry says the same. After steps the 5-point stencil reaches the diamond , whose inscribed circle has radius , while the wave reaches a circle of radius . Inside needs : here the necessary condition is also sufficient.
The checkerboard growth rates (the sim steps the scalar recurrence and an independent script finds the eigenvalues of the companion matrix) are per step at and at , against at and below.
Accuracy changes shape too. At points per wavelength and the phase ratio is along an axis but along the diagonal: the numerical speed depends on direction, so a circular wave turns slightly diamond-shaped. At the limit the diagonal is exact () and the axis is not (); at the axis gives the 1D value and the diagonal . No stable makes both exact, so the 1D trick does not carry over.
Boundaries: reflect or absorb
At a Dirichlet end () the scheme keeps the end node at zero, and the incoming pulse returns inverted; at a Neumann end () the ghost node mirrors the interior, and the pulse returns upright (9.4 The Wave Equation & Vibrating Strings). The sim gives and at three digits for , and .
Absorbing needs the characteristic idea of 9.5 d'Alembert's Solution & Characteristics. At the right end an outgoing wave satisfies . Discretize this by one-sided upwind: . At this just copies the neighbor and is exact for a right-moving wave. For a pulse of width ( cells) the reflected pulse has height at , at and at . The condition is exact only head-on: in 2D oblique waves partly reflect, hence absorbing layers (from memory).
First-order form and the staggered grid
For acoustics, write the physics as a first-order system for pressure and velocity , with density and sound speed set to : and . Eliminating gives . Put at cell centres and at the cell faces, and also stagger in time, with at the half steps:
Each field is updated from a difference of the other across half a cell. Eliminating returns the leapfrog scheme for , so the dispersion relation, the CFL limit and the exactness are identical. What is new: no group-velocity reversal, and a conservation law. The quantity is conserved by the scheme at walls, to round-off: the drift is below on an energy of over steps (, and ). Such a scheme cannot amplify or damp, so a pulse suffers only dispersion error. The velocity sits on faces, as in the MAC grid of 10.11 2D Grids, Boundary Conditions & Staggered (MAC) Grids, and the pressure in cells, as in the finite-volume cells of 10.10 The Finite Volume Method. A rigid wall is at a face (an upright reflection of ), and at the end absorbs the outgoing wave. In the sim, choose the staggered scheme and compare.
Check your understanding
Problems
At and four points per wavelength () find , and .
Show worked solution
, so and . Then , against exactly, so . The group speed is . The table’s last row gives and errors.
A 3D acoustic grid has cm and m/s. Find the largest stable for the 7-point leapfrog scheme, whose limit is .
Show worked solution
The worst mode has and gives . So and s. In 1D the limit would be s: the extra dimensions cost a factor of .
A kHz tone in air ( m/s) travels wavelengths. Using and a phase budget of cycles, find the cell size and time step.
Show worked solution
m. By the small-angle rule, (the exact dispersion relation gives ). With points, m and s. In 3D the domain of wavelengths is cells across, about million cells.
Computation
First the phase and group speed from the dispersion relation, and the points-per-wavelength rule built on them.
Now run the packet through leapfrog yourself.
Change the packet to points per wavelength and compare the measured lag with the prediction. Then set and watch the maximum of .
Key Takeaways
- Plane waves through leapfrog give : exactly at , a grid dispersion otherwise.
- is both the von Neumann condition (, nothing damped) and the dependence condition. At the worst mode grows per step, about in steps. CFL alone is necessary, not sufficient.
- Short waves lag: , . At and points per wavelength a packet is late over (predicted ).
- Points per wavelength grow like : for wavelengths, for (). A fourth-order stencil cuts the phase error from to at points but lowers the limit to .
- In 2D the 5-point scheme needs ( in 3D), and the wave speed depends on direction.
- Dirichlet returns a pulse inverted and Neumann upright; the characteristic end condition leaves at and nothing at .
- The staggered scheme has the same dispersion and limit, conserves a discrete energy to round-off, and avoids the collocated grid’s reversed group velocity.
What comes next
Grid-scale waves, the ones a grid represents worst, are where schemes go wrong: they lag, carry nothing at , and blow up first past the limit. The next lesson, 10.9 Multigrid, uses the same decomposition by wavelength in a different way, and the mechanism is not the same as the one here. For the iterative solvers of 10.8 Elliptic Solvers: Jacobi, Gauss–Seidel & SOR, relaxation kills rough error quickly and leaves smooth error for many sweeps. Multigrid hands the smooth part to a coarser grid, where it is rough again, and recurses. I have not yet computed any of that, so I only claim the structure, not the numbers. Production flow solvers lean on it for the pressure solve (from memory).