43.11.04 · numerical-analysis / 11-finite-difference-pdes

Hyperbolic finite differences: upwind, Lax-Friedrichs, Lax-Wendroff; numerical diffusion and dispersion

shipped3 tiersLean: none

Anchor (Master): LeVeque 2002 *Finite Volume Methods for Hyperbolic Problems* (Cambridge) Ch. 8-12, §8.6 (the modified-equation analysis, numerical diffusion and dispersion, Godunov's order-barrier theorem, and monotone vs. high-resolution schemes for scalar conservation laws); Richtmyer-Morton 1967 *Difference Methods for Initial-Value Problems* 2e (Interscience) Ch. 5, 12-13 (the Lax-Wendroff scheme, dissipation and dispersion of difference schemes, and the heat-equation analogy of the modified equation); Hirsch 2007 *Numerical Computation of Internal and External Flows* 2e (Butterworth-Heinemann) Ch. 8-10 (the modified-equation/equivalent-differential-equation method, numerical dissipation and dispersion error, and monotonicity for convection schemes)

Intuition Beginner

Picture a coloured pulse painted onto water in a long, straight canal, with the water moving at a steady speed. An hour later the pulse has slid downstream, unchanged in shape — every part of it carried at the same speed. That sliding-without-changing is what the simplest moving-wave rule, the advection equation $u_{t} + a u_{x} = 0$ , describes: a profile travels rightward at the fixed speed $a$ and nothing else happens to it. This unit asks how a grid-and-clock computer can reproduce that clean slide, and why its first honest attempts smear the pulse or wrap it in ripples.

The trouble is that the true rule reads its answer from one upstream spot — the place the water just came from — while a grid only stores values at fixed dots. To advance a dot, a scheme must blend a few neighbour values, never a perfect copy of that one spot. The natural fix is to look in the right direction: since the flow comes from the left when $a$ is positive, build each new value from the dot and its left neighbour. That is the upwind scheme, the cheapest correct idea, leaning on the speed-limit from the previous unit 43.11.03 — the signal must not outrun the grid in one tick.

Upwind works, but it pays a price. Blending a value with its left neighbour is a kind of averaging, and averaging always softens. So the computed pulse, step after step, loses height and spreads out, as if the canal had grown sticky. This artificial stickiness is called numerical diffusion: the scheme has quietly added a smear the true equation never asked for. A close cousin, the Lax-Friedrichs scheme, replaces the centre value by the average of its two neighbours; it is even easier to write down and even smearier.

To stop the smearing you reach for a sharper, second-order scheme — the Lax-Wendroff scheme — which matches the true motion more closely and keeps the pulse tall. But sharper schemes trade one fault for another. Instead of softening the pulse they make different wavelengths travel at slightly different speeds, so a crisp edge sheds a train of little ripples behind it. This is numerical dispersion: not a loss of height but a scrambling of timing, spurious wiggles where the true answer is smooth. The story of this unit is that simple linear schemes must pick their poison — smear or wiggle — and Godunov's theorem says no fixed linear recipe escapes the choice.

Visual Beginner

There are two pictures. The first compares the three schemes on a single travelling step. The second sorts the error into the two flavours: diffusion (the pulse shrinks and spreads) and dispersion (the pulse grows a ripple tail).

The table lists the schemes by how they build each new value, their accuracy order, and the kind of error they leave behind. The Courant number $ν = ak / h$ — speed times time-step over spacing, from the previous unit 43.11.03 — must stay at most one for any of them to be stable.

scheme	how it builds the new value	order	error flavour
upwind	the dot blended with its upwind (left, if $a > 0$ ) neighbour	first	numerical diffusion (smearing)
Lax-Friedrichs	the average of the two neighbours, then nudged downstream	first	numerical diffusion (more smearing)
Lax-Wendroff	a centred update plus a correction matching the true curvature	second	numerical dispersion (ripples)

 a step function carried right (true answer: same step, shifted)

  upwind / Lax-Friedrichs            Lax-Wendroff
  (numerical diffusion):            (numerical dispersion):

   true ___                          true ___
       |   |                             |   |
   ____|   |____ shifted            ____|   |____ shifted
                                                  ^
   computed: edge rounded off       computed: sharp edge, but a
   ____                             train of ripples behind it
       \____                        ____      _
            \___ smeared slope          |   |/ \  /\___ wiggles
                                    ____|   |   \/

The takeaway: the schemes split into two camps by the kind of error they make. First-order schemes (upwind, Lax-Friedrichs) add a smear — numerical diffusion — and are gentle but blurry. The second-order Lax-Wendroff scheme keeps edges sharp but adds ripples — numerical dispersion. Stability for all of them needs the Courant number $ν \leq 1$ , the same speed limit as in 43.11.03.

Worked example Beginner

Let us carry a single step one tick with the upwind scheme and watch it round off the corner — the smearing made concrete. Take the flow speed $a = 1$ moving rightward, spacing $h = 1$ , time step $k = 1/2$ , so the Courant number is $ν = ak / h = 1/2$ .

The upwind rule for rightward flow updates each value from itself and its left neighbour: $U_{j}^{new} = U_{j} - ν (U_{j} - U_{j - 1})$ . With $ν = 1/2$ this is $U_{j}^{new} = U_{j} - \frac{1}{2} (U_{j} - U_{j - 1}) = \frac{1}{2} U_{j} + \frac{1}{2} U_{j - 1}$ — the new value is the plain average of the dot and its left neighbour.

Start from a sharp step: the values are $\dots, 1, 1, 1, 0, 0, 0, \dots$ , jumping from $1$ down to $0$ between two dots. Name the last $1$ as position $2$ and the first $0$ as position $3$ .

Step 1. Update position $2$ (value $1$ , left neighbour value $1$ ): $\frac{1}{2} (1) + \frac{1}{2} (1) = 1$ . No change — both inputs were $1$ .

Step 2. Update position $3$ (value $0$ , left neighbour value $1$ ): $\frac{1}{2} (0) + \frac{1}{2} (1) = \frac{1}{2}$ . The first $0$ has been lifted to $\frac{1}{2}$ .

Step 3. Update position $4$ (value $0$ , left neighbour value $0$ ): $\frac{1}{2} (0) + \frac{1}{2} (0) = 0$ . Still zero.

Step 4. Collect the new row: $\dots, 1, 1, \frac{1}{2}, 0, 0, \dots$ . The clean jump from $1$ to $0$ has become a two-step ramp $1, \frac{1}{2}, 0$ . The corner has been rounded; the edge is one cell wider than it was.

What this tells us: a single upwind step turned a crisp jump into a softened ramp, without any sign of overshoot. That softening is numerical diffusion — the scheme behaving as though a little stickiness were smoothing the profile. Keep stepping and the ramp keeps widening, the step blurring more each tick, exactly the smearing the formal modified-equation analysis will pin to an artificial $u_{xx}$ term.

Check your understanding Beginner

Formal definition Intermediate+

Work on the uniform grid $x_{j} = j h$ , $j \in Z$ , with time step $k$ , time levels $t_{n} = nk$ , and grid values $U_{j}^{n} \approx u (x_{j}, t_{n})$ approximating the solution of the linear advection (transport) equation $$ u_t + a,u_x = 0, \qquad x \in \mathbb{R},\ t > 0, \qquad u(x,0) = u_0(x), $$ with constant speed $a$ . Its exact solution is $u (x, t) = u_{0} (x - a t)$ : the initial profile is transported rigidly at speed $a$ along the characteristics $x - a t = const$ , the continuous theory of 02.13.04. The single dimensionless parameter governing every scheme below is the Courant number $ν := ak / h$ of 43.11.03.

The three schemes. Take $a > 0$ for the one-sided scheme. The first-order upwind scheme differences in the upwind direction, $$ U_j^{n+1} = U_j^n - \nu,(U_j^n - U_{j-1}^n) \qquad (a > 0), $$ using the dot and its upstream neighbour (for $a < 0$ one uses $U_{j + 1}^{n} - U_{j}^{n}$ ). The Lax-Friedrichs scheme replaces the centre value in a forward-time centred-space update by the neighbour average, $$ U_j^{n+1} = \tfrac12\big(U_{j-1}^n + U_{j+1}^n\big) - \tfrac{\nu}{2}\big(U_{j+1}^n - U_{j-1}^n\big). $$ The Lax-Wendroff scheme adds to the centred update a centred second-difference correction whose weight is $ν^{2} /2$ , $$ U_j^{n+1} = U_j^n - \tfrac{\nu}{2}\big(U_{j+1}^n - U_{j-1}^n\big) + \tfrac{\nu^2}{2}\big(U_{j-1}^n - 2U_j^n + U_{j+1}^n\big). $$ The centred-only scheme $U_{j}^{n + 1} = U_{j}^{n} - \frac{ν}{2} (U_{j + 1}^{n} - U_{j - 1}^{n})$ — Lax-Wendroff without its correction — is the unconditionally unstable forward-time centred-space scheme proved unstable in 43.11.03; it is the witness that the CFL condition is necessary but not sufficient. Stability of upwind, Lax-Friedrichs, and Lax-Wendroff is exactly $∣ ν ∣ \leq 1$ , the von Neumann analysis carried out in 43.11.03.

The modified equation. A scheme of accuracy order $p$ for $u_{t} + a u_{x} = 0$ solves, to one order higher, an equivalent or modified equation $u_{t} + a u_{x} = \sum_{m \geq p + 1} c_{m} \partial_{x}^{m} u$ , obtained by Taylor-expanding the scheme about $(x_{j}, t_{n})$ and repeatedly using the equation itself (and its differential consequences such as $u_{tt} = a^{2} u_{xx}$ ) to convert all time derivatives into space derivatives. The leading term on the right is the truncation error in differential form. Its parity determines the error type. An even-order leading term $c u_{xx}$ with $c > 0$ is a diffusion (parabolic) term: it damps the amplitude of each Fourier mode, producing numerical diffusion — the dissipative smearing of upwind and Lax-Friedrichs. An odd-order leading term $d u_{xxx}$ is a dispersion term: it leaves amplitudes intact but makes the phase speed depend on wavenumber, producing numerical dispersion — the spurious oscillations of Lax-Wendroff.

The symbols $ν = ak / h$ (Courant number), the advection speed $a$ , the diffusion coefficient of the modified equation, the second-difference $δ^{2} U_{j} = U_{j - 1} - 2 U_{j} + U_{j + 1}$ , and the centred difference $δ_{0} U_{j} = U_{j + 1} - U_{j - 1}$ are recorded in _meta/NOTATION.md.

Counterexamples to common slips

Numerical diffusion is not round-off and not physical viscosity. It is a deterministic, scheme-induced term in the modified equation, present in exact arithmetic; its coefficient $\frac{ah}{2} (1 - ν)$ scales with the mesh $h$ and vanishes only as $h \to 0$ or at $ν = 1$ , where upwind becomes exact transport by one cell.
Higher order does not mean smaller error on a discontinuity. Lax-Wendroff is second-order for smooth data, but at a jump its dispersive $u_{xxx}$ term produces $O (1)$ oscillations that do not shrink with refinement near the discontinuity; first-order upwind, though only $O (h)$ accurate, gives a monotone, oscillation-free front. Order is an asymptotic statement about smooth solutions.
The centred scheme satisfies CFL yet is useless. Its stencil reaches one cell each side, so $∣ ν ∣ \leq 1$ meets the CFL necessary condition of 43.11.03; but its amplification factor has $∣ g ∣ > 1$ for every $ν > 0$ , so it is unconditionally unstable. CFL screens domains of dependence; it does not certify stability.
The diffusion coefficient must be nonnegative for stability. The upwind modified-equation coefficient is $\frac{ah}{2} (1 - ν) \geq 0$ exactly when $0 \leq ν \leq 1$ ; a negative diffusion coefficient is anti-diffusion, which amplifies modes and is the differential signature of instability — the same threshold $∣ ν ∣ \leq 1$ seen from the modified equation rather than the amplification factor.

Key theorem with proof Intermediate+

The signature result is the modified-equation classification: upwind and Lax-Friedrichs are first-order with an even-derivative leading error, hence diffusive; Lax-Wendroff is second-order with an odd-derivative leading error, hence dispersive. The mechanism is a single Taylor expansion of each scheme, with time derivatives traded for space derivatives through $u_{t} = - a u_{x}$ and $u_{tt} = a^{2} u_{xx}$ ^{[LeVeque, R. J. — Finite Difference Methods for Ordinary and Partial Differential Equations: Steady-State and Time-Dependent Problems; Strikwerda, J. C. — Finite Difference Schemes and Partial Differential Equations (2nd ed.)]}.

Theorem (modified equations of the advection schemes). Let $u$ be smooth and $ν = ak / h$ . Inserting the exact solution of $u_{t} + a u_{x} = 0$ into each scheme and expanding gives the following modified equations, satisfied to one order beyond the scheme's truncation order:

(i) Upwind ( $a > 0$ ) is first-order and solves $$ u_t + a u_x = \frac{ah}{2},(1 - \nu),u_{xx} + O(h^2), $$ a diffusion equation with nonnegative coefficient $\frac{ah}{2} (1 - ν) \geq 0$ for $0 \leq ν \leq 1$ .

(ii) Lax-Wendroff is second-order and solves $$ u_t + a u_x = -\frac{ah^2}{6},(1 - \nu^2),u_{xxx} + O(h^3), $$ a dispersion equation: no $u_{xx}$ term, leading correction $u_{xxx}$ .

Proof. Write $u = u (x_{j}, t_{n})$ and abbreviate $u_{x}, u_{xx}, \dots$ for its space derivatives there. Throughout, use the differential consequences of $u_{t} + a u_{x} = 0$ : $u_{t} = - a u_{x}$ , and differentiating, $u_{tt} = - a u_{x t} = - a (u_{t})_{x} = a^{2} u_{xx}$ , and likewise $u_{ttt} = - a^{3} u_{xxx}$ .

(i) Upwind. The scheme's residual when the exact solution is inserted is $$ R = \frac{u(x_j, t_{n+1}) - u(x_j,t_n)}{k} + a,\frac{u(x_j,t_n) - u(x_{j-1},t_n)}{h}. $$ Expand each difference. The time difference is $\frac{1}{k} (k u_{t} + \frac{k ^{2}}{2} u_{tt} + O (k^{3})) = u_{t} + \frac{k}{2} u_{tt} + O (k^{2})$ . The one-sided space difference is $\frac{1}{h} (h u_{x} - \frac{h ^{2}}{2} u_{xx} + O (h^{3})) = u_{x} - \frac{h}{2} u_{xx} + O (h^{2})$ . Hence $$ R = \big(u_t + a u_x\big) + \frac{k}{2}u_{tt} - \frac{ah}{2}u_{xx} + O(k^2 + h^2). $$ The first bracket vanishes. Replace $u_{tt} = a^{2} u_{xx}$ and $k = ν h / a$ : $$ R = \frac{k}{2}a^2 u_{xx} - \frac{ah}{2}u_{xx} + O(h^2) = \frac{a^2}{2}\cdot\frac{\nu h}{a},u_{xx} - \frac{ah}{2}u_{xx} + O(h^2) = \frac{ah}{2}\big(\nu - 1\big)u_{xx} + O(h^2). $$ Since the scheme sets its own update equal to the advection part, the exact solution satisfies $u_{t} + a u_{x} = - R + O (\dots) = \frac{ah}{2} (1 - ν) u_{xx} + O (h^{2})$ , the claimed diffusion equation, with leading error $O (h)$ so the scheme is first-order. The coefficient $\frac{ah}{2} (1 - ν)$ is nonnegative for $0 \leq ν \leq 1$ .

(ii) Lax-Wendroff. The scheme is built to be second-order, so all $u_{t} + a u_{x}$ , $u_{xx}$ -type residuals cancel through second order; one expands to third order. The time advance, with $u_{t} = - a u_{x}$ , $u_{tt} = a^{2} u_{xx}$ , $u_{ttt} = - a^{3} u_{xxx}$ , is $$ u(x_j, t_{n+1}) = u + k u_t + \tfrac{k^2}{2}u_{tt} + \tfrac{k^3}{6}u_{ttt} + O(k^4) = u - ak,u_x + \tfrac{a^2 k^2}{2}u_{xx} - \tfrac{a^3 k^3}{6}u_{xxx} + O(k^4). $$ The scheme's spatial part is the centred first difference $- \frac{ν}{2} δ_{0} u = - ak u_{x} - \frac{ak h ^{2}}{6} u_{xxx} + O (h^{4})$ (the centred difference has error $\frac{h ^{2}}{6} u_{xxx}$ ), plus the correction $\frac{ν ^{2}}{2} δ^{2} u = \frac{a ^{2} k ^{2}}{2 h ^{2}} (h^{2} u_{xx} + \frac{h ^{4}}{12} u_{xxxx} + O (h^{6})) = \frac{a ^{2} k ^{2}}{2} u_{xx} + O (k^{2} h^{2})$ . The $u_{x}$ terms match, and the $\frac{a ^{2} k ^{2}}{2} u_{xx}$ produced by the correction cancels the $\frac{a ^{2} k ^{2}}{2} u_{xx}$ from the time advance — this cancellation is exactly why the second-order accuracy and why no diffusion term survives. Collecting the surviving third-order terms, the residual is $$ R = \Big(!-\tfrac{a^3 k^3}{6} + \tfrac{a k h^2}{6}\Big)u_{xxx} + O(h^3). $$ Factor $\frac{ak h ^{2}}{6}$ and use $a^{2} k^{2} / h^{2} = ν^{2}$ : $- \frac{a ^{3} k ^{3}}{6} + \frac{ak h ^{2}}{6} = \frac{ak h ^{2}}{6} (1 - \frac{a ^{2} k ^{2}}{h ^{2}}) = \frac{ak h ^{2}}{6} (1 - ν^{2})$ . With $ak = ν h$ this is $\frac{ν h ^{3}}{6} (1 - ν^{2})$ , an $O (h^{2})$ residual divided by $k$ , confirming second order, and the modified equation reads $u_{t} + a u_{x} = - R = - \frac{a h ^{2}}{6} (1 - ν^{2}) u_{xxx} + O (h^{3})$ , with leading odd-derivative dispersion term and no $u_{xx}$ . $□$

Bridge. This theorem is the foundational reason the two error types are mutually exclusive at leading order for these schemes: the parity of the surviving derivative is fixed by the scheme's accuracy order, even orders giving the dissipative $u_{xx}$ and odd orders the dispersive $u_{xxx}$ , and a second-order scheme has annihilated its $u_{xx}$ term by construction so its leading error must be odd. This is exactly the amplitude-versus-phase split of the von Neumann amplification factor of 43.11.03: the modulus $∣ g (ξ) ∣$ records the even, diffusive part of the truncation error and the phase $ar g g (ξ)$ records the odd, dispersive part, so the modified equation and the symbol are dual encodings of one expansion — putting these together, $∣ g ∣ < 1$ is numerical diffusion and a wavenumber-dependent $ar g g$ is numerical dispersion. The diffusion coefficient $\frac{ah}{2} (1 - ν)$ generalises the artificial-viscosity reading of Lax-Friedrichs and builds toward the monotonicity theory below, where positive numerical diffusion is what buys an oscillation-free front. The central insight that one Taylor expansion governs both order and error character appears again in the Lax-Richtmyer equivalence theorem 43.11.05, where consistency (the order) and stability (the bounded amplification) combine into convergence, the bridge being that the modified equation is the differential face of the same consistency-plus-stability computation that von Neumann analysis performs algebraically.

Exercises Intermediate+

Exercise 3 (medium, symbolic).

Derive the amplification factor of the upwind scheme ( $a > 0$ ), $U_{j}^{n + 1} = U_{j}^{n} - ν (U_{j}^{n} - U_{j - 1}^{n})$ , and show $∣ g ∣^{2} = 1 - 2 ν (1 - ν) (1 - cos ξ h)$ . Read off the diffusion: for small $ξ h$ , $∣ g ∣ \approx 1 - \frac{ν ( 1 - ν )}{2} (ξ h)^{2}$ , a second-order amplitude decay.

Hint

Substitute $U_{j}^{n} = g^{n} e^{i ξ j h}$ ; collect $g = (1 - ν) + ν e^{- i ξ h}$ , then $∣ g ∣^{2} = g \overset{g}{ˉ}$ .

Answer

Substituting gives $g = 1 - ν (1 - e^{- i ξ h}) = (1 - ν) + ν e^{- i ξ h}$ . Then $∣ g ∣^{2} = (1 - ν)^{2} + 2 ν (1 - ν) cos ξ h + ν^{2} = [(1 - ν)^{2} + ν^{2}] + 2 ν (1 - ν) cos ξ h$ . Since $(1 - ν)^{2} + ν^{2} = 1 - 2 ν (1 - ν)$ , this is $∣ g ∣^{2} = 1 - 2 ν (1 - ν) (1 - cos ξ h)$ . For small $ξ h$ , $1 - cos ξ h \approx \frac{1}{2} (ξ h)^{2}$ , so $∣ g ∣^{2} \approx 1 - ν (1 - ν) (ξ h)^{2}$ and $∣ g ∣ \approx 1 - \frac{ν ( 1 - ν )}{2} (ξ h)^{2}$ . The amplitude deficit is order $(ξ h)^{2}$ — the spectral signature of the $u_{xx}$ diffusion term, with strength matching $\frac{ah}{2} (1 - ν)$ . Rubric: full credit for the symbol, the $∣ g ∣^{2}$ identity, and the second-order amplitude decay.

Exercise 4 (medium, symbolic).

The Lax-Wendroff amplification factor is $g (ξ) = 1 - i ν sin ξ h - ν^{2} (1 - cos ξ h)$ . Show that for small $ξ h$ its modulus deviates from $1$ only at fourth order in $ξ h$ (no diffusion to leading order), while its phase carries a third-order error (dispersion). Contrast with upwind's second-order amplitude deficit.

Hint

From Exercise 7 of 43.11.03, $∣ g ∣^{2} = 1 - ν^{2} (1 - ν^{2}) (1 - cos ξ h)^{2}$ ; expand $(1 - cos ξ h)^{2} \approx \frac{1}{4} (ξ h)^{4}$ . For the phase, $ar g g \approx - ν ξ h + (cubic)$ .

Answer

Using $∣ g ∣^{2} = 1 - ν^{2} (1 - ν^{2}) (1 - cos ξ h)^{2}$ and $1 - cos ξ h \approx \frac{1}{2} (ξ h)^{2}$ , one gets $(1 - cos ξ h)^{2} \approx \frac{1}{4} (ξ h)^{4}$ , so $∣ g ∣^{2} \approx 1 - \frac{ν ^{2} ( 1 - ν ^{2} )}{4} (ξ h)^{4}$ : the amplitude deficit is order $(ξ h)^{4}$ , two orders weaker than upwind's $(ξ h)^{2}$ . So Lax-Wendroff barely diffuses. The exact mode should advance with phase $- a ξ k = - ν ξ h$ ; expanding $ar g g = arctan (\frac{- ν s i n ξ h}{1 - ν ^{2} ( 1 - c o s ξ h )}) = - ν ξ h + \frac{ν ( 1 - ν ^{2} )}{6} (ξ h)^{3} + \dots$ , the phase error is order $(ξ h)^{3}$ , the dispersive $u_{xxx}$ signature with coefficient matching $- \frac{a h ^{2}}{6} (1 - ν^{2})$ . Short waves lag (or lead) the true speed, making ripples. Rubric: full credit for the $(ξ h)^{4}$ amplitude order, the $(ξ h)^{3}$ phase error, and the diffusion-vs-dispersion contrast.

Exercise 5 (medium, symbolic).

Show that the Lax-Friedrichs scheme can be rewritten as the unstable centred scheme plus an explicit artificial-diffusion term, $U_{j}^{n + 1} = U_{j}^{n} - \frac{ν}{2} δ_{0} U_{j}^{n} + \frac{1}{2} δ^{2} U_{j}^{n}$ , and identify the modified-equation diffusion coefficient as $\frac{h ^{2}}{2 k} (1 - ν^{2})$ .

Hint

Write $\frac{1}{2} (U_{j - 1} + U_{j + 1}) = U_{j} + \frac{1}{2} δ^{2} U_{j}$ with $δ^{2} U_{j} = U_{j - 1} - 2 U_{j} + U_{j + 1}$ . The $\frac{1}{2} δ^{2}$ is a discrete second derivative times $\frac{h ^{2}}{2}$ .

Answer

Since $\frac{1}{2} (U_{j - 1} + U_{j + 1}) = U_{j} + \frac{1}{2} (U_{j - 1} - 2 U_{j} + U_{j + 1}) = U_{j} + \frac{1}{2} δ^{2} U_{j}$ , the Lax-Friedrichs update is $U_{j}^{n + 1} = U_{j}^{n} - \frac{ν}{2} δ_{0} U_{j}^{n} + \frac{1}{2} δ^{2} U_{j}^{n}$ , i.e. forward-time centred-space plus $\frac{1}{2} δ^{2}$ . Now $\frac{1}{2} δ^{2} U_{j} \approx \frac{h ^{2}}{2} u_{xx}$ , so the added term is $\frac{h ^{2}}{2 k} u_{xx}$ when divided by $k$ to match $u_{t}$ . Carrying the modified-equation reduction (the centred part contributes $- \frac{a ^{2} k}{2} u_{xx}$ via $u_{tt} = a^{2} u_{xx}$ ), the net diffusion coefficient is $\frac{h ^{2}}{2 k} - \frac{a ^{2} k}{2} = \frac{h ^{2}}{2 k} (1 - \frac{a ^{2} k ^{2}}{h ^{2}}) = \frac{h ^{2}}{2 k} (1 - ν^{2}) \geq 0$ for $∣ ν ∣ \leq 1$ . This explicit artificial viscosity is exactly what stabilises the otherwise-unstable centred scheme; it is also stronger than upwind's, so Lax-Friedrichs smears more. Rubric: full credit for the rewrite, the $\frac{1}{2} δ^{2}$ identification, and the $\frac{h ^{2}}{2 k} (1 - ν^{2})$ coefficient.

Exercise 7 (hard, symbolic).

Derive the Lax-Wendroff scheme from the Taylor/Cauchy-Kowalevski device: expand $u (x, t + k) = u + k u_{t} + \frac{k ^{2}}{2} u_{tt} + O (k^{3})$ , replace $u_{t} = - a u_{x}$ and $u_{tt} = a^{2} u_{xx}$ , then discretise $u_{x}$ by the centred difference and $u_{xx}$ by the second difference. Show the result is exactly the stated Lax-Wendroff stencil.

Hint

After substitution $u (x, t + k) \approx u - ak u_{x} + \frac{a ^{2} k ^{2}}{2} u_{xx}$ . Use $u_{x} \approx \frac{1}{2 h} δ_{0} U$ and $u_{xx} \approx \frac{1}{h ^{2}} δ^{2} U$ , and $ν = ak / h$ .

Answer

Truncating the time Taylor series at second order and using the equation's consequences, $u (x_{j}, t_{n + 1}) \approx u_{j}^{n} - ak (u_{x})_{j}^{n} + \frac{a ^{2} k ^{2}}{2} (u_{xx})_{j}^{n}$ . Discretise the space derivatives by their centred stencils: $(u_{x})_{j} \approx \frac{1}{2 h} (U_{j + 1} - U_{j - 1}) = \frac{1}{2 h} δ_{0} U_{j}$ and $(u_{xx})_{j} \approx \frac{1}{h ^{2}} (U_{j - 1} - 2 U_{j} + U_{j + 1}) = \frac{1}{h ^{2}} δ^{2} U_{j}$ . Then $$ U_j^{n+1} = U_j^n - \frac{ak}{2h}\delta_0 U_j^n + \frac{a^2k^2}{2h^2}\delta^2 U_j^n = U_j^n - \frac{\nu}{2}\delta_0 U_j^n + \frac{\nu^2}{2}\delta^2 U_j^n, $$ which is $U_{j}^{n + 1} = U_{j}^{n} - \frac{ν}{2} (U_{j + 1}^{n} - U_{j - 1}^{n}) + \frac{ν ^{2}}{2} (U_{j - 1}^{n} - 2 U_{j}^{n} + U_{j + 1}^{n})$ , the stated scheme. The $\frac{ν ^{2}}{2} δ^{2}$ correction is not artificial viscosity bolted on but the discretised $\frac{a ^{2} k ^{2}}{2} u_{xx}$ from the time expansion — which is why it cancels the leading $u_{xx}$ in the modified equation and leaves second-order accuracy with only a dispersive remainder. Rubric: full credit for the time expansion with the derivative substitutions, the centred discretisations, and recovering the exact stencil with the $\frac{ν ^{2}}{2} δ^{2}$ term identified as the time-expansion's $u_{xx}$ .

Exercise 8 (hard, short-answer).

State Godunov's order-barrier theorem for linear schemes and explain, using the modified-equation picture, why it forbids a fixed linear scheme that is both second-order and monotone (oscillation-free). Name the resolution.

Hint

A monotone linear scheme has nonnegative coefficients (a weighted average). Connect "second-order" to the parity of the leading error term and "monotone" to positive numerical diffusion.

Answer

Godunov's theorem: a linear, constant-coefficient, monotonicity-preserving scheme for $u_{t} + a u_{x} = 0$ is at most first-order accurate. Equivalently, the only linear schemes that never create new extrema (no overshoot, no spurious oscillation) are first-order. The modified-equation reading: a monotone linear scheme is a convex combination of neighbour values, which forces a nonnegative numerical-diffusion coefficient (a genuine $u_{xx}$ smoothing) — and that even-derivative leading term is precisely what makes the scheme first-order. To reach second order one must annihilate the $u_{xx}$ term, after which the leading error is the odd, dispersive $u_{xxx}$ term; dispersion produces oscillations, so the second-order linear scheme cannot be monotone. The two demands are incompatible at fixed linear order: positive diffusion (monotone) versus no diffusion (second-order). The resolution is to abandon linearity: nonlinear high-resolution schemes (TVD methods with flux/slope limiters) switch behaviour by the local solution, using a second-order stencil in smooth regions and adding diffusion only near extrema, escaping the barrier — the subject of the finite-volume theory and the entropy-solution context of 02.18.06. Rubric: full credit for the correct statement of the barrier (linear monotone $\Rightarrow$ first-order), the diffusion-parity argument linking monotone to positive $u_{xx}$ and second-order to dispersive $u_{xxx}$ , and naming nonlinear high-resolution/TVD schemes as the resolution.

Advanced results Master

Theorem 1 (the three amplification factors and their stability thresholds). For $u_{t} + a u_{x} = 0$ on the whole line with $ν = ak / h$ , the von Neumann symbols of 43.11.03 are: upwind ( $a > 0$ ) $g = (1 - ν) + ν e^{- i ξ h}$ with $∣ g ∣^{2} = 1 - 2 ν (1 - ν) (1 - cos ξ h)$ ; Lax-Friedrichs $g = cos ξ h - i ν sin ξ h$ with $∣ g ∣^{2} = 1 - (1 - ν^{2}) sin^{2} ξ h$ ; Lax-Wendroff $g = 1 - i ν sin ξ h - ν^{2} (1 - cos ξ h)$ with $∣ g ∣^{2} = 1 - ν^{2} (1 - ν^{2}) (1 - cos ξ h)^{2}$ . Each satisfies $∣ g ∣ \leq 1$ for all $ξ$ exactly when $∣ ν ∣ \leq 1$ , the CFL number; the centred-only scheme has $∣ g ∣^{2} = 1 + ν^{2} sin^{2} ξ h > 1$ and is unconditionally unstable ^{[LeVeque, R. J. — Finite Difference Methods for Ordinary and Partial Differential Equations: Steady-State and Time-Dependent Problems]}.

Theorem 2 (modified equations and the parity classification of error). Upwind is consistent of order one with modified equation $u_{t} + a u_{x} = \frac{ah}{2} (1 - ν) u_{xx} + O (h^{2})$ , an even-derivative diffusion term, nonnegative for $0 \leq ν \leq 1$ . Lax-Friedrichs is order one with diffusion coefficient $\frac{h ^{2}}{2 k} (1 - ν^{2})$ , exceeding upwind's. Lax-Wendroff is order two with modified equation $u_{t} + a u_{x} = - \frac{a h ^{2}}{6} (1 - ν^{2}) u_{xxx} + O (h^{3})$ , an odd-derivative dispersion term. In every case the leading error vanishes at $ν = 1$ , where each scheme reduces to exact one-cell transport. The diffusion coefficient governs the decay rate of $∣ g (ξ) ∣$ below $1$ , and the dispersion coefficient governs the deviation of the discrete phase speed $- ar g g (ξ) / (ξ k)$ from $a$ ^{[Strikwerda, J. C. — Finite Difference Schemes and Partial Differential Equations (2nd ed.)]}.

Theorem 3 (Godunov's order barrier). A linear, constant-coefficient, monotonicity-preserving scheme $U_{j}^{n + 1} = \sum_{ℓ} c_{ℓ} U_{j + ℓ}^{n}$ for the advection equation — monotone in the sense that $c_{ℓ} \geq 0$ for all $ℓ$ , equivalently the scheme is monotonicity-preserving (it maps monotone data to monotone data and creates no new local extrema) — is at most first-order accurate. Consequently no fixed linear scheme is simultaneously second-order and oscillation-free: forcing second order removes the diffusive $u_{xx}$ term and exposes the dispersive $u_{xxx}$ term, which generates over- and undershoots at discontinuities. The obstruction is removed only by nonlinear high-resolution schemes whose coefficients depend on the solution ^{[LeVeque, R. J. — Finite Volume Methods for Hyperbolic Problems]}.

Theorem 4 (the artificial-viscosity reading and the modified-equation method). Every stable scheme for $u_{t} + a u_{x} = 0$ may be read as a discretisation of an advection-diffusion-dispersion equation $u_{t} + a u_{x} = β h u_{xx} + γ h^{2} u_{xxx} + \dots$ whose coefficients are the truncation terms; stability requires the leading even coefficient $β \geq 0$ (positive numerical viscosity), instability is signalled by $β < 0$ (anti-diffusion), and the order of the scheme is the smallest $m \geq 1$ with a surviving $\partial_{x}^{m + 1} u$ term. This equivalent-differential-equation or modified-equation method (Warming-Hyett) reproduces the von Neumann stability threshold $∣ ν ∣ \leq 1$ from the sign of the diffusion coefficient and predicts the qualitative error (smear if the leading surviving term is even, wiggle if odd) without solving the scheme ^{[LeVeque, R. J. — Finite Volume Methods for Hyperbolic Problems]}.

Synthesis. The foundational reason the advection schemes split cleanly into smearers and wigglers is a single structural fact about one Taylor expansion: the parity of the leading surviving derivative in the modified equation is locked to the scheme's accuracy order, even orders producing the dissipative $u_{xx}$ and odd orders the dispersive $u_{xxx}$ , so a first-order scheme must diffuse and a second-order scheme must disperse. This is exactly the amplitude-versus-phase decomposition of the von Neumann symbol of 43.11.03 — the modulus $∣ g (ξ) ∣$ is the diffusive content and the phase $ar g g (ξ)$ the dispersive content of the same expansion — and the modified equation is dual to the amplification factor, one differential and one algebraic encoding of consistency. The central insight is that monotonicity and accuracy pull in opposite directions through the diffusion coefficient: a monotone linear scheme needs a positive $u_{xx}$ term, which caps it at first order, while removing that term to gain second order unleashes the dispersive $u_{xxx}$ wiggles — putting these together is Godunov's barrier, and its only escape is to make the scheme nonlinear. The bridge to the wider theory is that this concrete diffusion-dispersion calculus is the linear, smooth-solution shadow of the nonlinear conservation-law theory of 02.18.06, where the same numerical viscosity that smears a linear front is what selects the physically correct entropy solution at a shock, and where consistency-plus-stability becomes the Lax-Richtmyer convergence theorem of 43.11.05 whose hypotheses these schemes verify mode by mode.

Full proof set Master

Proposition 1 (upwind is first-order with diffusive modified equation). For $a > 0$ and smooth $u$ , the upwind scheme inserting the exact solution of $u_{t} + a u_{x} = 0$ has local truncation error $τ = - \frac{ah}{2} (1 - ν) u_{xx} + O (h^{2})$ , so the scheme is consistent of order one and its modified equation is $u_{t} + a u_{x} = \frac{ah}{2} (1 - ν) u_{xx} + O (h^{2})$ with nonnegative coefficient for $0 \leq ν \leq 1$ .

Proof. The local truncation error is the residual of the exact solution in the scheme, divided by $k$ : $$ \tau = \frac{u(x_j,t_{n+1}) - u(x_j,t_n)}{k} + a,\frac{u(x_j,t_n) - u(x_{j-1},t_n)}{h}. $$ Taylor-expand at $(x_{j}, t_{n})$ . The forward time difference is $u_{t} + \frac{k}{2} u_{tt} + O (k^{2})$ and the backward space difference is $u_{x} - \frac{h}{2} u_{xx} + O (h^{2})$ , so $$ \tau = (u_t + au_x) + \tfrac{k}{2}u_{tt} - \tfrac{ah}{2}u_{xx} + O(k^2 + h^2). $$ The advection bracket vanishes. Differentiating the equation, $u_{tt} = a^{2} u_{xx}$ , and $k = ν h / a$ gives $\frac{k}{2} u_{tt} = \frac{ν h}{2 a} \cdot a^{2} u_{xx} = \frac{a ν h}{2} u_{xx}$ . Hence $$ \tau = \frac{a\nu h}{2}u_{xx} - \frac{ah}{2}u_{xx} + O(h^2) = -\frac{ah}{2}(1-\nu)u_{xx} + O(h^2). $$ The leading term is $O (h)$ , so the scheme is first-order. Since the scheme equates the discrete advance to the upwind advection difference, the exact solution satisfies $u_{t} + a u_{x} = - τ \cdot (leading) = \frac{ah}{2} (1 - ν) u_{xx} + O (h^{2})$ , a diffusion equation; its coefficient $\frac{ah}{2} (1 - ν) \geq 0$ exactly when $ν \leq 1$ (with $a, h > 0$ ). $□$

Proposition 2 (Lax-Wendroff is second-order with dispersive modified equation). For smooth $u$ , the Lax-Wendroff scheme has local truncation error $τ = \frac{a h ^{2}}{6} (1 - ν^{2}) u_{xxx} + O (h^{3})$ , so it is consistent of order two and its modified equation is $u_{t} + a u_{x} = - \frac{a h ^{2}}{6} (1 - ν^{2}) u_{xxx} + O (h^{3})$ , with no $u_{xx}$ term.

Proof. Expand the exact time advance to third order, using $u_{t} = - a u_{x}$ , $u_{tt} = a^{2} u_{xx}$ , $u_{ttt} = - a^{3} u_{xxx}$ : $$ u(x_j,t_{n+1}) = u + ku_t + \tfrac{k^2}{2}u_{tt} + \tfrac{k^3}{6}u_{ttt} + O(k^4) = u - aku_x + \tfrac{a^2k^2}{2}u_{xx} - \tfrac{a^3k^3}{6}u_{xxx} + O(k^4). $$ The scheme's right-hand side applied to the exact solution is $u - \frac{ν}{2} δ_{0} u + \frac{ν ^{2}}{2} δ^{2} u$ . The centred first difference expands as $\frac{1}{2 h} δ_{0} u = u_{x} + \frac{h ^{2}}{6} u_{xxx} + O (h^{4})$ , so $- \frac{ν}{2} δ_{0} u = - ν h (u_{x} + \frac{h ^{2}}{6} u_{xxx}) + O (h^{5}) = - ak u_{x} - \frac{ak h ^{2}}{6} u_{xxx} + O (\dots)$ , using $ν h = ak$ . The second difference expands as $\frac{1}{h ^{2}} δ^{2} u = u_{xx} + \frac{h ^{2}}{12} u_{xxxx} + O (h^{4})$ , so $\frac{ν ^{2}}{2} δ^{2} u = \frac{ν ^{2} h ^{2}}{2} u_{xx} + O (h^{4}) = \frac{a ^{2} k ^{2}}{2} u_{xx} + O (h^{4})$ , using $ν^{2} h^{2} = a^{2} k^{2}$ . Subtracting the scheme's advance from the exact advance, the $u$ , $u_{x}$ , and $u_{xx}$ terms cancel identically (this triple cancellation is the design of the scheme), leaving $$ k\tau = -\tfrac{a^3k^3}{6}u_{xxx} + \tfrac{akh^2}{6}u_{xxx} + O(h^4) = \tfrac{akh^2}{6}\big(1 - \tfrac{a^2k^2}{h^2}\big)u_{xxx} + O(h^4) = \tfrac{akh^2}{6}(1-\nu^2)u_{xxx} + O(h^4). $$ Dividing by $k$ and using $ak = ν h$ gives $τ = \frac{a h ^{2}}{6} (1 - ν^{2}) u_{xxx} + O (h^{3})$ , second order, and the modified equation $u_{t} + a u_{x} = - τ \cdot (leading) = - \frac{a h ^{2}}{6} (1 - ν^{2}) u_{xxx} + O (h^{3})$ , purely dispersive. $□$

Proposition 3 (Lax-Friedrichs as forward-time centred-space plus artificial viscosity). The Lax-Friedrichs scheme equals the forward-time centred-space scheme plus the term $\frac{1}{2} δ^{2} U_{j}^{n}$ , and its modified-equation diffusion coefficient is $\frac{h ^{2}}{2 k} (1 - ν^{2}) \geq 0$ for $∣ ν ∣ \leq 1$ .

Proof. From $\frac{1}{2} (U_{j - 1} + U_{j + 1}) = U_{j} + \frac{1}{2} δ^{2} U_{j}$ the update is $U_{j}^{n + 1} = U_{j}^{n} + \frac{1}{2} δ^{2} U_{j}^{n} - \frac{ν}{2} δ_{0} U_{j}^{n}$ , the centred scheme plus $\frac{1}{2} δ^{2}$ . For the modified equation, expand: the forward-time part gives $u_{t} + \frac{k}{2} u_{tt}$ , the centred-space part gives $a u_{x}$ (its $u_{xxx}$ error is third order), and the added $\frac{1}{k} \cdot \frac{1}{2} δ^{2} u = \frac{h ^{2}}{2 k} u_{xx} + O (h^{4} / k)$ contributes a diffusion. Collecting the $u_{xx}$ terms with $u_{tt} = a^{2} u_{xx}$ : $\frac{k}{2} a^{2} u_{xx}$ from the time error subtracts (it appears on the residual side as $+ \frac{a ^{2} k}{2} u_{xx}$ pulled to the equation side with the opposite sign), and the artificial term adds $\frac{h ^{2}}{2 k} u_{xx}$ , giving net coefficient $\frac{h ^{2}}{2 k} - \frac{a ^{2} k}{2} = \frac{h ^{2}}{2 k} (1 - \frac{a ^{2} k ^{2}}{h ^{2}}) = \frac{h ^{2}}{2 k} (1 - ν^{2})$ . This is nonnegative for $∣ ν ∣ \leq 1$ , and exceeds the upwind coefficient $\frac{ah}{2} (1 - ν) = \frac{h ^{2}}{2 k} ν (1 - ν)$ by the factor $(1 + ν) / ν \geq 1$ , so Lax-Friedrichs is the more diffusive scheme. $□$

Proposition 4 (Godunov's order barrier for linear schemes). A constant-coefficient linear scheme $U_{j}^{n + 1} = \sum_{ℓ} c_{ℓ} U_{j + ℓ}^{n}$ for $u_{t} + a u_{x} = 0$ that is monotonicity-preserving (maps every monotone grid function to a monotone grid function) has all $c_{ℓ} \geq 0$ , and any such scheme is at most first-order accurate.

Proof. Monotonicity-preservation forces $c_{ℓ} \geq 0$ : if some $c_{ℓ_{0}} < 0$ , apply the scheme to the monotone Heaviside data $U_{j}^{0} = 0$ for $j < 0$ and $U_{j}^{0} = 1$ for $j \geq 0$ ; the first difference of the output at the index reached through $c_{ℓ_{0}}$ is $\sum_{ℓ} c_{ℓ} (U_{j + ℓ + 1}^{0} - U_{j + ℓ}^{0}) = c_{- j}$ at the single jump, so a negative coefficient produces a negative first difference somewhere, breaking monotonicity. Hence all $c_{ℓ} \geq 0$ . Consistency to first order requires $\sum_{ℓ} c_{ℓ} = 1$ and $\sum_{ℓ} ℓ c_{ℓ} = - ν$ (matching $u$ and the transported $u_{x}$ ). Consider the modified-equation diffusion coefficient, proportional to the second moment minus the square of the first: the coefficient of $u_{xx}$ is $\frac{h ^{2}}{2 k} (\sum_{ℓ} ℓ^{2} c_{ℓ} - (\sum_{ℓ} ℓ c_{ℓ})^{2}) = \frac{h ^{2}}{2 k} (\sum_{ℓ} ℓ^{2} c_{ℓ} - ν^{2})$ . With $c_{ℓ} \geq 0$ summing to $1$ this is a variance of the integer displacements under the probability weights $c_{ℓ}$ , which is zero only if all weight sits on a single $ℓ$ ; that single-point case is exact transport, possible only when $ν$ is an integer. For non-integer $ν$ the variance is strictly positive, so the $u_{xx}$ coefficient is strictly positive: the scheme carries genuine numerical diffusion and its leading error is the even $O (h)$ term, first order. To be second-order the $u_{xx}$ coefficient must vanish, forcing zero variance, hence a single nonzero $c_{ℓ}$ and integer $ν$ — not a scheme valid for general $ν$ . Therefore no monotone linear scheme valid for non-integer $ν$ exceeds first order. $□$

Connections Master

The von Neumann stability analysis of 43.11.03 supplies the amplification factors this unit reinterprets: the upwind, Lax-Friedrichs, and Lax-Wendroff symbols $g (ξ)$ computed there as moduli for the CFL threshold $∣ ν ∣ \leq 1$ are read here through their modulus (diffusion) and phase (dispersion), so the same one-line Fourier substitution that decides stability also diagnoses error character. The centred-scheme instability proved there is the witness, reused here, that the CFL condition is necessary but not sufficient, and that a missing diffusion term ( $∣ g ∣ > 1$ , anti-diffusion) is the differential signature of blow-up.
The method-of-lines and consistency-plus-stability framework of 43.11.02 is the analysis template specialised here from the parabolic heat equation to the hyperbolic advection equation: the local-truncation-error Taylor expansion, the order definition, and the principle that consistency order plus stability yields convergence order all transfer directly, with the crucial difference that the hyperbolic modified equation carries a transport leading term and either diffusion or dispersion, where the parabolic one carried diffusion intrinsically.
The continuous wave and transport theory of 02.13.04 is the exact problem these schemes approximate: the characteristics $x - a t = const$ along which $u_{0}$ is carried rigidly are what the upwind stencil tries to follow by differencing in the upwind direction, and the analytic domain of dependence — the single characteristic foot — is what the CFL condition forces the numerical stencil to contain. Numerical diffusion and dispersion are precisely the ways a finite stencil fails to reproduce that rigid characteristic transport.
The scalar conservation laws and entropy solutions of 02.18.06 are the nonlinear context these linear schemes prefigure: numerical viscosity, harmless smearing in the linear smooth case, becomes the mechanism that selects the physically admissible entropy solution at a shock, and the monotonicity that Godunov's barrier shows incompatible with linear second-order accuracy is exactly the property needed to avoid spurious oscillations at discontinuities — motivating the nonlinear high-resolution (TVD/flux-limiter) schemes that the finite-volume theory builds on this foundation.
The Lax-Richtmyer equivalence theorem 43.11.05 is the capstone these schemes feed: each is a one-step operator $C (k)$ whose consistency (computed here as the modified equation's leading order) and stability (the von Neumann bound $∣ ν ∣ \leq 1$ of 43.11.03) combine, by that theorem, into convergence; the modified-equation method is the differential form of the consistency half of the same consistency-plus-stability-equals-convergence synthesis.

Historical & philosophical context Master

The linear advection equation became the proving ground for hyperbolic finite differences because it isolates pure transport without the complications of nonlinearity or systems. The first-order one-sided upwind idea — differencing into the direction information comes from — and the necessity of respecting the domain of dependence trace to the 1928 paper of Richard Courant, Kurt Friedrichs, and Hans Lewy ^{[Courant, Friedrichs & Lewy 1928]}, whose condition on difference equations of mathematical physics is the CFL bound the schemes here must satisfy. The averaging device that stabilises the centred scheme is due to Peter Lax in his 1954 study of weak solutions and difference schemes for hyperbolic conservation laws (Communications on Pure and Applied Mathematics 7, 159–193) ^{[Lax 1954]}, and is now named the Lax-Friedrichs scheme.

The second-order one-step scheme combining a centred difference with a curvature correction was introduced by Peter Lax and Burton Wendroff in 1960 in Systems of conservation laws (Communications on Pure and Applied Mathematics 13, 217–237) ^{[Lax & Wendroff 1960]}, using the device of converting time derivatives into space derivatives via the equation — the Cauchy-Kowalevski substitution. The systematic reading of the leading truncation term as an equivalent differential equation whose even-order part is dissipative and odd-order part dispersive was developed by R. F. Warming and B. J. Hyett in their 1974 modified-equation analysis (Journal of Computational Physics 14, 159–179) ^{[Warming & Hyett 1974]}. The order barrier — that a linear monotonicity-preserving scheme cannot exceed first order — was established by Sergei Godunov in 1959 (Matematicheskii Sbornik 47, 271–306) ^{[Godunov 1959]}, the result that drove the field toward the nonlinear high-resolution schemes consolidated in the monograph treatments of Randall LeVeque ^{[LeVeque, R. J. — Finite Volume Methods for Hyperbolic Problems]}.

Bibliography Master

@book{leveque2007fdmhyperbolic,
  author    = {LeVeque, Randall J.},
  title     = {Finite Difference Methods for Ordinary and Partial Differential Equations: Steady-State and Time-Dependent Problems},
  publisher = {Society for Industrial and Applied Mathematics (SIAM)},
  year      = {2007}
}

@book{leveque2002finitevolume,
  author    = {LeVeque, Randall J.},
  title     = {Finite Volume Methods for Hyperbolic Problems},
  series    = {Cambridge Texts in Applied Mathematics},
  publisher = {Cambridge University Press},
  year      = {2002}
}

@article{lax1954weak,
  author  = {Lax, Peter D.},
  title   = {Weak solutions of nonlinear hyperbolic equations and their numerical computation},
  journal = {Communications on Pure and Applied Mathematics},
  volume  = {7},
  number  = {1},
  year    = {1954},
  pages   = {159--193}
}

@article{laxwendroff1960,
  author  = {Lax, Peter D. and Wendroff, Burton},
  title   = {Systems of conservation laws},
  journal = {Communications on Pure and Applied Mathematics},
  volume  = {13},
  number  = {2},
  year    = {1960},
  pages   = {217--237}
}

@article{warminghyett1974,
  author  = {Warming, R. F. and Hyett, B. J.},
  title   = {The modified equation approach to the stability and accuracy analysis of finite-difference methods},
  journal = {Journal of Computational Physics},
  volume  = {14},
  number  = {2},
  year    = {1974},
  pages   = {159--179}
}

@article{godunov1959,
  author  = {Godunov, Sergei K.},
  title   = {A difference method for numerical calculation of discontinuous solutions of the equations of hydrodynamics},
  journal = {Matematicheskii Sbornik},
  volume  = {47(89)},
  number  = {3},
  year    = {1959},
  pages   = {271--306}
}

@article{courantfriedrichslewy1928hyperbolic,
  author  = {Courant, Richard and Friedrichs, Kurt and Lewy, Hans},
  title   = {{\"U}ber die partiellen Differenzengleichungen der mathematischen Physik},
  journal = {Mathematische Annalen},
  volume  = {100},
  number  = {1},
  year    = {1928},
  pages   = {32--74}
}

@book{strikwerda2004,
  author    = {Strikwerda, John C.},
  title     = {Finite Difference Schemes and Partial Differential Equations},
  edition   = {2},
  publisher = {Society for Industrial and Applied Mathematics (SIAM)},
  year      = {2004}
}

Prerequisites

43.11.03
43.11.02
02.13.04
02.18.06

Tier anchors

beginner: LeVeque 2007 *Finite Difference Methods for Ordinary and Partial Differential Equations* (SIAM) §10.1-10.4 (the advection equation $u_t+au_x=0$, the upwind scheme as following the characteristic, the Lax-Friedrichs and Lax-Wendroff schemes, and the smearing-vs-wiggles contrast of low- and high-order schemes); Strang 2007 *Computational Science and Engineering* (Wellesley-Cambridge) §6.5 (upwind differencing, the Courant number, and numerical viscosity pictured on a moving pulse)
intermediate: LeVeque 2007 *Finite Difference Methods for Ordinary and Partial Differential Equations* (SIAM) §10.1-10.10 (the advection schemes, the modified equation revealing the $\tfrac{ah}{2}(1-\nu)u_{xx}$ diffusion of upwind and the $-\tfrac{ah^2}{6}(1-\nu^2)u_{xxx}$ dispersion of Lax-Wendroff, the Courant number $\nu=ak/h$, and the link to von Neumann stability); Strikwerda 2004 *Finite Difference Schemes and Partial Differential Equations* 2e (SIAM) §1.3-1.4, §3.1-3.4 (one-sided vs centred advection schemes, the Lax-Wendroff construction, and the dissipation/dispersion reading of the amplification factor)
master: LeVeque 2002 *Finite Volume Methods for Hyperbolic Problems* (Cambridge) Ch. 8-12, §8.6 (the modified-equation analysis, numerical diffusion and dispersion, Godunov's order-barrier theorem, and monotone vs. high-resolution schemes for scalar conservation laws); Richtmyer-Morton 1967 *Difference Methods for Initial-Value Problems* 2e (Interscience) Ch. 5, 12-13 (the Lax-Wendroff scheme, dissipation and dispersion of difference schemes, and the heat-equation analogy of the modified equation); Hirsch 2007 *Numerical Computation of Internal and External Flows* 2e (Butterworth-Heinemann) Ch. 8-10 (the modified-equation/equivalent-differential-equation method, numerical dissipation and dispersion error, and monotonicity for convection schemes)

References

LeVeque, R. J. — Finite Difference Methods for Ordinary and Partial Differential Equations: Steady-State and Time-Dependent Problems · SIAM 2007. Chapter 10 treats the linear advection equation $u_t+au_x=0$ as the model hyperbolic problem. §10.1-10.4 derive the schemes: the first-order one-sided UPWIND scheme $U_j^{n+1}=U_j^n-\nu(U_j^n-U_{j-1}^n)$ for $a>0$ (and the mirror image for $a<0$), the LAX-FRIEDRICHS scheme $U_j^{n+1}=\tfrac12(U_{j-1}^n+U_{j+1}^n)-\tfrac\nu2(U_{j+1}^n-U_{j-1}^n)$, and the second-order LAX-WENDROFF scheme $U_j^{n+1}=U_j^n-\tfrac\nu2(U_{j+1}^n-U_{j-1}^n)+\tfrac{\nu^2}2(U_{j-1}^n-2U_j^n+U_{j+1}^n)$, with $\nu=ak/h$ the Courant number. §10.5-10.6 give the von Neumann amplification factors and the CFL stability bound $|\nu|\le1$. §10.7-10.8 develop the MODIFIED-EQUATION (equivalent-PDE) analysis: substituting Taylor expansions into the scheme shows upwind solves $u_t+au_x=\tfrac{ah}2(1-\nu)u_{xx}+\cdots$ (an even-order, parabolic, DISSIPATIVE term that smears discontinuities and damps amplitudes), while Lax-Wendroff solves $u_t+au_x=-\tfrac{ah^2}6(1-\nu^2)u_{xxx}+\cdots$ (an odd-order, DISPERSIVE term that makes wave packets travel at the wrong speed and produces trailing oscillations). §10.10 states Godunov's theorem that no linear monotone scheme exceeds first-order accuracy, motivating the nonlinear high-resolution schemes of the companion finite-volume text.
Strikwerda, J. C. — Finite Difference Schemes and Partial Differential Equations (2nd ed.) · SIAM 2004. §1.3-1.4 introduce one-sided and centred difference schemes for $u_t+au_x=0$, the instability of the forward-time centred-space scheme, and the CFL condition. Ch. 3 builds the higher-order schemes: §3.1 the Lax-Friedrichs scheme and its identification as forward-time centred-space plus the artificial-viscosity term $\tfrac{h^2}{2k}\delta^2$; §3.2-3.3 the Lax-Wendroff scheme derived by the Taylor/Cauchy-Kowalevski device $u_{tt}=a^2u_{xx}$ that converts the time derivatives in $u(x,t+k)=u+ku_t+\tfrac{k^2}2u_{tt}+\cdots$ into space derivatives, yielding the second-order one-step scheme; §3.4 the dissipation and dispersion of difference schemes read from the modulus and phase of the amplification factor $g(\xi)$, with the order of dissipation (the power of $\xi h$ at which $|g|$ first deviates from 1) controlling accuracy of amplitude and the phase error $\arg g(\xi)+a\xi k$ controlling the dispersion.
LeVeque, R. J. — Finite Volume Methods for Hyperbolic Problems · Cambridge University Press 2002. §8.6 and Ch. 8-12 develop the modified-equation analysis and the diffusion/dispersion dichotomy in depth: the leading truncation term of a scheme for $u_t+au_x=0$ is the right-hand side of an EQUIVALENT differential equation whose solution the scheme approximates to higher order than it approximates advection; an even-derivative leading term ($u_{xx}$) is diffusive (the amplitude of each Fourier mode decays — numerical viscosity/diffusion, characteristic of upwind and Lax-Friedrichs), and an odd-derivative term ($u_{xxx}$) is dispersive (each mode travels at a wavenumber-dependent speed with no amplitude loss — spurious oscillations/wiggles trailing or leading a discontinuity, characteristic of Lax-Wendroff). Ch. 12 states and discusses GODUNOV'S theorem: a linear, monotonicity-preserving scheme is at most first-order accurate, so no fixed linear scheme can be both oscillation-free and second-order; the resolution is nonlinear high-resolution (TVD/flux-limiter) schemes, reserved for the finite-volume treatment.

Estimated time

beginner: 20m
intermediate: 50m
master: 90m