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 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 lives, and then asks what to do about it.
Transcript
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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 (4.2 The Euler Family: Forward, Backward, Heun & Midpoint): with . Now let be complex. For a real system the eigenvalues of come in pairs (1.7 Complex Eigenvalues & Rotation): is a decay rate, an oscillation rate. Along each eigenvector the system is a scalar equation (1.5 Eigenvectors & Eigenvalues, 1.6 Change of Basis & Diagonalization), so the method is stable on the system exactly when every is in the region of absolute stability
For a nonlinear we use the Jacobian at the current state as a heuristic (from memory, not a theorem). Block A scans the axes of for six methods:
| method | stable out to (negative real axis) | stable out to (imaginary axis) | |
|---|---|---|---|
| forward Euler | |||
| Heun | |||
| Kutta RK3 | |||
| RK4 | |||
| backward Euler | no limit | no limit | |
| trapezoid | no limit | no limit |
These are the numbers of the earlier lessons. "" means unstable at every point off the origin: for Heun , and for RK4 , which is at most exactly when : the limit (block B prints the coefficients).
Three regions are exact shapes, not pictures:
- Forward Euler. is the closed disc of radius 1 centred at ; the boundary is .
- Backward Euler. is the outside of the disc of radius 1 centred at . The unstable part is the disc, in the right half-plane; the left half-plane is entirely stable.
- Trapezoid. , so exactly when : the left half-plane, nothing more and nothing less.
Block C tests all three on random points ( mismatches each) and finds on the two circles to .
A-stability and L-stability
A method is A-stable when contains the whole left half-plane: any decaying linear system is stepped stably for every . It is L-stable if also as : infinitely fast modes are killed in one step. Block D evaluates to compare:
| forward Euler | RK4 | trapezoid | backward Euler | |
|---|---|---|---|---|
| verdict | not A-stable | not A-stable | A-stable, not L-stable | A- and L-stable |
Why no explicit Runge–Kutta method is A-stable. For an explicit method is strictly lower triangular, so stops after terms and is a polynomial. Its linear coefficient is , so it is not constant, and a nonconstant polynomial has in every direction: is bounded (RK4 gives at ). Implicit methods invert , 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 .)
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 the stiffness ratio is
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 , , . Block F finds eigenvalues and ; the eigenvectors are and (1.5 Eigenvectors & Eigenvalues), and , so
The stiffness ratio is . At the fast mode is : invisible. Block F steps to :
| method | steps | max | error at | |
|---|---|---|---|---|
| forward Euler | ||||
| forward Euler | ||||
| forward Euler | ||||
| RK4 | ||||
| RK4 | ||||
| backward Euler | ||||
| backward Euler |
The mechanism is in the table’s thresholds. The fast mode has amplitude at and the method multiplies it by per step. Forward Euler: ; at , and (block F). At , and the dead mode never dies: the error stays . RK4 turns at . The smooth solution would be fine with ; the ratio of steps, to , is a price paid for modes that are not there. Backward Euler’s at removes the fast mode instantly.
The price of an implicit step
Backward Euler needs . Newton’s method (4.2 The Euler Family: Forward, Backward, Heun & Midpoint) on solves, per iteration, a linear system with the matrix . 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 , a factorization of ( dense, far less if 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 changes a lot. Block H counts this.
BDF: backward differentiation formulas
A BDF method of order differentiates the polynomial through the last points and sets its slope at equal to . For that is backward Euler. For the quadratic through has slope at :
On this is for the growth factor per step; stability needs both roots inside the unit circle. Putting on the boundary gives the curve , whose real part is (block E confirms to ). 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 random left-half-plane points, and the root radius at is : it tends to , 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 (-stability): . Orders to 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 to 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:
. Rates span nine orders of magnitude. Block H runs with , and the analytic Jacobian:
| method | steps | nfev | njev | LU factorizations |
|---|---|---|---|---|
| RK45 | – | – | ||
| BDF | ||||
| Radau | ||||
| LSODA |
The four answers for agree to within in and and to relative in (block H prints them). RK45 takes times as many steps as BDF. At the end state the Jacobian has an eigenvalue , and the stability limit is close to the last RK45 step, : accuracy is not what sets that step. BDF refactorized only times in steps ( Jacobians): Jacobian reuse at work. Radau is costlier per step (three stages) but takes only .
Stable is not accurate
An A-stable method guarantees only that the answer does not blow up. In the 2×2 table at both implicit methods are stable, yet the trapezoid error at is , against for backward Euler. The fast mode has , where and : the trapezoid rings, flipping the sign of a mode that should have vanished. On the slow mode () the roles reverse: and against . At the trapezoid’s error falls to , below backward Euler’s . 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.
Things to try (a headless run reproduced each of these):
- RK4, , then : , then (unstable). On the imaginary axis and : and . The readout scans the axes and prints and .
- Pick Backward Euler and sweep the dot: the unstable region is the disc around ; the whole left half-plane is shaded. Pick Trapezoid: the left half-plane exactly.
- Switch to the stiff 2×2 mode with Forward Euler against Backward Euler. At the forward run is stable ( steps, error ); at it overflows. Set ( steps): backward Euler error . Compare with Trapezoid: .
Exercise: the RK4 stability boundary
Build by stepping, as the sim does, then walk outward from along a ray at angle to the first point with , refining by bisection. The tests check the real axis, imaginary axis and two rays in between.
The sweep prints radius for to (the right half-plane is unstable: ), then at , at (the region bulges past the imaginary intercept), at , at , at and at .
Problems
A linearised structural mode has , , so (block G prints and the numbers below).
- Show that forward Euler is stable iff , and find the limit.
- At , . Compute for backward Euler and the trapezoid, and compare with the exact .
- Which of the two misrepresents the decay of the oscillation more, and in which direction?
Show worked solution
- (since ). This is at most iff , so , where .
- Backward Euler: , so . Trapezoid: , , so . Exact: .
- Backward Euler damps too strongly ( against per step); the trapezoid too weakly (). Both are stable at a step times beyond forward Euler’s limit, and neither is accurate. (Block G adds that RK4’s limit along this ray is .)
The theta method is , ( forward Euler, trapezoid, backward Euler).
- Show .
- Show that for all iff .
- Compute , and for .
- What is the smallest with ? Compare at order to say which is second order.
Show worked solution
- With : .
- and , so . (The pole lies in the right half-plane, so for the region contains the left half-plane.)
- : at , at . .
- . Expanding, against : second order only for . L-stability () costs one order.
Diffusion with on with interior points has eigenvalues , , (block G).
- Find the extreme eigenvalues, the stiffness ratio, and the forward Euler limit.
- How many forward Euler steps reach ? What does the grid refinement from points to do to the step limit?
- At a frame step , find on the fastest mode for forward Euler, backward Euler and the trapezoid. Which would you pick for diffusion, and why?
Show worked solution
- () and (): ratio . Forward Euler needs .
- , so steps. The limit fell from to , about times, because and halved.
- : forward (blow-up), backward , trapezoid . 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 gives ; the stability region is in the complex plane, , with the Jacobian eigenvalues.
- Forward Euler’s region is the disc ; backward Euler’s is the outside of ; the trapezoid’s is exactly . RK4 reaches on the negative real axis and on the imaginary axis.
- A-stable means the region contains the left half-plane; L-stable adds at . Backward Euler and BDF2 are both; the trapezoid is A-stable only ().
- Explicit RK methods have polynomial , so they cannot be A-stable.
- Stiff: the stable step is far smaller than the accurate one; the stiffness ratio measures the spread ( for the 2×2 example, for diffusion on points).
- Implicit steps cost a Newton iteration with ; solvers reuse the Jacobian. On Robertson on BDF took steps, RK45 .
- BDF1 and BDF2 are A-stable, BDF3 to BDF6 are -stable with down to .
- A-stability does not buy accuracy: at the trapezoid rings and backward Euler over-damps.