10.3 Von Neumann Stability Analysis pushed an advection equation through three finite-difference schemes and found that two of them failed above a Courant number of one. It never asked what the true solution does. This lesson solves the equation exactly, for a constant wind and then a varying one, with a tool you already own: the equation hides a family of ODEs, and your ODE solvers integrate them. The reward is the advection step of Jos Stam’s solver, which traces backward along the ODE for one step and reads the value it finds there.
Transcript
- Last lesson pushed u t plus c u x equals 0 through three schemes, and two failed above a Courant number of 1. Today we solve it exactly, because the equation hides a family of ODEs.
- Walk along a path x of t and read u. By the chain rule it changes at u t plus d x d t times u x. Choose d x d t equal to c and this is the left side of the PDE, which is zero. So u is constant along every curve d x d t equals c: the characteristics.
- For constant c they are straight lines and the solution is u 0 of x minus c t: the profile translates. To know u at x and t, walk backward along the characteristic to time zero and look. The landing point is the foot.
- The combination u t plus c u x is the material derivative, D u over D t: the rate of change riding the characteristic. A fixed station sees u change; a balloon in the wind sees it constant.
- Let the wind vary. The characteristics now solve d x d t equals c of x and t, and u is still constant on each. In the lab c is 1 plus b sine 2 pi x, with b equal to 0.5. One lap takes 1.1547, and a pulse starting at 0.25 is at 0.553, 0.711 and 0.841 at times 0.25, 0.5 and 0.75, then 0.040 at t equals 1.
- Characteristics lean over where c is large, so pulses stretch in fast zones and squeeze in slow ones. The lab pulse is 0.17 wide at half height at t equals 0 and 0.06 wide at t equals 0.5, on a grid of 0.005: about the speed ratio 0.514 over 1.5, or 0.34.
- For a variable wind there are two different equations. The conservative form keeps the integral of u: u is a density. Expanding it gives d u d t equals minus c sub x times u, so u decays where the wind speeds up. The exact result: c times u is constant along each characteristic.
- In the lab, with b equal to 0.5, 200 cells and a Gaussian at 0.25, look at t equals 0.5. The non-conservative pulse has peak 0.9979, unchanged. The conservative pulse has peak 2.9129 and mass 0.1772, while the non-conservative mass has dropped to 0.0638.
- Real dye diffuses, so add D u x x. Ride with the wind and it is just the heat equation: advection moves, diffusion smears. A pulse is carried one width in time L over c, and smears over its width in L squared over D. Their ratio is the Peclet number.
- With L equal to w equal to 0.1 and t equal to 1, ten widths of travel, the exact peak is 1 over the square root of 1 plus 40 over Pe: 0.4472 at Pe 10, 0.7071 at 40, 0.9129 at 200, 0.9806 at 1000. The lab, at CFL 1, gives 0.4471, 0.7068, 0.9124 and 0.9800.
- Now do the backward walk one step at a time: the advection step of Jos Stam's solver. The new value at x j is the old value at the foot X j of a one-step backtrace. The foot falls between nodes, so interpolate: 1 minus f times one neighbour plus f times the other.
- The new value is a weighted average of old values, so no step creates a new extreme, whatever the CFL number. With constant wind and CFL 4, upwind passes 10 to the 6 by step 23, while semi-Lagrangian reaches t equals 1 with L 2 error 2 times 10 to the minus 14.
- The price is smoothing: variance f times 1 minus f cells squared per step. At an integer CFL, f is 0 and the peak stays 0.9994 at CFL 1 through 5. The Gaussian has variance 200 cells squared. At CFL 2.5, 80 steps add 20, so the peak falls by the square root of 200 over 220: 0.953.
- On a constant wind at t equals 1, CFL 2.5 gives peak 0.9529, CFL 0.5 gives 0.8161, and CFL 0.25 gives 0.7557. More steps, more smoothing, so large steps are cheaper and, here, more accurate.
- For a variable wind f is almost never zero, so backtrace accuracy matters. At b equal to 0.5 and CFL 4, the L 2 error is 0.0182 with an RK4 backtrace and 0.0234 with Euler. And mass is only approximately conserved: 0.17669 against 0.17725 at CFL 0.5.
- To recap: u is constant along characteristics, so the PDE is a family of ODEs; the forms differ by c sub x times u; Peclet measures smearing; semi-Lagrangian trades smoothing and exact conservation for stability at any CFL.
- Next, let the speed depend on u itself. Characteristics cross and the smooth solution fails. In Burgers' equation, lesson 9.11, that becomes a shock.
The transport equation
The simplest PDE for motion says that a quantity is carried at constant speed :
Suppose someone walks along the line and reads at the walker’s position. By the chain rule (2.2 Linearization, the Chain Rule & the Jacobian) the reading changes at the rate
Choose the walker’s speed to be . The right side is then exactly the left side of the PDE, which is zero. So is constant along every curve . These curves are the characteristics, and they replace a PDE with a family of trivial ODEs: along each, .
For constant the characteristics are the straight lines . The value on the line through is the starting value . To find , ask which line passes through : it started at , so
Check: and . The profile translates intact. Read the formula as a recipe: to know at , walk backward along the characteristic to time zero and look. The landing point is the foot of the characteristic, and the numerical method at the end performs this recipe one step at a time.
Information travels only along these curves, which is why upwind schemes look upstream.
The material derivative
The combination has a name in fluid mechanics. If is the fluid velocity and some property of the fluid, then is the change seen at a fixed point and is the change due to the fluid arriving from a place where was different. Their sum is the material derivative,
the rate of change riding the characteristic: seen by a particle drifting with the flow. This is the 1D version of the formula derived in 11.1 Continuum Hypothesis & Flow Kinematics. The transport equation is simply : a property that nothing creates or destroys is constant on each particle. A balloon drifting with the air sees a constant value while a fixed station sees it change, and both statements are one equation. If something does create it, the equation becomes and along the characteristic you integrate , an ODE again.
Variable speed: characteristics are ODE solutions
Now let the wind vary, . The argument above never used constancy: the characteristics are the solutions of
and is still constant on each. These curves are no longer straight, but they are exactly the integral curves of 2.6 Vector Fields, Flow Lines & Streamlines, the paths of particles, and you can compute them with the integrators of 4.3 Runge–Kutta Methods & Butcher Tableaux. With smooth, existence and uniqueness (3.7 Existence & Uniqueness) say characteristics never cross, so every has exactly one foot.
A case with a closed form. Take . Then gives , so the foot of the characteristic through is and
A pulse centred at with width moves to with width and the same height: the front outruns the back, so the pulse stretches.
A case that needs the computer. In the lab the wind is on a periodic unit interval. The time for one lap is a clean integral, (a standard integral, quoted from memory, not derived here), which is for (the playground cell below integrates the ODE with RK4 and gets it). A Gaussian pulse starting at with has its centre at at , at , at and has lapped to at . It crawls through the slow zone near , where falls to .
In the x-t plane ( pointing up) characteristics lean over where is large and stand up steeply where it is small. Pulses stretch in a fast zone and squeeze in a slow one: the lab’s pulse is wide at half height at and wide at (grid resolution ), about the speed ratio .
If also depends on the ODE is merely non-autonomous; the exercise below uses such a .
Conservative or non-conservative?
For a variable wind there are two natural equations, and they are different:
The first is and was just solved. The second is a conservation law. Integrate it over a periodic domain and the flux term integrates to zero, so never changes: is a density, like mass per length, moved around without being created. Expanding the derivative shows the difference:
The characteristics are the same curves, but decays where the wind speeds up (, the density thins out) and grows where it slows (, a pile-up). The exact result is neat. Along a characteristic by the chain rule, so and . Hence
In a steady traffic stream the flux is the same everywhere: cars crawl where the road is crowded.
The lab shows it with . The same Gaussian starts at , where . At it has reached where . The non-conservative pulse has peak (unchanged, to the grid’s resolution), but the conservative pulse has peak (versus the centre’s estimate ), and its mass is , equal to at the start. The non-conservative mass is not conserved at all: at and at . Which equation is right depends on what is: a carried property such as temperature is ; a mass density is the conservative form.
Adding diffusion: the Peclet number
Real dye diffuses. The advection-diffusion equation adds the physics of 9.2 The Heat (Diffusion) Equation:
For constant , change to a frame riding with the wind, , and write . The chain rule gives and , so the equation becomes : the plain heat equation. Advection moves, diffusion smears, and in the moving frame they do not interact. A Gaussian of width (meaning ) obeys the heat equation by keeping its shape and growing as , with the peak falling to keep the mass:
What decides whether this matters? A pulse of width is carried one width in the advective time and smears over its own width in the diffusive time . Their ratio is the Peclet number
Like the Reynolds number (11.5 Non-dimensionalization & the Reynolds Number), it compares two rates. Large Pe means many widths of travel before blurring: after travelling widths (), with , and the peak is . Even costs a quarter of the peak after widths ().
The lab defines , , and runs to , which is widths. The exact peak is then : at , at , at , at . With and diffusion on, the lab (dotted curve: the exact Gaussian) gives , , and at CFL ; the small shortfall is discretisation error whose sources (grid, explicit sub-steps, splitting) I did not separate.
The semi-Lagrangian idea
Back to the recipe: walk backward along the characteristic and read the old value. Numerically, do it one time step at a time. Given the profile on a grid, the new value at is the old value at the point where the characteristic through stood at time :
Computing is the ODE stepped backward: one Euler step, one RK4 step, or several. The foot falls between nodes, so interpolate: if is a fraction of the way from to , then . That is the whole method.
Stable for any step. The new value is a weighted average of two old values with weights and in , so : no step creates a new extreme, whatever and . In von Neumann language (10.3 Von Neumann Stability Analysis) for every wavenumber and every CFL number. Upwind was stable only if the foot lay within one cell; this step follows the characteristic however far it goes. In the lab at constant wind and CFL (four cells per step) upwind passes by step , while semi-Lagrangian reaches with error .
The price: interpolation smooths. Weights and on points one cell apart have variance cells, and that variance is added to the pulse every step (the stable-fluids lesson writes it as numerical viscosity ). Two checks:
- Integer CFL is exact. At constant wind whenever the CFL number is whole, so nothing is interpolated: the peak stays at CFL .
- More steps, more smoothing. The Gaussian with is cells wide, variance cells. At CFL () the steps add , so the peak falls by ; the lab shows . At CFL the steps add : predicted , measured , identical to upwind since for the weights are those of . Large steps are cheaper and, here, more accurate, the opposite of explicit time stepping.
For a variable wind the fraction is nonzero almost everywhere, so smoothing never vanishes, and backtrace accuracy matters. At , CFL (the largest foot is cells back) the error at is with an RK4 backtrace and with Euler. For the conservative form interpolate , which is constant on characteristics, and divide by ; the mass is then conserved only approximately: against at CFL , where flux-form upwind conserves it to rounding.
The lab
The wind is on with cells, run to . Top: profile against exact (dashed). Middle: the x-t plane, characteristics coloured by the value they carry, with four bold backtraces from now to . Bottom: of the error. All numbers are at unless stated:
- CFL 4, constant wind (first button): parallel straight characteristics; the numbers above. At CFL the peak is ; at , ; at , .
- Diffusion on, CFL , sweep Pe: the peaks above, against the dotted curve.
- Non-conservative, , CFL : the pulse narrows near at and its peak stays . Switch to conservative: the dashed exact peak is . The numerical curves stay lower ( against the exact at ): smoothing eats a -cell pulse, so judge amplitude by the dashed curve.
- , CFL 1: the local CFL reaches . Upwind passes at step ; semi-Lagrangian finishes with error . The threshold is not sharp: at CFL the local CFL exceeds only by near the fastest point and upwind survives the run.
- SL backtrace: Euler against RK4 at , CFL : the errors quoted above.
Computing it
The exact solution keeps height and stretches the pulse by , centre to . Maximum error and peak: steps and ; steps and ; steps and . RK4 over lands within of the exact foot ( against ); an Euler backtrace gives maximum error over the same steps.
Concept checks
Problems
Solve , . Find and the peak’s position at .
Show worked solution
. The foot of is , so . The peak of is at , so at it is at .
Let . (a) Solve for a pulse centred at of width : how wide and tall is it at ? (b) Solve and show is constant.
Show worked solution
(a) . The centre reaches at with width and the same height.
(b) is constant on characteristics, so . Check with : , , so and gives . With , . At the pulse is three times wider and a third as tall.
A dye pulse of width cm travels at m/s in a pipe with m/s. Find Pe (with ) and the factor by which the peak has fallen after m.
Show worked solution
. The time is s, so m against m, and the peak is . Pe still costs a quarter of the peak, since m is widths and .
A constant wind moves a profile cells per step. Find the interpolation weights and the variance added per step; then the factor by which a Gaussian with cells loses peak in steps.
Show worked solution
The foot is cells plus back: , variance cells per step (the whole-cell shift adds none). The Gaussian has variance ; after steps . The peak goes as , so the factor is ; the lab shows .
What comes next
Let the speed depend on itself, . Characteristics are still straight lines, each with its own slope, so taller parts move faster, catch the parts ahead and the lines cross. Where they cross would be multi-valued and the smooth solution fails. In 9.11 Nonlinear Waves: Burgers' Equation & Shocks (9.11, Burgers’ equation) this becomes a shock: the characteristic picture says when and where, and the conservative form says how to continue past it. Later, the wave equation (9.4) factors into two transport equations, and the advection-schemes lesson of Module 10 returns to the grid with the trade you measured here between stability, smoothing and conservation.
Key Takeaways
- means is constant along the characteristics ; for constant the solution is .
- For variable the characteristics solve an ODE (your RK4), and .
- is the material derivative . The conservative form differs by : is constant on characteristics. In the lab (, ) the conservative peak is , the non-conservative one .
- Advection-diffusion in the moving frame is the heat equation; , and after widths the peak is .
- Semi-Lagrangian: trace back one step and interpolate. An average of old values, so stable at any CFL; it costs cells of smoothing per step (zero at integer CFL) and exact mass conservation.
- Let depend on and characteristics collide: Burgers’ equation and shocks.