In 10.2 Explicit Methods for the Heat Equation we found the explicit heat limit from the eigenvalues of a tidy tridiagonal matrix. Many schemes have no such matrix. This lesson gives a shortcut that needs none. Push a single wave through one step of the scheme and see what factor comes out. That factor is the amplification factor , and the scheme is stable when no wave is amplified. The recipe handles diffusion and advection, and shows why the obvious centred advection scheme fails for every time step.
Transcript
- In the heat lesson we found the explicit limit from the eigenvalues of a matrix. Many schemes have no such matrix. Push a single wave through one step of the scheme and see what factor comes out. That factor, G, is the amplification factor: its size is the growth per step, its phase the slide.
- Only theta from 0 to pi matters. At zero the wave is constant; at pi it is the sawtooth of wavelength two cells. A real solution is a sum of such waves, so it stays bounded exactly when the modulus of G is at most 1 for every theta. Where that fails is the unstable band.
- Check it on FTCS diffusion. The mode gives G equals 1 minus 4 r sine squared of theta over 2. That is real, so G at least minus 1 needs r at most one half, with no matrix. For r equals 0.6 the unstable band starts at theta equals 2.3005, and the run blows up at step 120.
- Advection only moves things. The CFL number c is how many cells the true solution moves in one step. Each wave picks up the factor e to the minus i c theta: modulus exactly 1, phase minus c theta. That is the benchmark for any scheme.
- Now the obvious scheme: forward in time, centred in space. Its factor is 1 minus i c sine theta, with modulus squared 1 plus c squared sine squared theta. That exceeds 1 for every theta between 0 and pi, and every nonzero c: no step size makes it stable. At c equals 0.5 the worst wave, theta equals pi over 2, has modulus 1.1180.
- Centred differences give purely imaginary eigenvalues, and forward Euler spirals outward on them. The square pulse blows up at step 189, the Gaussian at step 324: calm for hundreds of steps, then failure in tens.
- Upwind looks against the wind. Its factor, 1 minus c plus c e to the minus i theta, is a weighted average of two points on the unit circle. For c between 0 and 1 the weights are not negative, so G sits on a chord inside the disk. At c equals 1.2 a weight goes negative, G is minus 1.4 at theta equals pi, and the lab blows up at step 116.
- Lax-Friedrichs replaces u j by the average of its neighbours: the centred scheme plus explicit diffusion with r equal to one half. The factor is cosine theta minus i c sine theta, stable exactly when c is at most 1. At c equals 1.2 the worst modulus is 1.2, and the run blows up at step 195.
- Stable is not accurate. For small theta, upwind behaves as if the equation had extra viscosity. Run a Gaussian once around the domain, 200 steps at c equals 0.5. Upwind leaves a peak of 0.5141; Lax-Friedrichs only 0.3269.
- Diffusion adds to the variance of the pulse. From variance 18, the predicted peaks are 0.514 and 0.327, against 0.5141 and 0.3269 in the lab. Upwind at c equal to 0.25 after 400 steps: 0.440 against 0.4397. All three are stable, and all three smear.
- The phase of G gives numerical dispersion: grid speed over true speed, which should be 1. Upwind at c equals 0.5 gets it exactly. At c equals 0.25 it gives 0.8193 at theta equals pi over 2. Centred drops to 0.5903: the shorter the wave, the slower. Lax-Friedrichs runs to 2.0: twice too fast.
- A remark on Stam's solver. It traces each cell back by c equal to m plus f cells and interpolates linearly. The weights are never negative, so the modulus is at most 1 for every c; for c below 1 it is plain upwind. That is why it is stable, and its price is this numerical diffusion: the smoke smears.
- Why stability and not accuracy? The Lax equivalence theorem: for a well-posed linear problem, a consistent scheme converges exactly when it is stable. We state it here and do not prove it. Centred advection is the standing example: consistent, unstable, not convergent. The analysis assumes constant coefficients and a periodic domain; boundaries and nonlinear equations need more.
- The same trick works for implicit schemes. Put diffusion at the new time level and the unknown sits in a denominator: backward Euler and Crank-Nicolson stay inside the unit circle for every r. The price is a tridiagonal solve per step, which is how Stam's solver diffuses momentum. Implicit methods are next.
One mode through a scheme
Take a grid of spacing and a wave sampled on it, , and write , the phase advance per node. Suppose the scheme is linear with constant coefficients: each new value is a fixed weighted sum of old values at fixed offsets. Shifting the wave by one node just multiplies it by a constant, , so a weighted sum of shifted copies of is again a multiple of . Every wave is an eigenvector of the scheme, as was for linear ODEs and for the Laplace transform (6.1 The Laplace Transform). The multiplier is what we want. Write
substitute into the scheme, and divide by the common factor : an equation for the complex number remains. Its modulus is the growth per step and its phase is how far the wave slides along the grid per step. Euler’s formula (1.7 Complex Eigenvalues & Rotation) is all the complex arithmetic needed.
Only a window of matters. The values and give identical samples, and is the complex conjugate, so for real data
At the wave is constant; at it is , the sawtooth of wavelength two cells. A real solution is a sum of such waves, so it stays bounded exactly when no wave is amplified:
This is the von Neumann stability condition. Where it fails, the set of with is the unstable band, and the instability is that band growing like out of rounding error.
Check it on the one you know: FTCS diffusion
For FTCS, with , substitute :
This is real and ranges from to , so needs , the limit from before. It is the explicit-methods-for-the-heat-equation formula with , reached with no matrix, boundary or eigenvalue. The unstable band appears directly: for it is . For that starts at : only waves shorter than cells.
Advection and the CFL number
For diffusion everything decays; advection, , only moves things: the exact solution translates the profile at speed . With grid spacing and step define the CFL number (Courant, Friedrichs, Lewy)
the number of cells the true solution moves in one step. A wave moves to , and on the grid that multiplies each mode by
modulus exactly and phase . This is the benchmark: a scheme must have (stable), and for accuracy near and near on the waves we care about.
Centred advection is unstable for every step
The obvious scheme copies diffusion: forward in time, centred in space,
It is consistent and second order in space. Substituting a mode,
That exceeds for every strictly between and and every . No choice of makes it stable: smaller steps lower the growth per step but never remove it. Geometrically sits on the line , which touches the unit circle only at .
The mechanism is in the method of lines. Centred differencing makes the semi-discrete eigenvalues purely imaginary, : waves that oscillate and never decay. Forward Euler’s stability region (4.5 Stability Regions & Stiffness) is a disk of radius centred at , touching the imaginary axis only at the origin, so forward Euler on undamped oscillation spirals outward. Diffusion survived because its eigenvalues were real and negative.
For the worst wave is (four cells per wavelength), . Seeded at it needs steps to reach (see the problems): calm for hundreds of steps, then failure in tens. One qualification: this is for a fixed CFL number. With we get , which is allowed, but that step is the diffusion cost for a problem that should need a step proportional to .
Upwind: stable when information is not skipped
If the wind blows from left to right (), the information that decides comes from the left. Upwind differences against the wind:
For , is a weighted average of the points and of the unit circle with nonnegative weights, so it lies on the chord between them, inside the disk: with no algebra. Written out,
For the weight is negative, flips sign, and for every , worst at where : for . At , and the scheme is the exact shift by one cell.
So upwind is stable exactly for . For the true solution at came from more than one cell away, and the scheme only looks one cell back: it extrapolates with a negative weight. This is the Courant condition, which a later lesson derives again from domains of dependence.
Lax-Friedrichs: repairing centred advection
Lax-Friedrichs replaces in the centred scheme by the average of its neighbours:
Since , this is the centred scheme plus an explicit diffusion step with . In the extra term is , a push inward: and
It is stable exactly when , the same limit as upwind, and at it too is the exact shift. The price is smearing, next.
What does to a wave: numerical diffusion
A stable scheme can still lose amplitude on waves that should keep it. For small the upwind modulus is , so after steps
Physical diffusion multiplies a wave by over time . With and the two agree when : the scheme behaves as if the equation had an extra viscosity of that size. Lax-Friedrichs gives , a larger one.
The lab checks it. The Gaussian pulse is cells wide, variance cells. Diffusion adds to a variance: cells for upwind, for Lax-Friedrichs, and the peak falls by . At after steps (once around the periodic domain):
- Upwind: variance , predicted peak ; the lab shows .
- Lax-Friedrichs: variance , predicted ; the lab shows .
- Upwind, , steps: variance , predicted ; the lab shows .
All three are stable and all three smear: stable is not accurate.
The phase of : numerical dispersion
Per step the scheme moves mode by , where the exact motion is . The ratio is the wave’s speed on the grid over its true speed. If it differs from and depends on , a pulse of many waves falls apart: numerical dispersion. From the lab’s third panel:
- Upwind, : has phase exactly , ratio for every . All its error is in the modulus.
- Upwind, , : , ratio : too slow, and .
- Centred, : ratio at and at : the shorter the wave, the slower.
- Lax-Friedrichs, : ratio at and at , where advances the phase by per step instead of : twice too fast, and damped to .
The Lax equivalence theorem
Why analyse stability and not accuracy? Three words, for a scheme approximating a linear initial value problem:
- Consistent: the truncation error (10.1 Finite Differences: Discretizing Derivatives) goes to zero as .
- Stable: a perturbation is multiplied by at most a constant independent of the number of steps (for constant coefficients, ).
- Convergent: the numerical solution at a fixed time approaches the exact one as the grid is refined.
Lax equivalence theorem (Lax and Richtmyer, 1956, from memory). For a well-posed linear initial value problem and a consistent scheme, stability is necessary and sufficient for convergence. Consistency plus stability equals convergence. The proof is not given here.
The intuition is bookkeeping. Each step plants a small local error (the truncation error), and the error at time is the sum of all of them, each carried forward by the remaining steps. If the scheme is stable, carrying forward never amplifies, so the sum is about times the local error, which vanishes by consistency. If it is unstable, early errors are multiplied by huge factors and convergence fails however small the local error. Consistency is routine Taylor series, so the theorem turns a stability check into a convergence proof. Centred advection is the standing example: consistent, unstable, not convergent. Its lab pulse grows instead of translating.
The limits matter for fluids. Von Neumann analysis assumes constant coefficients and a periodic or infinite domain. For variable coefficients the practice is to freeze them and test locally (from memory: a necessary check, not a proof); boundaries and nonlinear equations such as Burgers’ need more tools.
The lab
The domain is periodic with nodes, , plus noise of . Panels: the pulse against the exact solution (dashed); with the unstable band shaded and the exact modulus as dots; the speed ratio; .
- Centred, , square pulse (first button). Largest at , and the band is modes to : all of them. is at step and at step ; blown up at step . Measured growth per step wanders between and , around . The Gaussian takes steps.
- Upwind, . The curve stays below (largest , at the longest wave) and the speed ratio is flat at . is at step and at step : smeared, not growing.
- Upwind, . The band is every mode; worst at . is at step ; blown up at step , growth . The red vanishes at .
- Lax-Friedrichs. At the largest modulus is at , and one lap leaves peak . At the band is modes, worst at , blown up at step .
- FTCS diffusion, (last button). The band is modes to ( from ; the exact edge lies between modes and ), worst . is at step , then at step ; blown up at step , growth .
The blow-up steps in items 3 to 5, and the Gaussian’s in item 1, are for the smooth Gaussian pulse. The square pulse’s sharp edges feed the unstable modes more energy at the start, so it blows up sooner; try it with the pulse menu.
Computing it
The output is at ; at ; and at .
Because the grid is periodic, the wave with fits it exactly and one step really does multiply it by one number: the same value for every , so reading is enough. This is the von Neumann analysis done by machine, and it is how you check an algebraic for a scheme you have just written.
Concept checks
Problems
Find for upwind with at and .
Show worked solution
. At , and . At , : the sawtooth is wiped out in one step. The shortest wave is damped most, the long waves hardly at all: numerical diffusion.
Centred advection starts from noise of in every wave. How many steps until the worst wave reaches size , at and at ?
Show worked solution
The worst wave is , . For : steps. For : and steps. A smaller delays the failure, but never prevents it.
(a) Show Lax-Friedrichs is the centred scheme plus diffusion with . (b) Derive . (c) Where, and how small, is at ?
Show worked solution
(a) , so the scheme is the centred step plus an FTCS diffusion step with . (b) . (c) For the minimum is at , : . At and it is : mid-length waves are smeared most.
For take . Show it is stable exactly when .
Show worked solution
With and , and
The bracket must be nonnegative on . It is linear in , so check the ends: gives ; gives , so . Physical diffusion cures the centred scheme only when , which for small viscosity is far below the CFL step.
What comes next
The trick of substituting a wave and reading off one number applies equally to implicit schemes. In 10.4 Implicit Methods & Crank–Nicolson we put the diffusion term at the new time level: backward Euler gives and Crank-Nicolson . The unknown now sits in a denominator, and both stay inside the unit circle for every . The price is a tridiagonal solve per step, which is how Stam’s solver diffuses momentum.
Key Takeaways
- Put , , into a linear constant-coefficient scheme and solve for : modulus is growth per step, phase is motion per step; suffices.
- Von Neumann condition: for all . The set where it fails is the unstable band, which grows geometrically from rounding noise.
- FTCS diffusion: , stable for , with no matrix needed.
- Centred advection: , unstable for every fixed (forward Euler on imaginary eigenvalues).
- Upwind: , stable exactly for . Lax-Friedrichs, , stabilises the centred scheme by adding diffusion.
- is numerical diffusion (upwind: viscosity ); gives numerical dispersion, waves at the wrong speed.
- Lax equivalence: consistent plus stable equals convergent for well-posed linear problems (proof not given); boundaries, variable coefficients and nonlinearity need more.
- Next: implicit methods put in a denominator, stable for every step at the cost of a linear solve.