Flow Lab

Syllabus / Module 4: Numerical Methods for ODEs — The Theory

Lesson 4.5

Stability Regions & Stiffness

Absolute stability regions in the complex plane, A-stability, stiff equations, and why implicit methods win for stiff problems; Newton's method in implicit steps.

Written byClaude Sonnet

🌊
Why this matters for simulation: Viscous terms on fine grids make fluid equations stiff — the reason for implicit diffusion solves.

By the end of this lesson you can…

  • Compute the stability function R(z) of forward Euler, Heun, RK4, backward Euler and the trapezoid rule, and read the real and imaginary stability limits from the region where |R(z)| is at most 1.
  • State A-stability and L-stability, classify each method, and explain why no explicit Runge–Kutta method is A-stable.
  • Define stiffness operationally and compute a stiffness ratio from the eigenvalues of the Jacobian.
  • Show on a 2×2 system why an explicit step is set by the fastest mode long after it has decayed, while an implicit step follows the slow mode.
  • Describe the cost of an implicit step (Newton iteration, Jacobian reuse), write down BDF1 and BDF2, and compare RK45, BDF, Radau and LSODA on Robertson's problem.
  • Explain why A-stability does not buy accuracy when the step is large.
On this page
·
  1. The stability function and its region
  2. A-stability and L-stability
  3. What stiffness is
  4. The price of an implicit step
  5. BDF: backward differentiation formulas
  6. The solvers: Radau, BDF, LSODA
  7. Stable is not accurate
  8. Exercise: the RK4 stability boundary
  9. Problems
  10. What comes next
  11. Key Takeaways

4.3 Runge–Kutta Methods & Butcher Tableaux ended on a limit, 4.4 Adaptive Step Size & RK45 on a failure: RK45 spent 912 steps on a smooth solution of y′=−1000 (y−cos⁡t)y' = -1000\,(y - \cos t) while Radau needed 15. A fluid code shows the same thing: a viscous term on a fine grid forces a tiny step however gently the flow evolves. This lesson draws the whole picture, in the plane where the product z=hλz = h\lambda lives, and then asks what to do about it.

▶ Video Stability regions in the complex z-plane for Euler, Heun, RK4, backward Euler and the trapezoid rule; A- and L-stability; a stiff 2×2 system explicit against implicit; Robertson's problemcaptions only
Transcript
  1. Step y prime equals lambda y once and the method multiplies by R of z, where z is h times lambda, an eigenvalue of the Jacobian: real part decay, imaginary part oscillation. Stable means the size of R is at most 1. Forward Euler: 1 plus z. Backward Euler: 1 over 1 minus z. Heun and RK4: Taylor polynomials.
  2. Plot where the size of R is at most 1, on a grid. Forward Euler: a disc of radius 1 centred at minus 1. Backward Euler: everything outside a disc centred at plus 1. The trapezoid: exactly the left half-plane. Against these shapes, 20000 random points gave 0 mismatches each.
  3. Explicit methods give bounded regions. Along the negative real axis RK4 is stable out to 2.7853, and along the imaginary axis to 2.8284, the square root of 8. Euler and Heun reach 2 on the real axis, and touch the imaginary axis only at 0.
  4. Why can no explicit method contain the left half-plane? Its R is a polynomial, so the size of R grows without bound: at z equals minus 100, forward Euler gives -99, RK4 4004901. Backward Euler gives 0.0099: A-stable and L-stable, since R goes to 0. The trapezoid gives minus 0.9608: A-stable only.
  5. Stiffness: stability, not accuracy, sets the step. This system has eigenvalues minus 1 and minus 1000: ratio 1000. By t equals 0.01 the fast mode is down to 4.5 times ten to the minus 5. What remains is a smooth half e to the minus t.
  6. Yet forward Euler still multiplies that dead mode by R of minus 1000 h each step. At h equals 0.0019 that is minus 0.9: error 1.87 times ten to the minus 5. At 0.0020 it is minus 1: the error stays 0.5. At 0.0021 it is minus 1.1: error 1.8 times ten to the 98. RK4 does the same past 2.7853 over 1000.
  7. Backward Euler follows the slow mode. At h equals 0.25 it takes 20 steps instead of 2632, with error 0.0024. R at z equals minus 250 is 0.00398: the fast mode is gone after one step.
  8. Stable is not accurate. The trapezoid has R equal to minus 0.98413 there: the fast mode rings, error 0.363. On the slow mode it is closer, 0.7778 against 0.8, exact 0.7788. At h equals 0.05 it wins: 1.71 times ten to the minus 4 against 4.33 times ten to the minus 4.
  9. Fluids hit this. Diffusion on 63 grid points has stiffness ratio 1659.4; on 127 points, 6639.5, and forward Euler needs h below 0.003052. At a frame step of one sixtieth the fastest mode has z equal to minus 10.921: forward Euler multiplies by minus 9.921, backward Euler by 0.08389, the trapezoid by minus 0.6904.
  10. Backward differentiation formulas build on backward Euler, which is order 1. For order 2 the boundary locus has real part 1 minus cosine t, squared, never negative: A-stable. Orders 3 to 6 are stable only inside a wedge about the negative real axis, of 86.03, 73.35, 51.84 and 17.84 degrees.
  11. Robertson's chemical kinetics, from 0 to 40. RK45 takes 34537 steps. BDF takes 144, Radau 78, LSODA 200. BDF factorised its matrix only 33 times in 144 steps, reusing the Jacobian.
  12. Why does RK45 need so many steps? At the end state the Jacobian has an eigenvalue of minus 3392.8, so the stability limit is 3.3066 over 3392.8: 9.75 times ten to the minus 4. The last step is 7.92 times ten to the minus 4. After t equals 0.01 every step lies between 0.81 and 1.13 times its limit.
  13. Recap: a step is stable when z lies where the size of R is at most 1. Explicit regions are bounded. Backward Euler is A-stable and L-stable. Stiffness forces explicit steps down to the limit. Next: multistep methods, then symplectic ones.

The stability function and its region

Apply a one-step method to y′=λyy' = \lambda y (4.2 The Euler Family: Forward, Backward, Heun & Midpoint): yn+1=R(z) yny_{n+1} = R(z)\,y_n with z=hλz = h\lambda. Now let λ\lambda be complex. For a real system y′=Jy\mathbf y' = J\mathbf y the eigenvalues of JJ come in pairs a±iba \pm ib (1.7 Complex Eigenvalues & Rotation): aa is a decay rate, bb an oscillation rate. Along each eigenvector the system is a scalar equation y′=λyy' = \lambda y (1.5 Eigenvectors & Eigenvalues, 1.6 Change of Basis & Diagonalization), so the method is stable on the system exactly when every zk=hλkz_k = h\lambda_k is in the region of absolute stability

S={ z∈C:∣R(z)∣≤1 }.\mathcal S = \{\, z \in \mathbb C : \lvert R(z)\rvert \le 1 \,\}.

For a nonlinear y′=f(y)\mathbf y' = \mathbf f(\mathbf y) we use the Jacobian JJ at the current state as a heuristic (from memory, not a theorem). Block A scans the axes of S\mathcal S for six methods:

methodR(z)R(z)stable out to (negative real axis)stable out to (imaginary axis)
forward Euler1+z1 + z2200
Heun1+z+z221 + z + \tfrac{z^2}{2}2200
Kutta RK3∑k≤3zk/k!\sum_{k\le3} z^k/k!2.51272.51271.73211.7321
RK4∑k≤4zk/k!\sum_{k\le4} z^k/k!2.78532.78532.82842.8284
backward Euler11−z\dfrac{1}{1 - z}no limitno limit
trapezoid1+z/21−z/2\dfrac{1 + z/2}{1 - z/2}no limitno limit

These are the numbers of the earlier lessons. "00" means unstable at every point off the origin: for Heun ∣R(iy)∣2=1+y4/4>1\lvert R(iy)\rvert^2 = 1 + y^4/4 \gt 1, and for RK4 ∣R(iy)∣2=1−y672+y8576=1+y6576(y2−8)\lvert R(iy)\rvert^2 = 1 - \tfrac{y^6}{72} + \tfrac{y^8}{576} = 1 + \tfrac{y^6}{576}(y^2 - 8), which is at most 11 exactly when y2≤8y^2 \le 8: the limit 8=2.8284\sqrt8 = 2.8284 (block B prints the coefficients).

Three regions are exact shapes, not pictures:

  • Forward Euler. ∣1+z∣≤1\lvert 1 + z\rvert \le 1 is the closed disc of radius 1 centred at −1-1; the boundary is z=−1+eiθz = -1 + e^{i\theta}.
  • Backward Euler. ∣1−z∣≥1\lvert 1 - z\rvert \ge 1 is the outside of the disc of radius 1 centred at +1+1. The unstable part is the disc, in the right half-plane; the left half-plane is entirely stable.
  • Trapezoid. ∣1+z/2∣2−∣1−z/2∣2=2 Re z\lvert 1 + z/2\rvert^2 - \lvert 1 - z/2\rvert^2 = 2\,\mathrm{Re}\,z, so ∣R∣≤1\lvert R\rvert \le 1 exactly when Re z≤0\mathrm{Re}\,z \le 0: the left half-plane, nothing more and nothing less.

Block C tests all three on 2000020000 random points (00 mismatches each) and finds ∣R∣=1\lvert R\rvert = 1 on the two circles to 2×10−162\times10^{-16}.

A-stability and L-stability

A method is A-stable when S\mathcal S contains the whole left half-plane: any decaying linear system is stepped stably for every hh. It is L-stable if also R(z)→0R(z) \to 0 as z→−∞z \to -\infty: infinitely fast modes are killed in one step. Block D evaluates R(−100)R(-100) to compare:

forward EulerRK4trapezoidbackward Euler
R(−100)R(-100)−99-9940049014004901−0.9608-0.96080.00990.0099
verdictnot A-stablenot A-stableA-stable, not L-stableA- and L-stable

Why no explicit Runge–Kutta method is A-stable. For an explicit method AA is strictly lower triangular, so (I−zA)−1=I+zA+z2A2+⋯(I - zA)^{-1} = I + zA + z^2A^2 + \cdots stops after ss terms and R(z)=1+z bT(I−zA)−11R(z) = 1 + z\,b^{\mathsf T}(I - zA)^{-1}\mathbf 1 is a polynomial. Its linear coefficient is bT1=1≠0b^{\mathsf T}\mathbf 1 = 1 \ne 0, so it is not constant, and a nonconstant polynomial has ∣R∣→∞\lvert R\rvert \to \infty in every direction: S\mathcal S is bounded (RK4 gives 13.7083,291,400490113.7083, 291, 4004901 at z=−5,−10,−100z = -5, -10, -100). Implicit methods invert (I−zA)(I - zA), which is rational, and rational functions can decay. (From memory, taken up properly in 4.6 Multistep Methods: the second Dahlquist barrier says no A-stable multistep method has order above 22.)

What stiffness is

Define it by what it does: a problem is stiff on an interval when the step that keeps a method stable is far smaller than the step that accuracy needs. Fast and slow scales sit in the Jacobian: with eigenvalues λk\lambda_k the stiffness ratio is

max⁡k∣Re λk∣min⁡k∣Re λk∣,\frac{\max_k \lvert\mathrm{Re}\,\lambda_k\rvert}{\min_k \lvert\mathrm{Re}\,\lambda_k\rvert},

large when decay rates are spread over many orders. The ratio is a symptom: what matters is that the fast modes have already decayed while the method must still resolve them in stability.

A 2×2 system. Take A=(−500.5499.5499.5−500.5)A = \begin{pmatrix} -500.5 & 499.5 \\ 499.5 & -500.5 \end{pmatrix}, y′=Ay\mathbf y' = A\mathbf y, y(0)=(1,0)\mathbf y(0) = (1, 0). Block F finds eigenvalues −1-1 and −1000-1000; the eigenvectors are (1,1)(1,1) and (1,−1)(1,-1) (1.5 Eigenvectors & Eigenvalues), and (1,0)=12(1,1)+12(1,−1)(1,0) = \tfrac12(1,1) + \tfrac12(1,-1), so

y1=12(e−t+e−1000t),y2=12(e−t−e−1000t).y_1 = \tfrac12\big(e^{-t} + e^{-1000t}\big), \qquad y_2 = \tfrac12\big(e^{-t} - e^{-1000t}\big).

The stiffness ratio is 10001000. At t=0.01t = 0.01 the fast mode is e−10=4.5×10−5e^{-10} = 4.5\times10^{-5}: invisible. Block F steps to t=5t = 5:

methodhhstepsmax ∣y∣\lvert y\rverterror at t=5t = 5
forward Euler0.00190.001926322632111.87×10−51.87\times10^{-5}
forward Euler0.00200.002025002500110.50.5
forward Euler0.00210.0021238123811.8×10981.8\times10^{98}1.8×10981.8\times10^{98}
RK40.00270.002718521852111.35×10−61.35\times10^{-6}
RK40.00280.0028178617867.6×10167.6\times10^{16}7.6×10167.6\times10^{16}
backward Euler0.250.252020110.00240.0024
backward Euler0.050.05100100114.3×10−44.3\times10^{-4}

The mechanism is in the table’s thresholds. The fast mode has amplitude 12\tfrac12 at t=0t = 0 and the method multiplies it by R(−1000h)R(-1000h) per step. Forward Euler: 2/1000=0.0022/1000 = 0.002; at h=0.0021h = 0.0021, R=−1.1R = -1.1 and 0.5⋅1.12381≈1.8×10980.5\cdot1.1^{2381} \approx 1.8\times10^{98} (block F). At h=0.002h = 0.002, R=−1R = -1 and the dead mode never dies: the error stays 0.50.5. RK4 turns at 2.7853/1000=0.00278532.7853/1000 = 0.0027853. The smooth solution would be fine with h=0.25h = 0.25; the ratio of steps, 26322632 to 2020, is a price paid for modes that are not there. Backward Euler’s R(−250)=0.00398R(-250) = 0.00398 at h=0.25h = 0.25 removes the fast mode instantly.

The price of an implicit step

Backward Euler needs w=yn+h f(tn+1,w)\mathbf w = \mathbf y_n + h\,\mathbf f(t_{n+1}, \mathbf w). Newton’s method (4.2 The Euler Family: Forward, Backward, Heun & Midpoint) on G(w)=w−yn−hf(tn+1,w)\mathbf G(\mathbf w) = \mathbf w - \mathbf y_n - h\mathbf f(t_{n+1},\mathbf w) solves, per iteration, a linear system with the matrix I−hJI - hJ. On a linear problem one iteration is exact: that is the 2×2 solve behind the table. On a large nonlinear problem the cost per step is a few evaluations of f\mathbf f, a factorization of I−hJI - hJ (O(n3)O(n^3) dense, far less if JJ is sparse), and the triangular solves. Production codes therefore reuse the Jacobian and its factorization over several steps (a “simplified Newton” iteration), refreshing only when convergence slows or hh changes a lot. Block H counts this.

BDF: backward differentiation formulas

A BDF method of order kk differentiates the polynomial through the last k+1k+1 points and sets its slope at tn+1t_{n+1} equal to fn+1f_{n+1}. For k=1k = 1 that is backward Euler. For k=2k = 2 the quadratic through yn−1,yn,yn+1y_{n-1}, y_n, y_{n+1} has slope (3yn+1−4yn+yn−1)/(2h)(3y_{n+1} - 4y_n + y_{n-1})/(2h) at tn+1t_{n+1}:

32 yn+1−2 yn+12 yn−1=h f(tn+1,yn+1).\tfrac32\, y_{n+1} - 2\,y_n + \tfrac12\, y_{n-1} = h\, f(t_{n+1}, y_{n+1}).

On y′=λyy' = \lambda y this is (32−z)ξ2−2ξ+12=0(\tfrac32 - z)\xi^2 - 2\xi + \tfrac12 = 0 for the growth factor ξ\xi per step; stability needs both roots inside the unit circle. Putting ξ=eiθ\xi = e^{i\theta} on the boundary gives the curve z=32−2e−iθ+12e−2iθz = \tfrac32 - 2e^{-i\theta} + \tfrac12 e^{-2i\theta}, whose real part is (1−cos⁡θ)2≥0(1 - \cos\theta)^2 \ge 0 (block E confirms to 4×10−164\times10^{-16}). The curve never enters the left half-plane, and the stable region is its outside: BDF2 is A-stable. Block E also finds no violation among 99339933 random left-half-plane points, and the root radius at z=−1,−100,−106z = -1, -100, -10^6 is 0.4472,0.0702,0.00070.4472, 0.0702, 0.0007: it tends to 00, so BDF2 is L-stable too.

Higher orders pay. Block E scans the boundary locus of BDF1..6 for the widest wedge around the negative real axis that stays stable (A(α)A(\alpha)-stability): α=90°,90°,86.03°,73.35°,51.84°,17.84°\alpha = 90°, 90°, 86.03°, 73.35°, 51.84°, 17.84°. Orders 33 to 66 are not A-stable but still cover almost all of the left half-plane away from the imaginary axis. That BDF7 and above are unusable (not zero-stable) is from memory and not checked here.

The solvers: Radau, BDF, LSODA

solve_ivp offers 'BDF' (variable order 11 to 55 in scipy, from its documentation), 'Radau' (a fifth-order implicit Runge–Kutta of the Radau IIA family: A- and L-stable, from memory) and 'LSODA' (switches between a non-stiff Adams method and BDF by itself, from its documentation). All three take an optional Jacobian jac=. Robertson’s chemical kinetics problem is the standard test:

y1′=−0.04 y1+104y2y3,y2′=0.04 y1−104y2y3−3×107y22,y3′=3×107y22,y_1' = -0.04\,y_1 + 10^4 y_2 y_3, \quad y_2' = 0.04\,y_1 - 10^4 y_2 y_3 - 3\times10^7 y_2^2, \quad y_3' = 3\times10^7 y_2^2,

y(0)=(1,0,0)\mathbf y(0) = (1, 0, 0). Rates span nine orders of magnitude. Block H runs [0,40][0, 40] with rtol=10−6\text{rtol} = 10^{-6}, atol=10−10\text{atol} = 10^{-10} and the analytic Jacobian:

methodstepsnfevnjevLU factorizations
RK453453734537242066242066––
BDF144144366366443333
Radau78786476471818100100
LSODA20020033033028282828

The four answers for y(40)y(40) agree to within 7×10−77\times10^{-7} in y1y_1 and y3y_3 and to 10−510^{-5} relative in y2y_2 (block H prints them). RK45 takes 34537/144=24034537/144 = 240 times as many steps as BDF. At the end state y2≈9×10−6y_2 \approx 9\times10^{-6} the Jacobian has an eigenvalue −3392.8-3392.8, and the stability limit 3.3066/3392.8=9.75×10−43.3066/3392.8 = 9.75\times10^{-4} is close to the last RK45 step, 7.9×10−47.9\times10^{-4}: accuracy is not what sets that step. BDF refactorized only 3333 times in 144144 steps (44 Jacobians): Jacobian reuse at work. Radau is costlier per step (three stages) but takes only 7878.

Stable is not accurate

An A-stable method guarantees only that the answer does not blow up. In the 2×2 table at h=0.25h = 0.25 both implicit methods are stable, yet the trapezoid error at t=5t = 5 is 0.3630.363, against 0.00240.0024 for backward Euler. The fast mode has z=−250z = -250, where Rtrap=−0.98413R_\text{trap} = -0.98413 and RBE=0.00398R_\text{BE} = 0.00398: the trapezoid rings, flipping the sign of a mode that should have vanished. On the slow mode (z=−0.25z = -0.25) the roles reverse: Rtrap=0.7778R_\text{trap} = 0.7778 and RBE=0.8R_\text{BE} = 0.8 against e−0.25=0.7788e^{-0.25} = 0.7788. At h=0.05h = 0.05 the trapezoid’s error falls to 1.7×10−41.7\times10^{-4}, below backward Euler’s 4.3×10−44.3\times10^{-4}. Stability fixes whether the step is allowed; accuracy still fixes what the step costs. This is why stiff codes favour L-stable or strongly damped methods (BDF, Radau) and why the damped but first-order backward Euler is often good enough for fluids.

◆ Interactive Drag z = hλ around the complex plane; then solve the stiff 2×2 system explicit against implicit

Loading simulation…

Things to try (a headless run reproduced each of these):

  1. RK4, h=1h = 1, λ=−2.7\lambda = -2.7 then −2.9-2.9: ∣R∣=0.8788\lvert R\rvert = 0.8788, then 1.18721.1872 (unstable). On the imaginary axis 2.8i2.8i and 2.9i2.9i: 0.93070.9307 and 1.19311.1931. The readout scans the axes and prints 2.78532.7853 and 2.82842.8284.
  2. Pick Backward Euler and sweep the dot: the unstable region is the disc around z=1z = 1; the whole left half-plane is shaded. Pick Trapezoid: the left half-plane exactly.
  3. Switch to the stiff 2×2 mode with Forward Euler against Backward Euler. At log⁡10h=−2.7\log_{10}h = -2.7 the forward run is stable (25062506 steps, error 2.0×10−52.0\times10^{-5}); at −2.65-2.65 it overflows. Set log⁡10h=−0.6\log_{10}h = -0.6 (2020 steps): backward Euler error 2.4×10−32.4\times10^{-3}. Compare with Trapezoid: 0.3630.363.
✅ Concept check

Why can no explicit Runge–Kutta method be A-stable?

✅ Concept check

A Jacobian has eigenvalues -0.5, -20 and -3000. RK4 uses the real limit 2.7853. How many equal steps does RK4 need at minimum to reach t = 3?

✅ Concept check

Which statement best defines a stiff problem?

Exercise: the RK4 stability boundary

Build RR by stepping, as the sim does, then walk outward from 00 along a ray at angle θ\theta to the first point with ∣R∣>1\lvert R\rvert \gt 1, refining by bisection. The tests check the real axis, imaginary axis and two rays in between.

🧪 Coding exerciseExercise: where |R| = 1 along a ray, for RK4
⌘/Ctrl + Enter

The sweep prints radius 00 for 0°0° to 75°75° (the right half-plane is unstable: R≈1+zR \approx 1 + z), then 2.82842.8284 at 90°90°, 2.8872.887 at 105°105° (the region bulges past the imaginary intercept), 2.62252.6225 at 120°120°, 2.70442.7044 at 135°135°, 2.842.84 at 150°150° and 2.78532.7853 at 180°180°.

🐍 PythonIntercepts, exact shapes, A- and L-stability, BDF, the stiff 2×2, diffusion, Robertson (blocks A to H)
⌘/Ctrl + Enter

Problems

✏️ Pen & paperA damped spring and three methods●○○

A linearised structural mode has x′=vx' = v, v′=−1600 x−20 vv' = -1600\,x - 20\,v, so λ=−10±38.73i\lambda = -10 \pm 38.73i (block G prints λ\lambda and the numbers below).

  1. Show that forward Euler is stable iff h≤20/1600h \le 20/1600, and find the limit.
  2. At h=0.1h = 0.1, z=−1+3.873iz = -1 + 3.873i. Compute ∣R∣\lvert R\rvert for backward Euler and the trapezoid, and compare with the exact ∣ez∣\lvert e^z\rvert.
  3. Which of the two misrepresents the decay of the oscillation more, and in which direction?
Show worked solution
  1. ∣1+hλ∣2=(1−10h)2+(38.73h)2=1−20h+1600h2\lvert 1 + h\lambda\rvert^2 = (1 - 10h)^2 + (38.73h)^2 = 1 - 20h + 1600h^2 (since ∣λ∣2=1600\lvert\lambda\rvert^2 = 1600). This is at most 11 iff h(1600h−20)≤0h(1600h - 20) \le 0, so h≤0.0125h \le 0.0125, where ∣1+z∣=1.0000\lvert 1 + z\rvert = 1.0000.
  2. Backward Euler: ∣1−z∣=∣2−3.873i∣=19=4.359\lvert 1 - z\rvert = \lvert 2 - 3.873i\rvert = \sqrt{19} = 4.359, so ∣R∣=0.2294\lvert R\rvert = 0.2294. Trapezoid: ∣1+z/2∣=∣0.5+1.9365i∣=2\lvert 1 + z/2\rvert = \lvert 0.5 + 1.9365i\rvert = 2, ∣1−z/2∣=6=2.4495\lvert 1 - z/2\rvert = \sqrt6 = 2.4495, so ∣R∣=0.8165\lvert R\rvert = 0.8165. Exact: e−1=0.3679e^{-1} = 0.3679.
  3. Backward Euler damps too strongly (0.2290.229 against 0.3680.368 per step); the trapezoid too weakly (0.81650.8165). Both are stable at a step 88 times beyond forward Euler’s limit, and neither is accurate. (Block G adds that RK4’s limit along this ray is h<0.0724h \lt 0.0724.)
✏️ Pen & paperThe theta method: where does A-stability start?●●○

The theta method is yn+1=yn+h[(1−θ)fn+θfn+1]y_{n+1} = y_n + h\big[(1 - \theta)f_n + \theta f_{n+1}\big], 0≤θ≤10 \le \theta \le 1 (θ=0\theta = 0 forward Euler, 12\tfrac12 trapezoid, 11 backward Euler).

  1. Show R(z)=1+(1−θ)z1−θzR(z) = \dfrac{1 + (1-\theta)z}{1 - \theta z}.
  2. Show that ∣R(iy)∣≤1\lvert R(iy)\rvert \le 1 for all yy iff θ≥12\theta \ge \tfrac12.
  3. Compute R(−∞)R(-\infty), and R(−100)R(-100) for θ=34\theta = \tfrac34.
  4. What is the smallest θ\theta with ∣R(−∞)∣≤0.2\lvert R(-\infty)\rvert \le 0.2? Compare R−ezR - e^z at order z2z^2 to say which θ\theta is second order.
Show worked solution
  1. With f=λyf = \lambda y: yn+1(1−θz)=yn(1+(1−θ)z)y_{n+1}(1 - \theta z) = y_n(1 + (1-\theta)z).
  2. ∣1+(1−θ)iy∣2=1+(1−θ)2y2\lvert 1 + (1-\theta)iy\rvert^2 = 1 + (1-\theta)^2y^2 and ∣1−θiy∣2=1+θ2y2\lvert 1 - \theta iy\rvert^2 = 1 + \theta^2y^2, so ∣R∣≤1  ⟺  (1−θ)2≤θ2  ⟺  θ≥12\lvert R\rvert \le 1 \iff (1-\theta)^2 \le \theta^2 \iff \theta \ge \tfrac12. (The pole 1/θ1/\theta lies in the right half-plane, so for θ≥12\theta \ge \tfrac12 the region contains the left half-plane.)
  3. R(−∞)=−(1−θ)/θR(-\infty) = -(1-\theta)/\theta: −1-1 at 12\tfrac12, −13-\tfrac13 at 34\tfrac34. R(−100)=(1−25)/(1+75)=−0.3158R(-100) = (1 - 25)/(1 + 75) = -0.3158.
  4. (1−θ)/θ≤0.2  ⟺  θ≥56(1-\theta)/\theta \le 0.2 \iff \theta \ge \tfrac56. Expanding, R=1+z+θz2+⋯R = 1 + z + \theta z^2 + \cdots against ez=1+z+12z2e^z = 1 + z + \tfrac12 z^2: second order only for θ=12\theta = \tfrac12. L-stability (θ=1\theta = 1) costs one order.
✏️ Pen & paperA finer diffusion grid●●●

Diffusion with ν=0.01\nu = 0.01 on (0,1)(0,1) with 127127 interior points has eigenvalues −4νΔx2sin⁡2 ⁣(kπΔx/2)-\tfrac{4\nu}{\Delta x^2}\sin^2\!\big(k\pi\Delta x/2\big), k=1,…,127k = 1, \dots, 127, Δx=1/128\Delta x = 1/128 (block G).

  1. Find the extreme eigenvalues, the stiffness ratio, and the forward Euler limit.
  2. How many forward Euler steps reach t=1t = 1? What does the grid refinement from 6363 points to 127127 do to the step limit?
  3. At a frame step h=1/60h = 1/60, find RR on the fastest mode for forward Euler, backward Euler and the trapezoid. Which would you pick for diffusion, and why?
Show worked solution
  1. λmin≈−νπ2=−0.0987\lambda_\text{min} \approx -\nu\pi^2 = -0.0987 (k=1k = 1) and λmax=−655.26\lambda_\text{max} = -655.26 (k=127k = 127): ratio 6639.56639.5. Forward Euler needs h<2/655.26=0.003052h \lt 2/655.26 = 0.003052.
  2. 1/0.003052=327.61/0.003052 = 327.6, so 328328 steps. The limit fell from 0.0122140.012214 to 0.0030520.003052, about 44 times, because λmax∝1/Δx2\lambda_\text{max} \propto 1/\Delta x^2 and Δx\Delta x halved.
  3. z=−655.26/60=−10.921z = -655.26/60 = -10.921: forward R=−9.921R = -9.921 (blow-up), backward 0.083890.08389, trapezoid (1+z/2)/(1−z/2)=−4.4605/6.4605=−0.6904(1 + z/2)/(1 - z/2) = -4.4605/6.4605 = -0.6904. The trapezoid does not blow up but flips the sign of the sharpest mode each frame; backward Euler damps it. Backward Euler is the usual choice for a diffusion solve in a fluid code.

What comes next

4.6 Multistep Methods builds Adams and BDF families in full (BDF2’s zero-stability root condition was used here without proof) and previews IMEX. 4.7 Energy & Symplectic Integrators asks for something stability does not give: energy that stays bounded for millions of steps.

Key Takeaways

  • Applying a method to y′=λyy' = \lambda y gives yn+1=R(z)yny_{n+1} = R(z)y_n; the stability region is {z:∣R(z)∣≤1}\{z : \lvert R(z)\rvert \le 1\} in the complex plane, z=hλz = h\lambda, with λ\lambda the Jacobian eigenvalues.
  • Forward Euler’s region is the disc ∣z+1∣≤1\lvert z + 1\rvert \le 1; backward Euler’s is the outside of ∣z−1∣<1\lvert z - 1\rvert \lt 1; the trapezoid’s is exactly Re z≤0\mathrm{Re}\,z \le 0. RK4 reaches 2.78532.7853 on the negative real axis and 2.82842.8284 on the imaginary axis.
  • A-stable means the region contains the left half-plane; L-stable adds R→0R \to 0 at −∞-\infty. Backward Euler and BDF2 are both; the trapezoid is A-stable only (R→−1R \to -1).
  • Explicit RK methods have polynomial RR, so they cannot be A-stable.
  • Stiff: the stable step is far smaller than the accurate one; the stiffness ratio max⁡∣Re λ∣/min⁡∣Re λ∣\max\lvert\mathrm{Re}\,\lambda\rvert/\min\lvert\mathrm{Re}\,\lambda\rvert measures the spread (10001000 for the 2×2 example, 1659.41659.4 for diffusion on 6363 points).
  • Implicit steps cost a Newton iteration with I−hJI - hJ; solvers reuse the Jacobian. On Robertson on [0,40][0,40] BDF took 144144 steps, RK45 3453734537.
  • BDF1 and BDF2 are A-stable, BDF3 to BDF6 are A(α)A(\alpha)-stable with α=86.03°\alpha = 86.03° down to 17.84°17.84°.
  • A-stability does not buy accuracy: at h=0.25h = 0.25 the trapezoid rings and backward Euler over-damps.
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: