ConceptComplete

Stability Theory for ODE Solvers

Stability determines whether numerical errors grow or decay during integration. For stiff problems, the stability region of the method -- not accuracy -- dictates the step size. The interplay between order, stability, and implementation defines the practical utility of each method.


Linear Stability Analysis

Definition7.7Stability Region

Apply a numerical method to the Dahlquist test equation yβ€²=Ξ»yy' = \lambda y with λ∈C\lambda \in \mathbb{C}, Re(Ξ»)≀0\mathrm{Re}(\lambda) \leq 0. The method produces yn+1=R(hΞ»)yny_{n+1} = R(h\lambda) y_n where R(z)R(z) is the stability function. The stability region is S={z∈C:∣R(z)βˆ£β‰€1}\mathcal{S} = \{z \in \mathbb{C} : |R(z)| \leq 1\}. A method is A-stable if SβŠ‡Cβˆ’={z:Re(z)≀0}\mathcal{S} \supseteq \mathbb{C}^- = \{z : \mathrm{Re}(z) \leq 0\}, meaning it is stable for all step sizes on all problems with decaying modes.

ExampleStability Regions of Common Methods
  • Forward Euler: R(z)=1+zR(z) = 1 + z, so S={z:∣1+zβˆ£β‰€1}\mathcal{S} = \{z : |1 + z| \leq 1\} (disc of radius 1 centered at βˆ’1-1).
  • Backward Euler: R(z)=1/(1βˆ’z)R(z) = 1/(1-z), A-stable (entire left half-plane).
  • Trapezoidal rule: R(z)=(1+z/2)/(1βˆ’z/2)R(z) = (1 + z/2)/(1 - z/2), A-stable and ∣R(z)∣=1|R(z)| = 1 on iRi\mathbb{R}.
  • RK4: R(z)=1+z+z2/2+z3/6+z4/24R(z) = 1 + z + z^2/2 + z^3/6 + z^4/24, stability region contains [βˆ’2.78,0]Γ—[βˆ’2.83i,2.83i][-2.78, 0] \times [-2.83i, 2.83i] approximately.

Stiffness and A-Stability

Definition7.8Stiff Problems and L-Stability

A system is stiff if it has widely separated time scales, i.e., eigenvalues of the Jacobian βˆ‚f/βˆ‚y\partial f/\partial y span several orders of magnitude with Re(Ξ»)<0\mathrm{Re}(\lambda) < 0. A method is L-stable if it is A-stable and R(z)β†’0R(z) \to 0 as zβ†’βˆ’βˆžz \to -\infty. L-stability ensures that very stiff components (∣hΞ»βˆ£β‰«1|h\lambda| \gg 1) are damped, not merely bounded. Backward Euler and BDFkk (k≀2k \leq 2) are L-stable; the trapezoidal rule is A-stable but not L-stable (∣R(z)∣=1|R(z)| = 1 on iRi\mathbb{R}).

RemarkDahlquist Barriers

First Dahlquist barrier: An explicit kk-step method has order at most kk. An implicit kk-step method has order at most k+1k + 1 (k+2k+2 if kk is odd). Second Dahlquist barrier: No A-stable multistep method has order greater than 2. The trapezoidal rule (order 2, A-stable) is the "best" A-stable multistep method. This motivates the use of BDF methods (which trade full A-stability for higher order) and implicit Runge-Kutta methods (which can be A-stable at any order).


Convergence

Definition7.9Zero-Stability and Convergence

A multistep method is zero-stable if the roots of its characteristic polynomial ρ(ΞΆ)=βˆ‘Ξ±jΞΆkβˆ’j\rho(\zeta) = \sum \alpha_j \zeta^{k-j} satisfy ∣΢jβˆ£β‰€1|\zeta_j| \leq 1, with roots on the unit circle being simple. The Dahlquist equivalence theorem states that a consistent multistep method is convergent if and only if it is zero-stable. Convergence then has order pp: max⁑n∣y(tn)βˆ’yn∣=O(hp)\max_n |y(t_n) - y_n| = O(h^p) where pp is the order of the local truncation error.

ExampleZero-Stability Failure: Midpoint Rule

The midpoint rule yn+1=ynβˆ’1+2hf(tn,yn)y_{n+1} = y_{n-1} + 2hf(t_n, y_n) has characteristic polynomial ρ(ΞΆ)=ΞΆ2βˆ’1\rho(\zeta) = \zeta^2 - 1 with roots ΞΆ=Β±1\zeta = \pm 1. Although the root ΞΆ=βˆ’1\zeta = -1 has ∣΢∣=1|\zeta| = 1 and is simple, rounding errors excite the parasitic solution (βˆ’1)n(-1)^n, causing oscillatory instability. This is zero-stable but marginally so; in practice, the midpoint rule is always used with periodic restarts or predictor-corrector damping.