In 10.3 Von Neumann Stability Analysis we pushed three schemes through the advection equation. The centred one blew up for every step. Upwind and Lax-Friedrichs were stable for but smeared a pulse to half its height in one lap: simulated smoke turns to fog. A more accurate scheme, Lax-Wendroff, takes two lines to build. It fixes the smearing and replaces it with ripples that dip below zero. A theorem then says the trade is unavoidable for any linear scheme, and the way out is a nonlinear scheme that decides, node by node, how much accuracy it can afford.
Transcript
- The centred scheme blows up for every step. Add a dose of diffusion, epsilon times the second difference, and it is repaired. Lax-Friedrichs adds one half; upwind adds c over two. Stability needs c squared at most two epsilon, so the smallest stable dose is c squared over two. That scheme exists, and it is Lax-Wendroff.
- Forward Euler is a Taylor series cut after one term. Keep the next. The equation turns u t t into a squared u x x, which is diffusion with exactly the missing sign. Centred differences for both space derivatives give Lax-Wendroff: the centred scheme plus c squared over two, second order.
- Its amplification factor has modulus squared 1 minus 4 c squared, times 1 minus c squared, times sine to the fourth of theta over 2. At c equals 0.5 and theta equals pi over 2, Lax-Wendroff gives 0.8125 and upwind 0.5. The damping is fourth order in theta, so long waves are barely touched.
- What equation does a scheme really solve? Expand it, and trade time derivatives for space derivatives. Upwind solves advection plus diffusion, with viscosity one half a h times 1 minus c. In the lab, mode 4 after one lap: the modified equation predicts 0.4540, the von Neumann factor gives 0.4538, and the measurement is 0.4538.
- Lax-Wendroff cancels the diffusion. What is left is a third derivative: dispersion. Short waves travel slower, so the high-frequency part of a sharp edge lags and trails it as ripples. For mode 16 the modified equation predicts a speed ratio of 0.9684, the factor G gives 0.9694, and the lab measures 0.9694.
- Now a square pulse: 200 nodes, c equals 0.5, one lap of 400 steps. Upwind never goes above 0.9544, but it rounds both corners. Lax-Wendroff keeps the edges sharp, but reaches 1.2321 and dips to minus 0.2313. Total variation, the total up and down travelled, is 3.847 against 2 for the clean pulse.
- On the smooth bump, upwind's peak falls to 0.5772, and Lax-Friedrichs to 0.3777. Lax-Wendroff stays close to the exact curve. Its L 2 error is 0.0231, four times smaller than upwind's 0.1012. Where the data are smooth, second order pays off.
- Is the trade an accident? Godunov's theorem says a linear scheme with no new extrema is at most first order. Second order needs this sum to be zero. If every weight is nonnegative, each term is zero, which is impossible. So second order needs a negative weight: Lax-Wendroff has one, upwind has none.
- The way out is a scheme that is nonlinear on purpose. Write Lax-Wendroff as upwind plus a correction, and scale the correction by phi of r, where r compares the slope behind a face with the slope ahead. Phi equal to 1 is Lax-Wendroff; phi equal to 0 is upwind. At a peak, r is negative and the scheme falls back to upwind. On a periodic grid the fluxes telescope, so the sum of u cannot change.
- Three standard limiters. Minmod is the most cautious. Van Leer is a smooth curve. Superbee is the boldest, and sharpens jumps. All pass through phi equals 1 at r equals 1, so they are second order on smooth data, and all lie inside Sweby's region, which makes them total variation diminishing. The price is at a smooth peak, where phi drops to zero and the scheme shaves the top.
- One lap at c equals 0.5, with both pulses together, so the starting total variation is 4. Upwind: total variation 3.055, L 2 error 0.1835. Lax-Wendroff: 5.829 and 0.1198. Minmod: 3.720 and 0.0949. Superbee: 3.939 and 0.0510. Lax-Wendroff's L 2 error looks decent, but its ripples show in the total variation. Minmod shaves the bump's top to 0.8603.
- Does Lax-Wendroff really reach second order? Refine the grid from 100 to 800 nodes. Its observed orders are 1.64, 1.94 and 1.99. Upwind's are 0.42, 0.57 and 0.71, climbing toward 1 slowly, because its smearing must first shrink below the width of the pulse.
- To recap: every scheme is the centred one plus diffusion. Lax-Wendroff cancels it and gets dispersion; Godunov says a linear scheme cannot be second order and ripple-free, and limiters escape by being nonlinear. But all of these are tied to c at most 1. Next, semi-Lagrangian advection traces characteristics back and interpolates, stable at any step. Godunov returns: linear interpolation is upwind, and cubic has a negative weight.
Three schemes, one pattern
The equation is on a periodic grid of spacing , with CFL number as before. Write for the second difference. The centred step is , with : unstable at every . Adding to it, which is an explicit diffusion step with , gives
- Lax-Friedrichs, .
- Upwind, . Expand and compare: it is exactly centred plus .
So the stable schemes of 10.3 Von Neumann Stability Analysis are the broken one with a repair dose. The problem at the end of that lesson found the exact dose needed: the centred scheme with diffusion is stable when . The smallest stable dose is , and for we have . Lax-Friedrichs adds the most diffusion, upwind less, and a scheme with would add the least that still works. That scheme exists, and it is the next section.
Lax-Wendroff from the Taylor series
Forward Euler in time is a Taylor series cut after one term. Keep the next one:
The equation turns time derivatives into space derivatives (9.10 First-Order PDEs: Advection & Characteristics used the same fact): , and differentiating once more, . Hence
Replace by the centred difference and by :
This is Lax-Wendroff (Lax and Wendroff, 1960, from memory). It is the centred scheme plus : the exact smallest dose, and now we see why. Forward Euler in time drops the term, which is a diffusion term with a sign that removes viscosity, and that missing term is the instability. Lax-Wendroff puts it back. The error is : second order.
Its amplification factor follows by the usual substitution, with :
With the real part is and , so , which simplifies to the formula. It is at most exactly when , and at it is the exact shift again. For comparison, at and : Lax-Wendroff has and upwind has (formula from the last lesson). Its damping is of fourth order in , so long waves are barely touched. Its phase is another matter.
What equation does the scheme actually solve?
The truncation error says how a scheme fails to satisfy the PDE. The modified equation turns that into a statement you can reason about: the scheme solves a different PDE, to a higher order of accuracy than it solves the original (Warming and Hyett, 1974, from memory). To find it, Taylor-expand every term of the scheme about , then use the equation itself to trade time derivatives for space derivatives.
Upwind. The scheme is . Expanding,
At leading order , and , so
Upwind solves an advection-diffusion equation. Its viscosity is the one we read off from last time, now derived from the scheme rather than from a wave. The same bookkeeping explains the whole pattern: a dose adds of diffusion, forward Euler subtracts , and the net is . Check upwind: gives .
Lax-Wendroff. Here cancels the diffusion, so the leading error is the next one (what is left of is itself and enters at third order). Carrying the expansion one order further (the centred differences contribute , the time series contributes with ) gives
A third derivative is dispersion. For a wave this equation gives : the phase speed is with . Shorter waves travel slower, and with always. A sharp edge is a sum of many short waves, so the high-frequency part lags behind the main step and shows up as a ripple trailing the jump.
The rule: an even derivative in the modified equation (second, fourth) is diffusion, which smooths; an odd one (third) is dispersion, which tilts phases. First-order schemes smear, second-order linear schemes ripple. Both defects come from a Taylor series cut short.
Does the sim agree?
The lab’s mode readout compares one Fourier mode of the numerical solution with the same mode of the exact one. Smooth bump alone, , , one period of steps:
- Upwind, mode (): the modified equation predicts the amplitude falls by ; the von Neumann factor gives ; the measured ratio is . At : , , . The speed ratio is , as the last lesson found for .
- Lax-Wendroff, mode (, nodes per wave): the modified equation predicts a speed ratio ; gives ; the measurement is . Per lap this wave is slow: a lag of nodes, nearly half its wavelength, with amplitude down to .
The modified equation is off by at , as an truncation should be; matches the measurement to four digits, as it must for a linear scheme.
Godunov’s theorem: the trade cannot be dodged
Upwind never creates a new maximum, since is an average and cannot exceed its inputs. Lax-Wendroff has a negative weight, on , and overshoots. Is that an accident of one scheme?
Godunov’s theorem (1959, from memory): a linear scheme that is monotone, meaning it creates no new extrema, is at most first-order accurate. The proof is not given here. For nonnegative weights there is a short argument that carries the idea. Write any linear scheme as . It is exact for the data , , (the definition of second order, since each is shifted exactly by the true solution) when, in index units,
Now compute . If every , each term of this sum is nonnegative, so each is zero: all the weight sits at , impossible for a fractional . Second order forces a negative weight. Look at the weights as a probability distribution: second order demands its variance about the true foot be zero. Upwind has weights at and at , with : the numerical diffusion per step, in cells squared. Lax-Wendroff has weights , and : they sum to , the variance is zero, and one of them is negative.
So no choice of linear coefficients gives sharp and clean. The theorem hits only schemes whose coefficients are fixed numbers. A scheme whose coefficients depend on the data is nonlinear even for a linear PDE, and escapes.
Flux limiters: nonlinear on purpose
Write each scheme in conservation form, , with the flux through the face between nodes and :
On a periodic grid the sum of cannot change, since fluxes telescope. Lax-Wendroff is upwind plus a correction. A flux-limited scheme scales the correction by a factor chosen at each face:
The ratio compares the slope behind the face with the slope ahead. On smooth monotone data it is close to ; at a local maximum the differences have opposite signs, so ; near a jump one difference dwarfs the other. Then is Lax-Wendroff and is upwind. Three standard choices (from memory for their origins: van Leer, Roe, and the minmod family):
- Minmod: , the most cautious, never above Lax-Wendroff.
- Van Leer: , a smooth curve.
- Superbee: , the boldest, which sharpens jumps.
All three have , so on smooth data they are Lax-Wendroff and second order. All have for , so at an extremum they drop to upwind and cannot grow a new bump.
The test for “no new wiggles” is the total variation, , the total up-and-down travelled along the profile. A single pulse has ; a spurious ripple adds to it. A scheme is TVD (total variation diminishing, Harten, 1983, from memory) if always. TVD implies no new extrema and no overshoot. Sweby (1984, from memory) showed that for a flux-limited scheme is TVD when for and for : the shaded region in the lab’s bottom panel. The three limiters above lie inside it; Lax-Wendroff () leaves it for .
The price is local accuracy at extrema. At a smooth peak , , and the scheme is upwind exactly where the profile is sharpest, so a limited scheme shaves the tops of smooth bumps. The lab shows how much.
The lab
The domain is periodic with nodes, , , one period steps ( at ). The square pulse is on ; the bump is , ten nodes to its point. Press jump to one period to read the numbers after one lap. All of the following are for , steps, both pulses together (default buttons), so the initial total variation is (two for each pulse):
- Upwind. Max , min (it never goes negative), TV , error . The bump peak falls to alone.
- Lax-Wendroff. Max , min , TV , error . The extremes belong to the square pulse: above the top and of its height below zero, in ripples trailing each edge (the minimum is at node , behind the left edge at node ). The bump alone, from the pulse menu: max , min , error , four times smaller than upwind’s .
- Minmod. Max , min , TV , . No ripples. The bump alone peaks at : the shaved top.
- Superbee. Max , min , TV , . The square stays almost square (its error alone is , against for upwind). The bump alone peaks at against for van Leer and for minmod.
- Mass. Every scheme keeps the starting mass .
- Failure. At Lax-Wendroff fails like upwind did: at and, for the bump, passes at step .
Lax-Wendroff’s error on the square pulse alone () beats upwind’s (), yet its shape is worse for anything that must stay in . Total variation, max and min see the ripples; does not.
Computing it
The output is for upwind and for Lax-Wendroff at to . Lax-Wendroff’s observed orders are : it reaches . Upwind’s are and climb toward slowly, because the smearing variance must shrink well below the pulse’s own variance before first order shows: at it is , still half of it. A first-order scheme needs a very fine grid before its asymptotics even begin.
Plot one_period(lax_wendroff, s0, 0.5) against s0 and find the ripples behind each edge. Then try : the minimum becomes .
Concept checks
Problems
For list the stencil weights of upwind and of Lax-Wendroff. Verify and for both, then compute and .
Show worked solution
Upwind: , . Lax-Wendroff: , , . Both give and . Upwind has , not , so it is not second order, and . Lax-Wendroff has (second order) and , which it achieves only through the negative weight .
Show that upwind with on a periodic grid satisfies .
Show worked solution
Let . From , subtract the same formula at and : the new difference is . Both weights are nonnegative, so . Summing over all on the periodic grid, each of the two sums is the old , so . For the weight is negative and the argument fails.
Lax-Friedrichs is centred plus . With the net diffusion , find for , , and predict the peak of the bump (a Gaussian , variance ) after one lap, . Compare with the lab.
Show worked solution
, so and . Diffusion adds to the variance: . The peak scales as . The lab (Lax-Friedrichs, bump, , steps) gives . Upwind, , gives ; the lab shows .
What comes next
Every scheme here looks only a cell or two away, so all are tied to . The next lesson, semi-Lagrangian advection, drops that tie. It traces each node back along the characteristic of 9.10 First-Order PDEs: Advection & Characteristics and interpolates, which is Stam’s advection step (11.11 Stam's Stable Fluids, Step by Step), stable at any step. Godunov’s theorem comes straight back: for linear interpolation is upwind, with nonnegative weights, so it smears. Cubic interpolation has a negative weight, so it sharpens and can overshoot.
Two later lessons come back to the nonlinear case this one prepares. In a nonlinear-waves lesson on Burgers’ equation (9.11) the speed depends on the solution and a shock forms from smooth data, so a scheme that creates ripples at jumps is a scheme that fails exactly where the physics gets interesting. The finite-volume lesson (10.10) makes the conservation form used above the foundation, with limited upwind fluxes at the cell faces.
Key Takeaways
- Centred, upwind, Lax-Friedrichs and Lax-Wendroff differ by a dose of diffusion: , , , . Stability needs .
- Lax-Wendroff keeps with : second order, , stable for .
- The modified equation is the PDE the scheme really solves: upwind has diffusion and smears; Lax-Wendroff has the dispersive term , so short waves lag and ripples trail jumps. The lab agrees with both.
- At , , one lap, a square pulse through Lax-Wendroff reaches and , with total variation against .
- Godunov’s theorem: a linear scheme with no new extrema is at most first order. Second order forces , impossible with all . (General proof not given.)
- Flux limiters blend upwind and Lax-Wendroff with . They are nonlinear, TVD inside Sweby’s region, second order on smooth data and first order at extrema.
- Total variation, max and min catch ripples that hides.
- Next: semi-Lagrangian advection removes and meets the same trade through interpolation weights.