Flow Lab

Syllabus / Module 10: Numerical Methods for PDEs

Lesson 10.4

Implicit Methods & Crank–Nicolson

Backward Euler in time (BTCS), Crank–Nicolson, tridiagonal systems and the Thomas algorithm, ADI for 2D.

Written byClaude Sonnet

🌊
Why this matters for simulation: Implicit viscosity is standard in fluid solvers for large time steps.

By the end of this lesson you can…

  • Write BTCS and Crank–Nicolson (CN) for the heat equation as tridiagonal systems and derive their per-mode factors from the eigenvalues of the semi-discrete matrix.
  • Show both are stable for every $r = \alpha\Delta t/h^2$, and explain why CN's factor tends to $-1$ for the highest modes while BTCS's tends to $0$.
  • Measure the orders in time (one for BTCS, two for CN) by halving $\Delta t$, and explain them from the Taylor expansion of each factor.
  • Implement the Thomas algorithm, count its $8n-7$ operations, and say why diagonal dominance means no pivoting.
  • Predict and measure CN's ringing on a sharp profile at a large step, and cure it with a Rannacher start.
  • Describe ADI in 2D and say when one linear solve per step is worth paying for.
On this page
·
  1. Backward Euler in time: BTCS
  2. Crank–Nicolson: the trapezoid rule
  3. Accuracy: first order against second
  4. Sharp profiles at a big step: CN rings
  5. The Rannacher start
  6. The tridiagonal system: Thomas algorithm
  7. Two dimensions: ADI
  8. What one solve buys
  9. The lab
  10. Computing it
  11. Concept checks
  12. Problems
  13. Key Takeaways

In 10.2 Explicit Methods for the Heat Equation the heat equation set a speed limit, r=αΔt/h2≤12r = \alpha\Delta t/h^2 \le \tfrac12, 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.

▶ Video Moving the Laplacian to the new time level, the per-mode factors of BTCS and CN, the sharp pulse ringing under CN, the Thomas sweep, ADI, and the Rannacher fixcaptions only
Transcript
  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. 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.
  8. 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.
  9. 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.
  10. 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.
  11. 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.
  12. 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.
  13. 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.
  14. 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.
  15. 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 u˙=αh2Lu\dot{\mathbf u} = \tfrac{\alpha}{h^2}L\mathbf u with L=tridiag(1,−2,1)L = \mathrm{tridiag}(1,-2,1). 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):

un+1=un+r L un+1⟺(I−rL) un+1=un,r=αΔth2.\mathbf u^{n+1} = \mathbf u^n + r\,L\,\mathbf u^{n+1} \quad\Longleftrightarrow\quad (I - rL)\,\mathbf u^{n+1} = \mathbf u^n, \qquad r = \frac{\alpha\Delta t}{h^2}.

Row by row, −r ui−1n+1+(1+2r) uin+1−r ui+1n+1=uin-r\,u_{i-1}^{n+1} + (1+2r)\,u_i^{n+1} - r\,u_{i+1}^{n+1} = u_i^n: 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 LL. Its eigenvectors are the sampled sines sin⁡(kπxi)\sin(k\pi x_i) with eigenvalues −4sin⁡2(θ/2)-4\sin^2(\theta/2), where θ=kπh\theta = k\pi h (10.1 Finite Differences: Discretizing Derivatives). So I−rLI - rL has the same eigenvectors with eigenvalues 1+4rsin⁡2(θ/2)1 + 4r\sin^2(\theta/2), and inverting it divides each mode by that number:

GBTCS(θ)=11+4rsin⁡2(θ/2).G_{\mathrm{BTCS}}(\theta) = \frac{1}{1 + 4r\sin^2(\theta/2)} .

The denominator is at least 11, so 0<G≤10 \lt G \le 1 for every rr: unconditionally stable, the A-stability of backward Euler from 4.5 Stability Regions & Stiffness applied to each eigenvalue. The highest mode (sin⁡2≈1\sin^2 \approx 1) is multiplied by about 1/(1+4r)1/(1+4r): heavily damped, and positive like the exact factor. Backward Euler is also L-stable: G→0G \to 0 as r→∞r \to \infty.

One more property. I−rLI - rL 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:

un+1=un+r2 L (un+un+1)⟺(I−r2L)un+1=(I+r2L)un.\mathbf u^{n+1} = \mathbf u^n + \frac r2\,L\,(\mathbf u^n + \mathbf u^{n+1}) \quad\Longleftrightarrow\quad \Big(I - \frac r2 L\Big)\mathbf u^{n+1} = \Big(I + \frac r2 L\Big)\mathbf u^n .

This is Crank–Nicolson. Each side has the same eigenvectors, so a mode is multiplied by 1−2rsin⁡2(θ/2)1 - 2r\sin^2(\theta/2) on the right and divided by 1+2rsin⁡2(θ/2)1 + 2r\sin^2(\theta/2) on the left:

GCN(θ)=1−2rsin⁡2(θ/2)1+2rsin⁡2(θ/2).G_{\mathrm{CN}}(\theta) = \frac{1 - 2r\sin^2(\theta/2)}{1 + 2r\sin^2(\theta/2)} .

The numerator is smaller in size than the denominator whenever sin⁡2>0\sin^2 \gt 0, so ∣G∣≤1\lvert G\rvert \le 1 for all rr: also unconditionally stable. A CN step costs a BTCS solve plus an FTCS-sized sweep for the right side.

Now the catch. Let z=−λΔt=4rsin⁡2(θ/2)z = -\lambda\Delta t = 4r\sin^2(\theta/2). BTCS multiplies by 1/(1+z)1/(1+z) and CN by (1−z/2)/(1+z/2)(1 - z/2)/(1 + z/2), against the exact e−ze^{-z}. As z→∞z \to \infty these tend to 00 and −1-1. 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 (h=1/50h = 1/50) at r=100r = 100, i.e. Δt=0.04\Delta t = 0.04. Mode k=1k=1 is smooth, k=49k = 49 is the sawtooth.

mode kkexactBTCSCNFTCS
10.67380.71700.67040.6053
30.02860.2201−0.2783-0.2783−2.5425-2.5425
49below 10−30010^{-300}0.0025−0.9900-0.9900−398.6-398.6

On the smooth mode CN is closest to the exact value (0.67040.6704 against 0.67380.6738; BTCS is off by 0.0430.043). From k=3k = 3 on, CN’s factor is negative. A mode the physics erases in one step comes back at −0.99-0.99 and flips sign every step, losing only 1%1\% per step. FTCS shows the explicit instability. Only CN’s factors are wrong in sign.

Accuracy: first order against second

Compare each factor with e−ze^{-z} for small zz (small steps). Backward Euler: 1/(1+z)=1−z+z2−⋯1/(1+z) = 1 - z + z^2 - \cdots against e−z=1−z+12z2−⋯e^{-z} = 1 - z + \tfrac12 z^2 - \cdots, a local error of 12z2\tfrac12 z^2. CN: (1−z/2)/(1+z/2)=1−z+12z2−14z3+⋯(1-z/2)/(1+z/2) = 1 - z + \tfrac12z^2 - \tfrac14z^3 + \cdots, which matches e−ze^{-z} through z2z^2 and misses by −112z3-\tfrac1{12}z^3. Since z∝Δtz \propto \Delta t and we take T/ΔtT/\Delta t steps, the global errors are O(Δt)O(\Delta t) and O(Δt2)O(\Delta t^2) (the language of 4.1 Local Error, Global Error & Order).

Test it on one grid mode. Take k=3k = 3 on the 49-node grid, final time T=0.02T = 0.02, and compare with the grid mode’s own exact decay eλT=0.17012e^{\lambda T} = 0.17012, so no spatial error enters. Halving Δt\Delta t gives:

stepsrrBTCS errorratioCN errorratio
412.50.060640.004999
86.250.031771.910.0012364.05
163.1250.016271.950.00030804.01
321.56250.0082371.980.000076954.00

The ratios tend to 22 and 44: observed orders log⁡22=1\log_2 2 = 1 and log⁡24=2\log_2 4 = 2, as predicted. Eight CN steps are 2626 times more accurate than eight BTCS steps (1.236×10−31.236\times10^{-3} against 3.177×10−23.177\times10^{-2}).

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 −0.9-0.9. Run the pulse (u=1u = 1 on 0.4<x<0.60.4 \lt x \lt 0.6, half height at the two edge nodes) for one step at r=100r = 100 (the lab does exactly this):

  • Exact, at t=0.04t = 0.04: a smooth hump of peak 0.27500.2750.
  • BTCS: smooth, peak 0.38640.3864 (too fat: first-order error), minimum 0.00850.0085, error 0.11140.1114.
  • CN: peak 0.65330.6533, but the centre has been dug out to 0.01070.0107, and the profile dips to −0.1516-0.1516 on either side of the hole. Error 0.41560.4156, almost four times BTCS’s.

At step 1010 (t=0.4t = 0.4) the exact hump has decayed to 0.00760.0076 and BTCS has error 0.00650.0065, but CN still has minimum −0.2233-0.2233 and error 0.23030.2303. At r=10r = 10 CN stays non-negative (minimum 0.01490.0149 at step 1010) yet is 0.02830.0283 off, against BTCS’s 0.00890.0089. This is not instability: every factor has size at most 11. 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 (r/2r/2 each) strip those modes: at r=100r = 100 the top mode is multiplied by 1/(1+200⋅0.999)=0.004981/(1 + 200\cdot 0.999) = 0.00498 twice, 2.5×10−52.5\times10^{-5} in all, rather than CN’s −0.99-0.99. By the second step the data are smooth and CN does its second-order work. On the same pulse at r=100r = 100 (fourth panel of the lab):

  • Step 1: error 0.05250.0525 against CN’s 0.41560.4156 and BTCS’s 0.11140.1114; minimum 0.01070.0107, no negatives.
  • Step 10: 4.05×10−44.05\times10^{-4} against CN 0.23030.2303 and BTCS 6.5×10−36.5\times10^{-3}. Minimum 4.7×10−44.7\times10^{-4}, still positive.

At r=10r = 10 the error after 1010 steps falls from 0.02830.0283 (plain CN) to 3.05×10−43.05\times10^{-4}. The price is one extra solve: 770770 instead of 581581 operations for the first step, 59995999 against 58105810 over ten.

The tridiagonal system: Thomas algorithm

A dense solve of n=49n = 49 unknowns costs about 23n3≈78,000\tfrac23 n^3 \approx 78{,}000 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 n−1n-1 forward rows has one division, two multiplications and two subtractions: 55 operations. The back-substitution is one division, then a multiplication, a subtraction and a division for each of n−1n-1 rows. Total 5(n−1)+1+3(n−1)=8n−75(n-1) + 1 + 3(n-1) = 8n - 7: 385 for n=49n = 49, about 200200 times less than a dense solve, and the cost grows linearly in nn. The lab counts these inside the code rather than by this formula, and a BTCS step costs exactly 385385, a CN step 196+385=581196 + 385 = 581 and an FTCS step 196196. (The matrix never changes, so its multipliers ww could be computed once and the sweep trimmed; the lab does not.)

Why no pivoting? The matrices are diagonally dominant: BTCS has diagonal 1+2r1+2r against off-diagonals of size rr, CN has 1+r1+r against r/2r/2. By induction every pivot bi′b_i' exceeds the off-diagonal size: if bi−1′>rb'_{i-1} \gt r then bi′=1+2r−r2/bi−1′>1+rb'_i = 1 + 2r - r^2/b'_{i-1} \gt 1 + r. So each multiplier ww has size below 11 (the same argument with r/2r/2 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 MM 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 xx and explicit in yy, then half a step the other way:

(1−r2δx2)u∗=(1+r2δy2)un,(1−r2δy2)un+1=(1+r2δx2)u∗.\Big(1 - \tfrac r2\delta_x^2\Big)u^{*} = \Big(1 + \tfrac r2\delta_y^2\Big)u^{n}, \qquad \Big(1 - \tfrac r2\delta_y^2\Big)u^{n+1} = \Big(1 + \tfrac r2\delta_x^2\Big)u^{*}.

Here δx2\delta_x^2 and δy2\delta_y^2 are the three-point second differences along each axis, so each half step is, for each grid line, a tridiagonal system for Thomas. Counting 44 operations per cell for the explicit side and 8M−78M - 7 per line for MM lines, a half step is 12M2−7M12M^2 - 7M, and a full step 24M2−14M24M^2 - 14M: for M=24M = 24, 13,48813{,}488 operations, about 2323 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 1−2rsin⁡2(θy/2)1 - 2r\sin^2(\theta_y/2) and divides by 1+2rsin⁡2(θx/2)1 + 2r\sin^2(\theta_x/2), the second swaps the roles, so

GADI=1−2rsin⁡2(θx/2)1+2rsin⁡2(θx/2)⋅1−2rsin⁡2(θy/2)1+2rsin⁡2(θy/2),G_{\mathrm{ADI}} = \frac{1 - 2r\sin^2(\theta_x/2)}{1 + 2r\sin^2(\theta_x/2)}\cdot\frac{1 - 2r\sin^2(\theta_y/2)}{1 + 2r\sin^2(\theta_y/2)} ,

a product of two CN factors, so ∣G∣≤1\lvert G\rvert \le 1 for all rr. It shares CN’s flaw: for the checkerboard at r=100r = 100 on M=24M = 24 the factors are −0.9900-0.9900 each, so G=+0.9801G = +0.9801. 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 Δt≤h2/(2α)\Delta t \le h^2/(2\alpha). The implicit step costs about three times as much but can take any Δt\Delta t, so accuracy, not stability, sets the step. Take the same k=3k=3 mode on the 49-node grid to T=0.02T = 0.02 and measure the error against the real PDE decay e−(3π)2T=0.1692e^{-(3\pi)^2T} = 0.1692:

  • FTCS must stay at r≤0.5005r \le 0.5005, so at least 100100 steps (r=0.5r = 0.5): error 1.79×10−31.79\times10^{-3}, cost 100×196=19,600100\times196 = 19{,}600 operations.
  • CN, 8 steps (r=6.25r = 6.25): error 3.44×10−43.44\times10^{-4}, cost 8×581=46488\times581 = 4648.
  • BTCS, 8 steps: error 0.03270.0327, cost 8×385=30808\times385 = 3080. Cheap, but first order wants smaller steps.

CN reaches a 55 times smaller error with 4.24.2 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 h2h^2, implicit ones only as the accuracy demands. A fast transient you must follow step by step costs a small step either way.

The lab

◆ Interactive FTCS, BTCS, Crank–Nicolson and CN with a Rannacher start on the same time step, against the exact solution

Loading simulation…

The rod has 4949 nodes, α=1\alpha = 1, ends held at 00, and every scheme takes the same Δt=rh2\Delta t = rh^2. 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 GG for every mode, with the exact factor as dots.

  1. Pulse, r=0.4r = 0.4. All four agree. After 1010 steps the errors are FTCS 6.22×10−36.22\times10^{-3}, BTCS 7.41×10−37.41\times10^{-3}, CN 3.12×10−33.12\times10^{-3}, Rannacher 3.15×10−33.15\times10^{-3}, at 19601960, 38503850, 58105810 and 59995999 operations: at a stable step implicit methods only cost more.
  2. Pulse, r=10r = 10. FTCS reaches 5.05.0 and −4.0-4.0 after one step and is flagged BLEW UP at step 77 (step 44 at r=100r = 100). At step 33: BTCS 0.04520.0452, CN 0.12460.1246, Rannacher 0.00530.0053.
  3. Pulse, r=100r = 100. The numbers of the ringing and Rannacher sections.
  4. Smooth bump, r=10r = 10, ten steps. CN beats BTCS: 2.24×10−42.24\times10^{-4} against 7.56×10−37.56\times10^{-3}, with Rannacher at 1.40×10−41.40\times10^{-4}. At r=100r = 100, one step, even the bump rings under CN: minimum −0.1247-0.1247, error 0.36590.3659, against BTCS 0.09430.0943 and Rannacher 0.04370.0437.
  5. The cost line. At r=100r = 100 FTCS would need 200200 sub-steps (39,20039{,}200 operations) to cross one step, against 581581 for CN, though the sub-steps would resolve the physics better.

Computing it

🐍 PythonLab: accuracy against cost for one mode, and the top-mode factors
⌘/Ctrl + Enter

The output reproduces the cost-benefit list (1.79×10−31.79\times10^{-3} at 1960019600, 0.03270.0327 at 30803080, 3.44×10−43.44\times10^{-4} at 46484648) and the top-mode factors 0.00250.0025 and −0.9900-0.9900.

🧪 Coding exerciseExercise: the Thomas algorithm and Crank–Nicolson, with a convergence check
⌘/Ctrl + Enter

With N=20N = 20, k=3k = 3, T=0.02T = 0.02 the solution gives errors 7.75×10−47.75\times10^{-4}, 1.93×10−41.93\times10^{-4}, 4.83×10−54.83\times10^{-5} for 1010, 2020, 4040 steps (ratios 4.0074.007, 4.0024.002).

Concept checks

✅ Concept check

On a fine grid at $r = 100$, the highest mode has $\sin^2(\theta/2) \approx 1$. What factor per step does BTCS apply to it? (Use $1/(1+4r)$.)

✅ Concept check

CN is stable for every $r$, yet a sharp pulse rings at $r = 100$. What is the best explanation?

✅ Concept check

How many arithmetic operations does the Thomas algorithm use for $n = 100$ unknowns, counting $5$ per forward row, $1$ for the last back-substitution and $3$ for each other back-substitution row?

✅ Concept check

Halving $\Delta t$ reduces a scheme's error at fixed final time by a factor of about $4$. What is its order in time?

Problems

✏️ Pen & paperFactors on a three-node grid●○○

Take n=3n = 3 interior nodes (h=1/4h = 1/4). For the highest mode k=3k = 3 at r=2r = 2, find the FTCS, BTCS and CN factors.

Show worked solution

sin⁡2(3π/8)=0.85355\sin^2(3\pi/8) = 0.85355. FTCS: 1−4(2)(0.85355)=−5.8281 - 4(2)(0.85355) = -5.828 (unstable). BTCS: 1/(1+6.828)=0.12771/(1 + 6.828) = 0.1277. CN: (1−3.414)/(1+3.414)=−0.5469(1 - 3.414)/(1 + 3.414) = -0.5469: bounded, negative, well short of −1-1 on this coarse grid.

✏️ Pen & paperWhich modes does CN turn negative?●●○

On the 49-node rod (h=1/50h = 1/50) at r=10r = 10, for which kk is GCN<0G_{\mathrm{CN}} \lt 0?

Show worked solution

G<0G \lt 0 exactly when 2rsin⁡2(θ/2)>12r\sin^2(\theta/2) \gt 1, i.e. sin⁡2(kπ/100)>1/20=0.05\sin^2(k\pi/100) \gt 1/20 = 0.05, i.e. sin⁡(kπ/100)>0.2236\sin(k\pi/100) \gt 0.2236. So kπ/100>0.2255k\pi/100 \gt 0.2255, k>7.18k \gt 7.18: modes k=8,…,49k = 8, \dots, 49. At r=100r = 100 the same steps give k≥3k \ge 3, matching the table.

✏️ Pen & paperThomas by hand●●○

Solve 3x1−x2=13x_1 - x_2 = 1, −x1+3x2−x3=2-x_1 + 3x_2 - x_3 = 2, −x2+3x3=3-x_2 + 3x_3 = 3 with the Thomas algorithm, and give the operation count.

Show worked solution

Forward: w2=−1/3w_2 = -1/3, b2′=3−13=83b_2' = 3 - \tfrac13 = \tfrac83, d2′=2+13=73d_2' = 2 + \tfrac13 = \tfrac73. Then w3=−38w_3 = -\tfrac38, b3′=3−38=218b_3' = 3 - \tfrac38 = \tfrac{21}8, d3′=3+78=318d_3' = 3 + \tfrac78 = \tfrac{31}8. Back: x3=31/21x_3 = 31/21, x2=(73+3121)/83=10/7x_2 = (\tfrac73 + \tfrac{31}{21})/\tfrac83 = 10/7, x1=(1+107)/3=17/21x_1 = (1 + \tfrac{10}7)/3 = 17/21. Row two checks: −1721+9021−3121=2-\tfrac{17}{21} + \tfrac{90}{21} - \tfrac{31}{21} = 2. Operations: 8n−7=178n - 7 = 17.

Key Takeaways

  • BTCS: (I−rL)un+1=un(I - rL)\mathbf u^{n+1} = \mathbf u^n, G=1/(1+4rsin⁡2(θ/2))G = 1/(1 + 4r\sin^2(\theta/2)), in (0,1](0, 1] for every rr. It never undershoots; first order in time.
  • CN is the trapezoid rule: G=(1−2rsin⁡2)/(1+2rsin⁡2)G = (1 - 2r\sin^2)/(1 + 2r\sin^2). Stable for every rr, second order (local error −z3/12-z^3/12); halving Δt\Delta t gave ratios 4.054.05, 4.014.01, 4.004.00.
  • CN’s factor tends to −1-1 at the top of the spectrum: at r=100r = 100 one step on the pulse gives minimum −0.1516-0.1516 and error 0.41560.4156.
  • A Rannacher start (two BTCS half-steps, then CN) gives error 0.05250.0525 at step 11 and 4.05×10−44.05\times10^{-4} at step 1010 on that pulse, for about 3%3\% extra work.
  • The system is tridiagonal and diagonally dominant: Thomas solves it in 8n−78n - 7 operations without pivoting.
  • ADI: tridiagonal solves along rows, then columns, about 2323 operations per cell at M=24M = 24; its factor is a product of two CN factors.
  • One solve per step buys any Δt\Delta t when accuracy sets the step: on the smooth mode CN is 5×5\times more accurate than FTCS with 4.2×4.2\times 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.
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: