In 10.2 Explicit Methods for the Heat Equation the heat equation set a speed limit, , from the stiffest grid mode. The 10.3 Von Neumann Stability Analysis lesson previewed the way out: put the diffusion term at the new time level, so the unknown sits in a denominator. This lesson derives it. We get two schemes, backward Euler in time (BTCS) and Crank–Nicolson, each stable for every step and costing one tridiagonal solve per step. Then we see what stability does not buy: BTCS is forgiving but first order in time, while CN is second order but keeps the highest modes alive, so a sharp profile at a big step makes it ring. This is also the diffusion step of Jos Stam’s solver, the partner of the 10.7 Semi-Lagrangian Advection advection we just finished.
Transcript
- The explicit heat step has a speed limit, r at most one half. Move the Laplacian to the new time level and each step becomes a tridiagonal linear solve. The rod has 49 nodes; r equals 100 means a time step of 0.04.
- Each mode of the new matrix has eigenvalue 1 plus 4 r sine squared, so backward Euler divides every mode by at least 1. The factor is between 0 and 1 for every r: unconditionally stable, and positive like the exact decay. At r equals 100 the highest mode is crushed to about 1 over 1 plus 4 r.
- Crank Nicolson averages the old and new right sides, the trapezoid rule. Its factor is also at most 1 in size for every r, so it is stable too. But look at the stiff end. It tends to minus 1. Crank Nicolson does not damp the stiffest modes: it flips their sign and keeps their size.
- The table, for the 49 node rod at r equals 100. On the smooth mode Crank Nicolson is closest to exact: 0.6704 against 0.6738. From k equals 3 on its factor is negative. The top mode returns at minus 0.9900, flipping sign every step and losing only 1 percent. FTCS has blown up.
- Take mode 3 to time 0.02 and halve the step. BTCS errors fall by 1.91, 1.95, then 1.98: first order. CN errors fall by 4.05, 4.01, 4.00: second order. Eight CN steps are 26 times more accurate than eight BTCS steps.
- Now a sharp profile: a square pulse, one step at r equals 100. The exact solution at time 0.04 is a smooth hump with peak 0.2750. BTCS is smooth too, a little fat, with error 0.1114.
- Crank Nicolson is not. The centre is dug out to 0.0107, and the profile dips to minus 0.1516 on either side of the hole. Its error is 0.4156, almost 4 times BTCS's. The pulse's jump edges are full of high modes, and CN sends them back with a factor near minus 0.9.
- Run to step 10. The exact hump has decayed to 0.0076, and BTCS has error 0.0065, but CN still has minimum minus 0.2233 and error 0.2303. This is not instability, every factor has size at most 1. It is an accuracy failure at high wavenumbers. Check for undershoot before trusting a big CN step.
- The ringing is seeded by the high modes of the initial data. So take the first step as two BTCS half steps, then switch to Crank Nicolson: a Rannacher start. At r equals 100 the top mode is multiplied by 0.00498 twice, 2.5 times 10 to the minus 5 in all, rather than minus 0.99.
- On the same pulse, Rannacher has error 0.0525 at step 1, against 0.4156 for CN and 0.1114 for BTCS, and no negatives. At step 10 it is 4.05 times 10 to the minus 4, against 0.2303 for CN and 6.5 times 10 to the minus 3 for BTCS. The price is one extra solve: 770 operations instead of 581 for the first step.
- Thomas algorithm: a forward sweep removes the sub diagonal, then a back substitution finishes. Each forward row costs 5 operations, the back substitution 1 plus 3 per row, so the total is 8 n minus 7: 385 for n equals 49, about 200 times less than a dense solve, and linear in n.
- No pivoting is needed. The matrices are diagonally dominant, so each pivot stays above r, every multiplier is below 1 in size, and the arithmetic cannot blow up. The lab counts operations inside the code: a BTCS step costs 385, a CN step 196 plus 385 is 581, and an FTCS step 196.
- In 2D the matrix is no longer tridiagonal, but ADI keeps every solve tridiagonal: half a step implicit in x, then half a step implicit in y. For M equals 24 a full step is 13,488 operations, about 23 per cell. The factor is a product of two CN factors, so the checkerboard at r equals 100 has G equal plus 0.9801: it barely decays.
- Mode 3 again, to time 0.02, against the real decay 0.1692. FTCS must stay at r at most one half: 100 steps, error 1.79 times 10 to the minus 3, at 19,600 operations. CN with 8 steps has error 3.44 times 10 to the minus 4 at 4648. That is 5 times smaller with 4.2 times fewer operations. Accuracy, not stability, sets the step.
- To recap: BTCS and Crank Nicolson are one tridiagonal solve per step, stable for every r. CN is second order but rings on sharp data, which a Rannacher start cures. Stam's step is BTCS: r is 0.2731, and backward Euler gives 0.3140. In 2D the system is five banded, so next, lesson 10.8: relaxation sweeps.
Backward Euler in time: BTCS
Method of lines again: space on a grid gives with . Forward Euler evaluates the right side at the old time. Backward Euler evaluates it at the new one (see 4.2 The Euler Family: Forward, Backward, Heun & Midpoint):
Row by row, : BTCS, backward in time, centred in space. The new values are coupled, so each step is a linear solve, with a tridiagonal matrix.
The factor per step comes from the eigenvalues of . Its eigenvectors are the sampled sines with eigenvalues , where (10.1 Finite Differences: Discretizing Derivatives). So has the same eigenvectors with eigenvalues , and inverting it divides each mode by that number:
The denominator is at least , so for every : unconditionally stable, the A-stability of backward Euler from 4.5 Stability Regions & Stiffness applied to each eigenvalue. The highest mode () is multiplied by about : heavily damped, and positive like the exact factor. Backward Euler is also L-stable: as .
One more property. has a positive diagonal, non-positive off-diagonals and diagonal dominance, so every entry of its inverse is non-negative (the M-matrix property, from memory). A non-negative profile therefore stays non-negative: BTCS never undershoots. Keep that in mind for CN.
Crank–Nicolson: the trapezoid rule
Backward Euler is first order in time. Replace it by the trapezoid rule, which averages the right side at the old and the new time:
This is Crank–Nicolson. Each side has the same eigenvectors, so a mode is multiplied by on the right and divided by on the left:
The numerator is smaller in size than the denominator whenever , so for all : also unconditionally stable. A CN step costs a BTCS solve plus an FTCS-sized sweep for the right side.
Now the catch. Let . BTCS multiplies by and CN by , against the exact . As these tend to and . CN does not damp the stiffest modes: it flips their sign and keeps their size. That is A-stability without L-stability.
The table gives the factors for the 49-node rod () at , i.e. . Mode is smooth, is the sawtooth.
| mode | exact | BTCS | CN | FTCS |
|---|---|---|---|---|
| 1 | 0.6738 | 0.7170 | 0.6704 | 0.6053 |
| 3 | 0.0286 | 0.2201 | ||
| 49 | below | 0.0025 |
On the smooth mode CN is closest to the exact value ( against ; BTCS is off by ). From on, CN’s factor is negative. A mode the physics erases in one step comes back at and flips sign every step, losing only per step. FTCS shows the explicit instability. Only CN’s factors are wrong in sign.
Accuracy: first order against second
Compare each factor with for small (small steps). Backward Euler: against , a local error of . CN: , which matches through and misses by . Since and we take steps, the global errors are and (the language of 4.1 Local Error, Global Error & Order).
Test it on one grid mode. Take on the 49-node grid, final time , and compare with the grid mode’s own exact decay , so no spatial error enters. Halving gives:
| steps | BTCS error | ratio | CN error | ratio | |
|---|---|---|---|---|---|
| 4 | 12.5 | 0.06064 | 0.004999 | ||
| 8 | 6.25 | 0.03177 | 1.91 | 0.001236 | 4.05 |
| 16 | 3.125 | 0.01627 | 1.95 | 0.0003080 | 4.01 |
| 32 | 1.5625 | 0.008237 | 1.98 | 0.00007695 | 4.00 |
The ratios tend to and : observed orders and , as predicted. Eight CN steps are times more accurate than eight BTCS steps ( against ).
Sharp profiles at a big step: CN rings
A square pulse has large content in the high modes (its jump edges). Exact diffusion erases them; CN at a large step sends them back with a factor near . Run the pulse ( on , half height at the two edge nodes) for one step at (the lab does exactly this):
- Exact, at : a smooth hump of peak .
- BTCS: smooth, peak (too fat: first-order error), minimum , error .
- CN: peak , but the centre has been dug out to , and the profile dips to on either side of the hole. Error , almost four times BTCS’s.
At step () the exact hump has decayed to and BTCS has error , but CN still has minimum and error . At CN stays non-negative (minimum at step ) yet is off, against BTCS’s . This is not instability: every factor has size at most . It is an accuracy failure at high wavenumbers, where the factor has the wrong sign, caused by a step far larger than the profile’s own time scale.
The Rannacher start
The ringing is seeded by the high modes of the initial data. The remedy is a Rannacher start (R. Rannacher, 1984, from memory): take the first step as two BTCS half-steps, then switch to CN. The half-steps ( each) strip those modes: at the top mode is multiplied by twice, in all, rather than CN’s . By the second step the data are smooth and CN does its second-order work. On the same pulse at (fourth panel of the lab):
- Step 1: error against CN’s and BTCS’s ; minimum , no negatives.
- Step 10: against CN and BTCS . Minimum , still positive.
At the error after steps falls from (plain CN) to . The price is one extra solve: instead of operations for the first step, against over ten.
The tridiagonal system: Thomas algorithm
A dense solve of unknowns costs about operations (from memory). Ours is tridiagonal, so elimination reduces to a forward sweep and a back-substitution, the Thomas algorithm:
def thomas(a, b, c, d): # sub-, main, super-diagonal, right side
n = len(d)
for i in range(1, n): # forward sweep: remove the sub-diagonal
w = a[i-1] / b[i-1]
b[i] -= w * c[i-1]
d[i] -= w * d[i-1]
x = [0.0] * n
x[-1] = d[-1] / b[-1]
for i in range(n - 2, -1, -1): # back-substitution
x[i] = (d[i] - c[i] * x[i+1]) / b[i]
return x
Count the arithmetic. Each of the forward rows has one division, two multiplications and two subtractions: operations. The back-substitution is one division, then a multiplication, a subtraction and a division for each of rows. Total : 385 for , about times less than a dense solve, and the cost grows linearly in . The lab counts these inside the code rather than by this formula, and a BTCS step costs exactly , a CN step and an FTCS step . (The matrix never changes, so its multipliers could be computed once and the sweep trimmed; the lab does not.)
Why no pivoting? The matrices are diagonally dominant: BTCS has diagonal against off-diagonals of size , CN has against . By induction every pivot exceeds the off-diagonal size: if then . So each multiplier has size below (the same argument with covers CN), the arithmetic cannot blow up, and no row swaps are needed.
Two dimensions: ADI
In 2D the five-point matrix is no longer tridiagonal: the north and south neighbours sit places away, and elimination fills the band in. ADI (alternating-direction implicit, Peaceman–Rachford 1955, from memory) avoids this. Do half a step implicit in and explicit in , then half a step the other way:
Here and are the three-point second differences along each axis, so each half step is, for each grid line, a tridiagonal system for Thomas. Counting operations per cell for the explicit side and per line for lines, a half step is , and a full step : for , operations, about per cell. Work proportional to the number of cells, the best a method can do.
The von Neumann factor follows at once: the first half-step multiplies a mode by and divides by , the second swaps the roles, so
a product of two CN factors, so for all . It shares CN’s flaw: for the checkerboard at on the factors are each, so . The sign no longer flips, but the mode barely decays either. (Second-order accuracy, and the need for a modified form in 3D, are from memory; we do not derive them.)
What one solve buys
The explicit step must obey . The implicit step costs about three times as much but can take any , so accuracy, not stability, sets the step. Take the same mode on the 49-node grid to and measure the error against the real PDE decay :
- FTCS must stay at , so at least steps (): error , cost operations.
- CN, 8 steps (): error , cost .
- BTCS, 8 steps: error , cost . Cheap, but first order wants smaller steps.
CN reaches a times smaller error with times fewer operations. It stops helping once the time error falls below the grid’s spatial error, so choose the step that makes the two match. The advantage grows with refinement: explicit steps shrink like , implicit ones only as the accuracy demands. A fast transient you must follow step by step costs a small step either way.
The lab
The rod has nodes, , ends held at , and every scheme takes the same . Dashed is the exact PDE solution (a Fourier series of the true profile); error is the largest node difference from it; operation counts come from counters in the step functions. The bottom plot shows each scheme’s factor for every mode, with the exact factor as dots.
- Pulse, . All four agree. After steps the errors are FTCS , BTCS , CN , Rannacher , at , , and operations: at a stable step implicit methods only cost more.
- Pulse, . FTCS reaches and after one step and is flagged BLEW UP at step (step at ). At step : BTCS , CN , Rannacher .
- Pulse, . The numbers of the ringing and Rannacher sections.
- Smooth bump, , ten steps. CN beats BTCS: against , with Rannacher at . At , one step, even the bump rings under CN: minimum , error , against BTCS and Rannacher .
- The cost line. At FTCS would need sub-steps ( operations) to cross one step, against for CN, though the sub-steps would resolve the physics better.
Computing it
The output reproduces the cost-benefit list ( at , at , at ) and the top-mode factors and .
With , , the solution gives errors , , for , , steps (ratios , ).
Concept checks
Problems
Take interior nodes (). For the highest mode at , find the FTCS, BTCS and CN factors.
Show worked solution
. FTCS: (unstable). BTCS: . CN: : bounded, negative, well short of on this coarse grid.
On the 49-node rod () at , for which is ?
Show worked solution
exactly when , i.e. , i.e. . So , : modes . At the same steps give , matching the table.
Solve , , with the Thomas algorithm, and give the operation count.
Show worked solution
Forward: , , . Then , , . Back: , , . Row two checks: . Operations: .
Key Takeaways
- BTCS: , , in for every . It never undershoots; first order in time.
- CN is the trapezoid rule: . Stable for every , second order (local error ); halving gave ratios , , .
- CN’s factor tends to at the top of the spectrum: at one step on the pulse gives minimum and error .
- A Rannacher start (two BTCS half-steps, then CN) gives error at step and at step on that pulse, for about extra work.
- The system is tridiagonal and diagonally dominant: Thomas solves it in operations without pivoting.
- ADI: tridiagonal solves along rows, then columns, about operations per cell at ; its factor is a product of two CN factors.
- One solve per step buys any when accuracy sets the step: on the smooth mode CN is more accurate than FTCS with fewer operations.
- Next: in 2D the implicit matrix is five-banded, not tridiagonal. ADI is one fix; the other, which Stam uses, is relaxation by Jacobi or Gauss–Seidel sweeps. 10.8 Elliptic Solvers: Jacobi, Gauss–Seidel & SOR (lesson 10.8) covers how fast that converges.