Flow Lab

Syllabus / Module 10: Numerical Methods for PDEs

Lesson 10.3

Von Neumann Stability Analysis

Fourier modes on a grid, amplification factors, stability conditions, and the Lax equivalence theorem.

Written byClaude Sonnet

🌊
Why this matters for simulation: Von Neumann analysis was invented for fluid simulations at Los Alamos.

By the end of this lesson you can…

  • Feed one Fourier mode $u_j^n = G^n e^{ij\theta}$ through a linear scheme and read off its amplification factor $G(\theta)$.
  • Apply the condition $\lvert G\rvert \le 1$ for all $\theta \in [0, \pi]$ and find the unstable band when it fails.
  • Recover $r \le 1/2$ for FTCS diffusion; show centred advection has $\lvert G\rvert^2 = 1 + c^2\sin^2\theta$ and upwind is stable exactly for $0 \le c \le 1$.
  • Explain how Lax-Friedrichs repairs centred advection by adding diffusion.
  • Read $\lvert G\rvert$ as numerical diffusion and $\arg G$ as numerical dispersion, and predict how far a pulse is smeared.
  • State the Lax equivalence theorem (consistency plus stability gives convergence) and what it does not cover.
On this page
·
  1. One mode through a scheme
  2. Check it on the one you know: FTCS diffusion
  3. Advection and the CFL number
  4. Centred advection is unstable for every step
  5. Upwind: stable when information is not skipped
  6. Lax-Friedrichs: repairing centred advection
  7. What ∣G∣<1\lvert G\rvert \lt 1∣G∣<1 does to a wave: numerical diffusion
  8. The phase of GGG: numerical dispersion
  9. The Lax equivalence theorem
  10. The lab
  11. Computing it
  12. Concept checks
  13. Problems
  14. What comes next
  15. Key Takeaways

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 GG, 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.

▶ Video One Fourier mode pushed through a scheme, the amplification factor stepping around the complex plane, the unstable band of wavenumbers, and the three advection schemes comparedcaptions only
Transcript
  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. 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.
  8. 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.
  9. 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.
  10. 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.
  11. 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.
  12. 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.
  13. 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.
  14. 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 hh and a wave sampled on it, uj=eijkhu_j = e^{ijkh}, and write θ=kh\theta = kh, 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, ei(j+1)θ=eiθeijθe^{i(j+1)\theta} = e^{i\theta}e^{ij\theta}, so a weighted sum of shifted copies of eijθe^{ij\theta} is again a multiple of eijθe^{ij\theta}. Every wave is an eigenvector of the scheme, as eλte^{\lambda t} was for linear ODEs and este^{st} for the Laplace transform (6.1 The Laplace Transform). The multiplier is what we want. Write

ujn=Gneijθ,u_j^n = G^n e^{ij\theta},

substitute into the scheme, and divide by the common factor GneijθG^n e^{ij\theta}: an equation for the complex number G(θ)G(\theta) remains. Its modulus ∣G∣\lvert G\rvert is the growth per step and its phase arg⁡G\arg G 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 θ\theta matters. The values θ\theta and θ+2π\theta + 2\pi give identical samples, and −θ-\theta is the complex conjugate, so for real data

0≤θ≤π.0 \le \theta \le \pi.

At θ=0\theta = 0 the wave is constant; at θ=π\theta = \pi it is (−1)j(-1)^j, 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:

  ∣G(θ)∣≤1for every θ∈[0,π]  \boxed{\;\lvert G(\theta)\rvert \le 1 \quad\text{for every } \theta \in [0, \pi]\;}

This is the von Neumann stability condition. Where it fails, the set of θ\theta with ∣G∣>1\lvert G\rvert \gt 1 is the unstable band, and the instability is that band growing like ∣G∣n\lvert G\rvert^n out of rounding error.

Check it on the one you know: FTCS diffusion

For FTCS, ujn+1=ujn+r(uj+1n−2ujn+uj−1n)u_j^{n+1} = u_j^n + r(u_{j+1}^n - 2u_j^n + u_{j-1}^n) with r=αΔt/h2r = \alpha\Delta t/h^2, substitute ujn=Gneijθu_j^n = G^n e^{ij\theta}:

G=1+r(eiθ−2+e−iθ)=1−2r(1−cos⁡θ)=1−4rsin⁡2θ2.G = 1 + r\left(e^{i\theta} - 2 + e^{-i\theta}\right) = 1 - 2r(1 - \cos\theta) = 1 - 4r\sin^2\frac{\theta}{2}.

This is real and ranges from 1−4r1 - 4r to 11, so G≥−1G \ge -1 needs r≤1/2r \le 1/2, the limit from before. It is the explicit-methods-for-the-heat-equation formula 1−4rsin⁡2(kπh/2)1 - 4r\sin^2(k\pi h/2) with θ=kπh\theta = k\pi h, reached with no matrix, boundary or eigenvalue. The unstable band appears directly: for r>1/2r \gt 1/2 it is θ>2arcsin⁡(1/2r)\theta \gt 2\arcsin(1/\sqrt{2r}). For r=0.6r = 0.6 that starts at θ=2.3005\theta = 2.3005: only waves shorter than 2π/2.3005=2.732\pi/2.3005 = 2.73 cells.

Advection and the CFL number

For diffusion everything decays; advection, ut+aux=0u_t + a u_x = 0, only moves things: the exact solution translates the profile at speed aa. With grid spacing hh and step Δt\Delta t define the CFL number (Courant, Friedrichs, Lewy)

c=a Δth,c = \frac{a\,\Delta t}{h},

the number of cells the true solution moves in one step. A wave eikxe^{ikx} moves to eik(x−aΔt)e^{ik(x - a\Delta t)}, and on the grid that multiplies each mode by

Gexact(θ)=e−ikaΔt=e−icθ,G_{\text{exact}}(\theta) = e^{-ik a\Delta t} = e^{-ic\theta},

modulus exactly 11 and phase −cθ-c\theta. This is the benchmark: a scheme must have ∣G∣≤1\lvert G\rvert \le 1 (stable), and for accuracy ∣G∣\lvert G\rvert near 11 and arg⁡G\arg G near −cθ-c\theta on the waves we care about.

Centred advection is unstable for every step

The obvious scheme copies diffusion: forward in time, centred in space,

ujn+1=ujn−c2(uj+1n−uj−1n).u_j^{n+1} = u_j^n - \frac{c}{2}\left(u_{j+1}^n - u_{j-1}^n\right).

It is consistent and second order in space. Substituting a mode,

G=1−c2(eiθ−e−iθ)=1−icsin⁡θ,∣G∣2=1+c2sin⁡2θ.G = 1 - \frac{c}{2}\left(e^{i\theta} - e^{-i\theta}\right) = 1 - ic\sin\theta, \qquad \lvert G\rvert^2 = 1 + c^2\sin^2\theta.

That exceeds 11 for every θ\theta strictly between 00 and π\pi and every c≠0c \ne 0. No choice of cc makes it stable: smaller steps lower the growth per step but never remove it. Geometrically GG sits on the line Re G=1\mathrm{Re}\,G = 1, which touches the unit circle only at G=1G = 1.

The mechanism is in the method of lines. Centred differencing makes the semi-discrete eigenvalues purely imaginary, λ=−i(a/h)sin⁡θ\lambda = -i(a/h)\sin\theta: waves that oscillate and never decay. Forward Euler’s stability region (4.5 Stability Regions & Stiffness) is a disk of radius 11 centred at −1-1, 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 c=0.5c = 0.5 the worst wave is θ=π/2\theta = \pi/2 (four cells per wavelength), ∣G∣=1.25=1.1180\lvert G\rvert = \sqrt{1.25} = 1.1180. Seeded at 10−1610^{-16} it needs 330330 steps to reach 11 (see the problems): calm for hundreds of steps, then failure in tens. One qualification: this is for a fixed CFL number. With Δt∝h2\Delta t \propto h^2 we get ∣G∣2−1≤c2=O(Δt)\lvert G\rvert^2 - 1 \le c^2 = O(\Delta t), which is allowed, but that step is the diffusion cost for a problem that should need a step proportional to hh.

Upwind: stable when information is not skipped

If the wind blows from left to right (a>0a \gt 0), the information that decides uju_j comes from the left. Upwind differences against the wind:

ujn+1=ujn−c(ujn−uj−1n)=(1−c) ujn+c uj−1n,G=(1−c)+c e−iθ.u_j^{n+1} = u_j^n - c\left(u_j^n - u_{j-1}^n\right) = (1-c)\,u_j^n + c\,u_{j-1}^n, \qquad G = (1 - c) + c\,e^{-i\theta}.

For 0≤c≤10 \le c \le 1, GG is a weighted average of the points 11 and e−iθe^{-i\theta} of the unit circle with nonnegative weights, so it lies on the chord between them, inside the disk: ∣G∣≤1\lvert G\rvert \le 1 with no algebra. Written out,

∣G∣2=(1−c+ccos⁡θ)2+c2sin⁡2θ=1−2c(1−c)(1−cos⁡θ).\lvert G\rvert^2 = (1 - c + c\cos\theta)^2 + c^2\sin^2\theta = 1 - 2c(1-c)(1 - \cos\theta).

For c>1c \gt 1 the weight 1−c1 - c is negative, c(1−c)c(1-c) flips sign, and ∣G∣>1\lvert G\rvert \gt 1 for every θ>0\theta \gt 0, worst at θ=π\theta = \pi where G=1−2cG = 1 - 2c: −1.4-1.4 for c=1.2c = 1.2. At c=1c = 1, G=e−iθG = e^{-i\theta} and the scheme is the exact shift by one cell.

So upwind is stable exactly for 0≤c≤10 \le c \le 1. For c>1c \gt 1 the true solution at xjx_j 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 ujnu_j^n in the centred scheme by the average of its neighbours:

ujn+1=12(uj+1n+uj−1n)−c2(uj+1n−uj−1n).u_j^{n+1} = \tfrac12\left(u_{j+1}^n + u_{j-1}^n\right) - \frac{c}{2}\left(u_{j+1}^n - u_{j-1}^n\right).

Since 12(uj+1+uj−1)=uj+12(uj+1−2uj+uj−1)\tfrac12(u_{j+1} + u_{j-1}) = u_j + \tfrac12(u_{j+1} - 2u_j + u_{j-1}), this is the centred scheme plus an explicit diffusion step with r=1/2r = 1/2. In GG the extra term is cos⁡θ−1=−2sin⁡2(θ/2)\cos\theta - 1 = -2\sin^2(\theta/2), a push inward: G=cos⁡θ−icsin⁡θG = \cos\theta - ic\sin\theta and

∣G∣2=cos⁡2θ+c2sin⁡2θ=1−(1−c2)sin⁡2θ.\lvert G\rvert^2 = \cos^2\theta + c^2\sin^2\theta = 1 - (1 - c^2)\sin^2\theta.

It is stable exactly when c≤1c \le 1, the same limit as upwind, and at c=1c = 1 it too is the exact shift. The price is smearing, next.

What ∣G∣<1\lvert G\rvert \lt 1 does to a wave: numerical diffusion

A stable scheme can still lose amplitude on waves that should keep it. For small θ\theta the upwind modulus is ∣G∣2≈1−c(1−c)θ2\lvert G\rvert^2 \approx 1 - c(1-c)\theta^2, so after nn steps

∣G∣n≈e−12c(1−c) nθ2.\lvert G\rvert^n \approx e^{-\frac12 c(1-c)\,n\theta^2}.

Physical diffusion ut=Duxxu_t = Du_{xx} multiplies a wave eikxe^{ikx} by e−Dk2te^{-Dk^2t} over time tt. With θ=kh\theta = kh and t=nch/at = nch/a the two agree when Dnum=12ah(1−c)D_{\text{num}} = \tfrac12 ah(1 - c): the scheme behaves as if the equation had an extra viscosity of that size. Lax-Friedrichs gives e−12(1−c2)nθ2e^{-\frac12(1-c^2)n\theta^2}, a larger one.

The lab checks it. The Gaussian pulse e−((x−0.3)/0.06)2e^{-((x-0.3)/0.06)^2} is 66 cells wide, variance 1818 cells2^2. Diffusion adds 2Dt2Dt to a variance: c(1−c)nc(1-c)n cells2^2 for upwind, (1−c2)n(1-c^2)n for Lax-Friedrichs, and the peak falls by 18/new variance\sqrt{18/\text{new variance}}. At c=0.5c = 0.5 after 200200 steps (once around the periodic domain):

  • Upwind: variance 18+50=6818 + 50 = 68, predicted peak 18/68=0.514\sqrt{18/68} = 0.514; the lab shows 0.51410.5141.
  • Lax-Friedrichs: variance 18+150=16818 + 150 = 168, predicted 0.3270.327; the lab shows 0.32690.3269.
  • Upwind, c=0.25c = 0.25, 400400 steps: variance 9393, predicted 0.4400.440; the lab shows 0.43970.4397.

All three are stable and all three smear: stable is not accurate.

The phase of GG: numerical dispersion

Per step the scheme moves mode θ\theta by −arg⁡G-\arg G, where the exact motion is −cθ-c\theta. The ratio −arg⁡G/(cθ)-\arg G/(c\theta) is the wave’s speed on the grid over its true speed. If it differs from 11 and depends on θ\theta, a pulse of many waves falls apart: numerical dispersion. From the lab’s third panel:

  • Upwind, c=0.5c = 0.5: G=12(1+e−iθ)G = \tfrac12(1 + e^{-i\theta}) has phase exactly −θ/2=−cθ-\theta/2 = -c\theta, ratio 1.00001.0000 for every θ\theta. All its error is in the modulus.
  • Upwind, c=0.25c = 0.25, θ=π/2\theta = \pi/2: G=0.75−0.25iG = 0.75 - 0.25i, ratio 0.81930.8193: 18%18\% too slow, and ∣G∣=0.7906\lvert G\rvert = 0.7906.
  • Centred, c=0.5c = 0.5: ratio 0.86540.8654 at θ=π/4\theta = \pi/4 and 0.59030.5903 at π/2\pi/2: the shorter the wave, the slower.
  • Lax-Friedrichs, c=0.5c = 0.5: ratio 1.18071.1807 at π/4\pi/4 and 2.00002.0000 at π/2\pi/2, where G=−0.5iG = -0.5i advances the phase by π/2\pi/2 per step instead of π/4\pi/4: twice too fast, and damped to 0.50.5.

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 h,Δt→0h, \Delta t \to 0.
  • Stable: a perturbation is multiplied by at most a constant independent of the number of steps (for constant coefficients, ∣G∣≤1+O(Δt)\lvert G\rvert \le 1 + O(\Delta t)).
  • 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 TT 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 TT 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

◆ Interactive Pick a scheme and a CFL number: read |G(θ)| and the unstable band, then watch a pulse run through the scheme

Loading simulation…

The domain is periodic with 100100 nodes, a=α=1a = \alpha = 1, plus noise of 10−810^{-8}. Panels: the pulse against the exact solution (dashed); ∣G(θ)∣\lvert G(\theta)\rvert with the unstable band shaded and the exact modulus as dots; the speed ratio; log⁡10max⁡∣u∣\log_{10}\max\lvert u\rvert.

  1. Centred, c=0.5c = 0.5, square pulse (first button). Largest ∣G∣=1.1180\lvert G\rvert = 1.1180 at θ=1.571\theta = 1.571, and the band is modes 11 to 4949: all of them. max⁡∣u∣\max\lvert u\rvert is 32.232.2 at step 5050 and 6.4×1036.4\times10^3 at step 100100; blown up at step 189189. Measured growth per step wanders between 1.091.09 and 1.121.12, around 1.1181.118. The Gaussian takes 324324 steps.
  2. Upwind, c=0.5c = 0.5. The curve stays below 11 (largest 0.99950.9995, at the longest wave) and the speed ratio is flat at 11. max⁡∣u∣\max\lvert u\rvert is 0.64640.6464 at step 100100 and 0.51410.5141 at step 200200: smeared, not growing.
  3. Upwind, c=1.2c = 1.2. The band is every mode; worst 1.40001.4000 at θ=π\theta = \pi. max⁡∣u∣\max\lvert u\rvert is 5.5×1055.5\times10^5 at step 100100; blown up at step 116116, growth 1.3951.395. The red vanishes at c=1c = 1.
  4. Lax-Friedrichs. At c=0.5c = 0.5 the largest modulus is 1.00001.0000 at θ=π\theta = \pi, and one lap leaves peak 0.32690.3269. At c=1.2c = 1.2 the band is 4949 modes, worst 1.20001.2000 at θ=π/2\theta = \pi/2, blown up at step 195195.
  5. FTCS diffusion, r=0.6r = 0.6 (last button). The band is modes 3737 to 5050 (θ\theta from 2.3252.325; the exact edge 2.30052.3005 lies between modes 3636 and 3737), worst 1.40001.4000. max⁡∣u∣\max\lvert u\rvert is 0.4790.479 at step 5050, then 1.9×1051.9\times10^5 at step 100100; blown up at step 120120, growth 1.3891.389.

The blow-up steps in items 3 to 5, and the Gaussian’s 324324 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

🐍 PythonLab: maximum |G| of three schemes, and a check of the upwind formula
⌘/Ctrl + Enter

The output is 1.118,1.0,1.01.118, 1.0, 1.0 at c=0.5c = 0.5; 1.4142,1.0,1.01.4142, 1.0, 1.0 at c=1c = 1; and 1.562,1.4,1.21.562, 1.4, 1.2 at c=1.2c = 1.2.

🧪 Coding exerciseExercise: measure G by evolving one Fourier mode for one step
⌘/Ctrl + Enter

Because the grid is periodic, the wave eijθe^{ij\theta} with θ=2πm/J\theta = 2\pi m/J fits it exactly and one step really does multiply it by one number: the same value for every jj, so reading j=0j = 0 is enough. This is the von Neumann analysis done by machine, and it is how you check an algebraic GG for a scheme you have just written.

Concept checks

✅ Concept check

Upwind advection at $c = 0.25$. What is the amplification factor of the sawtooth wave $\theta = \pi$? (Use $G = 1 - c + ce^{-i\theta}$.)

✅ Concept check

Centred (FTCS) advection at $c = 0.5$ and $\theta = \pi/2$. To three decimals, what is $\lvert G\rvert$?

✅ Concept check

A friend says: 'FTCS for advection blows up, so use a much smaller time step.' What happens?

✅ Concept check

If a scheme is consistent with a well-posed linear PDE and also stable, what does the Lax equivalence theorem say about it?

Problems

✏️ Pen & paperUpwind at c = 1/2●○○

Find ∣G∣\lvert G\rvert for upwind with c=0.5c = 0.5 at θ=π/2\theta = \pi/2 and θ=π\theta = \pi.

Show worked solution

G=0.5+0.5e−iθG = 0.5 + 0.5e^{-i\theta}. At θ=π/2\theta = \pi/2, G=0.5−0.5iG = 0.5 - 0.5i and ∣G∣=0.5=0.7071\lvert G\rvert = \sqrt{0.5} = 0.7071. At θ=π\theta = \pi, G=0G = 0: the sawtooth is wiped out in one step. The shortest wave is damped most, the long waves hardly at all: numerical diffusion.

✏️ Pen & paperHow long until the centred scheme fails?●●○

Centred advection starts from noise of 10−1610^{-16} in every wave. How many steps until the worst wave reaches size 11, at c=0.5c = 0.5 and at c=0.1c = 0.1?

Show worked solution

The worst wave is θ=π/2\theta = \pi/2, ∣G∣=1+c2\lvert G\rvert = \sqrt{1 + c^2}. For c=0.5c = 0.5: ln⁡(1016)/ln⁡(1.1180)=36.84/0.1116=330\ln(10^{16})/\ln(1.1180) = 36.84/0.1116 = 330 steps. For c=0.1c = 0.1: ∣G∣=1.00499\lvert G\rvert = 1.00499 and 36.84/0.004975=740536.84/0.004975 = 7405 steps. A smaller cc delays the failure, but never prevents it.

✏️ Pen & paperLax-Friedrichs from scratch●●○

(a) Show Lax-Friedrichs is the centred scheme plus diffusion with r=1/2r = 1/2. (b) Derive ∣G∣2=1−(1−c2)sin⁡2θ\lvert G\rvert^2 = 1 - (1 - c^2)\sin^2\theta. (c) Where, and how small, is ∣G∣\lvert G\rvert at c=0.5c = 0.5?

Show worked solution

(a) 12(uj+1+uj−1)=uj+12(uj+1−2uj+uj−1)\tfrac12(u_{j+1} + u_{j-1}) = u_j + \tfrac12(u_{j+1} - 2u_j + u_{j-1}), so the scheme is the centred step plus an FTCS diffusion step with r=12r = \tfrac12. (b) ∣G∣2=cos⁡2θ+c2sin⁡2θ=1−(1−c2)sin⁡2θ\lvert G\rvert^2 = \cos^2\theta + c^2\sin^2\theta = 1 - (1 - c^2)\sin^2\theta. (c) For c<1c \lt 1 the minimum is at sin⁡2θ=1\sin^2\theta = 1, θ=π/2\theta = \pi/2: ∣G∣=c=0.5\lvert G\rvert = c = 0.5. At θ=0\theta = 0 and π\pi it is 11: mid-length waves are smeared most.

✏️ Pen & paperAdvection with physical diffusion●●●

For ut+aux=αuxxu_t + au_x = \alpha u_{xx} take ujn+1=ujn−c2(uj+1n−uj−1n)+r(uj+1n−2ujn+uj−1n)u_j^{n+1} = u_j^n - \tfrac c2(u_{j+1}^n - u_{j-1}^n) + r(u_{j+1}^n - 2u_j^n + u_{j-1}^n). Show it is stable exactly when c2≤2r≤1c^2 \le 2r \le 1.

Show worked solution

With s=sin⁡2(θ/2)∈[0,1]s = \sin^2(\theta/2) \in [0, 1] and sin⁡2θ=4s(1−s)\sin^2\theta = 4s(1-s), G=1−4rs−icsin⁡θG = 1 - 4rs - ic\sin\theta and

∣G∣2=(1−4rs)2+4c2s(1−s)=1−4s[(2r−c2)−s(4r2−c2)].\lvert G\rvert^2 = (1 - 4rs)^2 + 4c^2s(1-s) = 1 - 4s\left[(2r - c^2) - s(4r^2 - c^2)\right].

The bracket must be nonnegative on [0,1][0, 1]. It is linear in ss, so check the ends: s→0s \to 0 gives 2r≥c22r \ge c^2; s=1s = 1 gives 2r(1−2r)≥02r(1 - 2r) \ge 0, so r≤12r \le \tfrac12. Physical diffusion cures the centred scheme only when α≥a2Δt/2\alpha \ge a^2\Delta t/2, 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 G=1/(1+4rsin⁡2(θ/2))G = 1/(1 + 4r\sin^2(\theta/2)) and Crank-Nicolson G=(1−2rsin⁡2(θ/2))/(1+2rsin⁡2(θ/2))G = (1 - 2r\sin^2(\theta/2))/(1 + 2r\sin^2(\theta/2)). The unknown now sits in a denominator, and both stay inside the unit circle for every rr. The price is a tridiagonal solve per step, which is how Stam’s solver diffuses momentum.

Key Takeaways

  • Put ujn=Gneijθu_j^n = G^n e^{ij\theta}, θ=kh\theta = kh, into a linear constant-coefficient scheme and solve for G(θ)G(\theta): modulus is growth per step, phase is motion per step; θ∈[0,π]\theta \in [0, \pi] suffices.
  • Von Neumann condition: ∣G∣≤1\lvert G\rvert \le 1 for all θ\theta. The set where it fails is the unstable band, which grows geometrically from rounding noise.
  • FTCS diffusion: G=1−4rsin⁡2(θ/2)G = 1 - 4r\sin^2(\theta/2), stable for r≤1/2r \le 1/2, with no matrix needed.
  • Centred advection: ∣G∣2=1+c2sin⁡2θ\lvert G\rvert^2 = 1 + c^2\sin^2\theta, unstable for every fixed cc (forward Euler on imaginary eigenvalues).
  • Upwind: ∣G∣2=1−2c(1−c)(1−cos⁡θ)\lvert G\rvert^2 = 1 - 2c(1-c)(1-\cos\theta), stable exactly for 0≤c≤10 \le c \le 1. Lax-Friedrichs, 1−(1−c2)sin⁡2θ1 - (1-c^2)\sin^2\theta, stabilises the centred scheme by adding diffusion.
  • ∣G∣<1\lvert G\rvert \lt 1 is numerical diffusion (upwind: viscosity 12ah(1−c)\tfrac12 ah(1-c)); arg⁡G\arg G 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 GG in a denominator, stable for every step at the cost of a linear solve.
Finished this lesson?

Mark it complete to track your progress (saved in this browser). Reading every section does this for you.

Where this leads

These later lessons build directly on this one: