Flow Lab

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

Lesson 4.6

Multistep Methods

Adams–Bashforth and Adams–Moulton families, starting values, zero-stability and the Dahlquist barriers.

Written byClaude Sonnet

🌊
Why this matters for simulation: Many CFD codes advance nonlinear terms with Adams–Bashforth and viscous terms implicitly (IMEX schemes).

By the end of this lesson you can…

  • Derive Adams–Bashforth 2 by integrating a line through past f values, and get the AB and Adams–Moulton weights from Lagrange polynomials.
  • Run a predictor-corrector (PECE) pair and choose starting values for a k-step method.
  • State the root condition and use parasitic roots to explain why a consistent scheme can diverge.
  • Compute the real-axis stability limits of AB2 to AB4 and compare their cost with RK4.
  • Name the weaknesses of multistep methods and describe the IMEX idea.
On this page
·
  1. Adams–Bashforth: extrapolate fff, integrate exactly
  2. Adams–Moulton: add the new point
  3. Predictor–corrector: PECE
  4. Starting values
  5. Zero-stability and the root condition
  6. Stability regions of the Adams methods
  7. IMEX: implicit where stiff, explicit elsewhere
  8. Weaknesses
  9. The lab
  10. Exercise: AB2 with an RK2 start
  11. Problems
  12. Key Takeaways
  13. What comes next

RK4 evaluates ff four times per step and keeps only their combination. In a fluid or flight code one evaluation is a whole pass over the grid or the airframe model, and the values fn,fn−1,…f_n, f_{n-1}, \dots of earlier steps were already paid for. A multistep method reuses them: one new evaluation per step, at any order. The price is start-up values, a rigid step and a new kind of instability. The lesson settles two loose ends: the diverging scheme of 4.1 Local Error, Global Error & Order and the root condition and Dahlquist barrier that 4.5 Stability Regions & Stiffness used from memory.

▶ Video Reusing past values of f: Adams–Bashforth by extrapolation, Adams–Moulton and PECE, starting values, parasitic roots and the root condition, stability limits, and the IMEX ideacaptions only
Transcript
  1. RK4 spends four evaluations of f per step and keeps only their combination. A multistep method keeps the old values instead: one new evaluation per step, at any order. RK4 at 240 steps costs 960 evaluations; AB4 at 960 steps, 969.
  2. Adams-Bashforth 2: draw the line through the last two values of f and extend it across the next step. Its area is the increment, h times three f n minus f n minus one, over two. Here it gives minus 0.1243; the exact integral is minus 0.1447.
  3. Integrating each Lagrange basis polynomial exactly gives the weights. Bashforth 4 is 55, minus 59, 37, minus 9, over 24. Adams-Moulton also uses f at the new point, so it is implicit, and its error constants are 5, 9 and 13.211 times smaller.
  4. Predict with Bashforth, evaluate, correct with Moulton, evaluate again: PECE, two evaluations per step. The order is the smaller of the corrector order and the predictor order plus one. Yet at about 960 evaluations on the oscillator, AB4 beats RK4 by 6.1 times, and PECE loses to both.
  5. A k-step method needs k starting values, so a one-step method supplies them. Starting errors of order h to the q give global order min of p and q. One Euler step suffices for AB2 but caps AB3 and AB4 at 2. The exercise's AB2 with a Heun start takes 21 calls.
  6. Set f to zero: solutions behave like the roots of rho to the n. AB2's roots are 1 and 0. The scheme from the error lesson has 1 and minus 5, and at h equals 0.1 the parasitic root is minus 5.30483. Its error at t equals 1: 7.045, 4.652 times ten to the 6, 2.883 times ten to the 19.
  7. The root condition: roots inside the unit disc, those on the circle simple. The Dahlquist equivalence theorem, from memory: consistent plus zero-stable means convergent. BDF's largest parasitic root stays below 1 through BDF6, but BDF7 has 1.0222 and BDF8 1.1839.
  8. Stability regions come from the boundary locus, rho over sigma. On the real axis AB2 reaches minus 1, AB3 minus 6 over 11, AB4 minus 0.3. At minus 0.9 the roots are 0.5183 and minus 0.8683; at minus 1.1 the second is minus 1.1347, past minus 1. The trapezoid's locus is the imaginary axis.
  9. RK4 reaches 2.7853 for four evaluations: 1.436 per unit lambda t at the limit. AB2 needs 1.0, better. But AB3 needs 1.833 and AB4 3.333, worse: raising the order shrinks the Bashforth region.
  10. On waves AB2 has no stable interval. Its growth factor exceeds 1 by 2.5507 times ten to the minus 5 at h equals 0.1, so 200 steps raise the energy by 1.026 times ten to the minus 2, matching the measured 1.025 times ten to the minus 2. AB3 and AB4 lose energy; RK4 loses 2.774 times ten to the minus 6.
  11. Treat the stiff part implicitly and the rest explicitly: IMEX. Explicit Euler overflows at h equals 0.05 and 0.01, and errs 226 at 0.0025. IMEX Euler gives 9.610 times ten to the minus 6 down to 5.167 times ten to the minus 7. Fluid solvers pair implicit diffusion with explicit advection, from memory.
  12. Multistep coefficients assume equal steps. Let the steps wander between half and one and a half times the mean: equal-spacing weights then give order 1, error 5.400 times ten to the minus 3 at N equals 800; the variable-step formula keeps order 2, at 1.449 times ten to the minus 4. Adaptive solvers therefore lean on Runge-Kutta.
  13. Recap: reuse old values, one evaluation per step. Weights come from integrating a polynomial. PECE costs two evaluations. Roots of rho must stay inside the disc. Bashforth regions shrink with order. Next: symplectic methods.

Adams–Bashforth: extrapolate ff, integrate exactly

Integrate over a step: y(tn+1)=y(tn)+∫tntn+1f dty(t_{n+1}) = y(t_n) + \int_{t_n}^{t_{n+1}} f\,dt. The integrand is unknown on the interval, but known at earlier points: replace ff by the polynomial through the last kk values and integrate that exactly. For k=2k = 2 the line through (tn−1,fn−1)(t_{n-1}, f_{n-1}) and (tn,fn)(t_n, f_n) is p(t)=fn+fn−fn−1h(t−tn)p(t) = f_n + \frac{f_n - f_{n-1}}{h}(t - t_n), and

∫tntn+hp dt=hfn+fn−fn−1h⋅h22⟹yn+1=yn+h 3fn−fn−12.\int_{t_n}^{t_n + h} p\,dt = h f_n + \frac{f_n - f_{n-1}}{h}\cdot\frac{h^2}{2} \quad\Longrightarrow\quad y_{n+1} = y_n + h\,\frac{3 f_n - f_{n-1}}{2}.

This is Adams–Bashforth 2 (AB2); a constant (k=1k = 1) gives forward Euler, and AM1 will be backward Euler. In general put nodes at s=0,−1,…,−(k−1)s = 0, -1, \dots, -(k-1) steps from tnt_n and give fn−jf_{n-j} the weight ∫01Lj(s) ds\int_0^1 L_j(s)\,ds of its Lagrange basis polynomial. Block A does this in exact fractions, also for the Adams–Moulton nodes s=1,0,−1,…s = 1, 0, -1, \dots (weights on fn+1,fn,…f_{n+1}, f_n, \dots), with the error constant Cp+1C_{p+1} defined below:

methodweightsCp+1C_{p+1}
AB23/2, −1/23/2,\ -1/25/125/12
AB323/12, −4/3, 5/1223/12,\ -4/3,\ 5/123/83/8
AB455/24, −59/24, 37/24, −9/2455/24,\ -59/24,\ 37/24,\ -9/24251/720251/720
AM2 (trapezoid)1/2, 1/21/2,\ 1/2−1/12-1/12
AM35/12, 2/3, −1/125/12,\ 2/3,\ -1/12−1/24-1/24
AM43/8, 19/24, −5/24, 1/243/8,\ 19/24,\ -5/24,\ 1/24−19/720-19/720

Why order kk. A degree k−1k-1 polynomial through kk points misses a smooth ff by O(hk)O(h^k); integrating over length hh gives local error O(hk+1)O(h^{k+1}), global order kk (4.1 Local Error, Global Error & Order). Block A checks: on y=tqy = t^q at tn=0t_n = 0 each order-kk formula has residual 00 for q≤kq \le k and a nonzero one at q=k+1q = k+1 (5/25/2 for AB2). The error constant is defined by local error ≈Cp+1hp+1y(p+1)\approx C_{p+1}h^{p+1}y^{(p+1)}, so it is that residual over (p+1)!(p+1)!: (5/2)/3!=5/12(5/2)/3! = 5/12. Block B measures global orders 1.991.99, 2.992.99, 3.983.98 (AB2 to AB4).

Adams–Moulton: add the new point

Include (tn+1,fn+1)(t_{n+1}, f_{n+1}) among the nodes. The polynomial now interpolates across the interval instead of extrapolating past it, and the formula is implicit: fn+1=f(tn+1,yn+1)f_{n+1} = f(t_{n+1}, y_{n+1}) is on the right. AM1 is backward Euler, AM2 the trapezoid rule. Against its Bashforth twin the constant is smaller by ∣CAB∣/∣CAM∣=5, 9, 13.211\lvert C_\text{AB}\rvert / \lvert C_\text{AM}\rvert = 5,\ 9,\ 13.211 for orders 2,3,42, 3, 4 (block A), with opposite sign. The implicit equation can be solved by Newton (4.5 Stability Regions & Stiffness) or by fixed-point sweeps y[m+1]=const+hβ0f(tn+1,y[m])y^{[m+1]} = \text{const} + h\beta_0 f(t_{n+1}, y^{[m]}), a contraction when hβ0L<1h\beta_0 L \lt 1 (LL the Lipschitz constant).

Predictor–corrector: PECE

Predict with an Adams–Bashforth step, Evaluate ff at the prediction, Correct with Adams–Moulton using that value as fn+1f_{n+1}, Evaluate again for the history: two evaluations per step. Euler plus trapezoid is Heun’s method (4.2 The Euler Family: Forward, Backward, Heun & Midpoint). Block B runs pairs on x′′=−xx'' = -x to T=6T = 6 with N=30N = 30 to 480480; the observed order at the last halving is AB1+AM2 2.02.0, AB2+AM3 2.992.99, AB3+AM3 2.972.97, AB3+AM2 1.991.99, AB1+AM1 0.970.97. All fit order = min(corrector order, predictor order + 1). Mechanism: the predictor’s local error O(hp∗+1)O(h^{p^*+1}) enters the corrector multiplied by hβ0 ∂f/∂yh\beta_0\,\partial f/\partial y, adding O(hp∗+2)O(h^{p^*+2}), while the corrector itself contributes O(hp+1)O(h^{p+1}).

Is the second evaluation worth it? Not here. At about 960960 evaluations RK4 reaches 1.864×10−81.864\times10^{-8} (N=240N = 240), AB4 3.046×10−93.046\times10^{-9} (N=960N = 960) and PECE AB3+AM3 4.587×10−74.587\times10^{-7} (N=480N = 480): AB4 beats RK4 by a factor 6.16.1 and PECE spends half its budget on corrections. It does give a free error estimate, corrected minus predicted, which classical Adams codes use to pick the step (from memory).

Starting values

A kk-step method needs kk values and the ODE gives one; a one-step method supplies the rest. One step of size h=0.05h = 0.05 has error 1.25×10−31.25\times10^{-3} from Euler, 2.08×10−52.08\times10^{-5} from RK2 and 2.60×10−92.60\times10^{-9} from RK4: O(h2)O(h^2), O(h3)O(h^3), O(h5)O(h^5). Block C runs ABkk on the oscillator with each starter; observed order at the last halving:

  • AB2: 1.991.99 with an Euler start (error 3.516×10−43.516\times10^{-4}) and with RK4 (3.735×10−43.735\times10^{-4}).
  • AB3: 1.951.95 with Euler (rising: 1.52, 1.8, 1.91, 1.951.52,\ 1.8,\ 1.91,\ 1.95), 2.992.99 with RK2.
  • AB4: 2.02.0 with Euler, 2.922.92 with RK2 (rising: 1.97, 2.61, 2.82, 2.921.97,\ 2.61,\ 2.82,\ 2.92), 3.983.98 with RK4.

The rule: starting errors of O(hq)O(h^q) give global order min⁡(p,q)\min(p, q). A start error perturbs the solution itself, which travels along the principal root, so it arrives at TT times a bounded factor and must be O(hp)O(h^p) to keep order pp. One Euler step is enough for AB2, caps AB3 and AB4 at 22; RK2 points AB4 toward 33; only RK4 reaches 44.

Zero-stability and the root condition

Write a linear kk-step method as ∑j=0kαjyn+j=h∑j=0kβjfn+j\sum_{j=0}^{k} \alpha_j y_{n+j} = h\sum_{j=0}^{k} \beta_j f_{n+j} with characteristic polynomials ρ(ξ)=∑αjξj\rho(\xi) = \sum \alpha_j \xi^j and σ(ξ)=∑βjξj\sigma(\xi) = \sum \beta_j \xi^j (AB2: ρ=ξ2−ξ\rho = \xi^2 - \xi, σ=(3ξ−1)/2\sigma = (3\xi - 1)/2). It is consistent when it solves y′=0y' = 0 and y′=1y' = 1 exactly: ρ(1)=0\rho(1) = 0 and ρ′(1)=σ(1)\rho'(1) = \sigma(1).

Set f=0f = 0: then ∑αjyn+j=0\sum \alpha_j y_{n+j} = 0, solved by ξn\xi^n for each root ξ\xi of ρ\rho (nξnn\xi^n for a double root). Since n≈T/h→∞n \approx T/h \to \infty, these must stay bounded: the root condition says all roots of ρ\rho have ∣ξ∣≤1\lvert\xi\rvert \le 1, and those on the circle are simple. The root ξ=1\xi = 1 is the real solution; the other k−1k-1 have no counterpart in a first-order ODE and are parasitic. An Adams method has ρ=ξk−ξk−1\rho = \xi^k - \xi^{k-1}, roots 11 and 00 (block D): parasitic roots die at once, every free parameter goes into σ\sigma. The scheme of 4.1 Local Error, Global Error & Order, yn+1=−4yn+5yn−1+h(4fn+2fn−1)y_{n+1} = -4y_n + 5y_{n-1} + h(4f_n + 2f_{n-1}), spends them in ρ\rho: ρ=ξ2+4ξ−5\rho = \xi^2 + 4\xi - 5 has roots 11 and −5-5. It gains an order, breaks the condition. Block D, y′=−yy' = -y to t=1t = 1, exact starts:

steps NNunstable schemeAB2
10107.0457.0451.464×10−31.464\times10^{-3}
20204.652×1064.652\times10^{6}3.751×10−43.751\times10^{-4}
40402.883×10192.883\times10^{19}9.481×10−59.481\times10^{-5}
80801.671×10461.671\times10^{46}2.383×10−52.383\times10^{-5}

AB2’s error falls by about 44 per halving; the unstable scheme’s is multiplied by 6.6×1056.6\times10^{5}, then 6.2×10126.2\times10^{12}, then 5.8×10265.8\times10^{26}.

Dahlquist equivalence theorem (from memory): with Lipschitz ff and starting values converging to y0y_0, a linear multistep method converges if and only if it is consistent and zero-stable, at the order of consistency if the starting errors share it (block C). BDF has ρ(ξ)=∑j=1k1j ξk−j(ξ−1)j\rho(\xi) = \sum_{j=1}^{k} \tfrac1j\,\xi^{k-j}(\xi - 1)^j; block D finds its largest parasitic root for BDF1 to BDF8: 0, 0.3333, 0.4264, 0.5609, 0.7087, 0.8634, 1.0222, 1.18390,\ 0.3333,\ 0.4264,\ 0.5609,\ 0.7087,\ 0.8634,\ 1.0222,\ 1.1839. BDF1 to BDF6 pass; BDF7 and BDF8 fail (higher orders were not tried), confirming what 4.5 Stability Regions & Stiffness said from memory.

The Dahlquist barriers (from memory, not derived or checked here). First: a zero-stable kk-step method has order at most k+2k+2 for even kk, k+1k+1 for odd kk, and kk if explicit. Second: an A-stable multistep method has order at most 22, and the trapezoid rule has the smallest error constant among them (block A shows its −1/12-1/12, not that it is smallest).

✅ Concept check

Four two-step methods have these first characteristic polynomials. Which violates the root condition?

Stability regions of the Adams methods

On y′=λyy' = \lambda y, z=hλz = h\lambda, the growth factor satisfies ρ(ξ)−zσ(ξ)=0\rho(\xi) - z\sigma(\xi) = 0 and the method is stable when every root is in the unit disc. A root reaches the circle, ξ=eiθ\xi = e^{i\theta}, on the boundary locus z(θ)=ρ(eiθ)/σ(eiθ)z(\theta) = \rho(e^{i\theta})/\sigma(e^{i\theta}). The locus can cut through the region, so block E decides by the roots: walk down the negative axis, bisect at the exit. The limits equal the locus at θ=π\theta = \pi: AB2 1.00001.0000, AB3 0.54550.5455 (=6/11=6/11), AB4 0.30000.3000. AM2 (trapezoid) has no limit up to −60-60 (block E): its locus z=2(ξ−1)/(ξ+1)=2itan⁡(θ/2)z = 2(\xi - 1)/(\xi + 1) = 2i\tan(\theta/2) is on the imaginary axis.

Raising the order of an Adams–Bashforth method shrinks its region, the opposite of RK. RK4’s limit is 2.78532.7853 for 44 evaluations, so the evaluations per unit of ∣λ∣t\lvert\lambda\rvert t at the limit are 1.01.0 (AB2), 1.8331.833 (AB3), 3.3333.333 (AB4) and 1.4361.436 (RK4): at the stability edge AB2 beats RK4 and AB3 and AB4 lose.

Oscillations. Advection and waves have imaginary eigenvalues. For AB2 at z=ihz = ih, ∣ξ∣−1=2.5507×10−5, 1.5703×10−6, 9.778×10−8\lvert\xi\rvert - 1 = 2.5507\times10^{-5},\ 1.5703\times10^{-6},\ 9.778\times10^{-8} for h=0.1,0.05,0.025h = 0.1, 0.05, 0.025: ratios 16.216.2, 16.116.1, about h4/4h^4/4. AB2 has no stable interval there. At h=0.1h = 0.1 the largest ∣ξ∣\lvert\xi\rvert is 1.00002551.0000255 (AB2), 0.99996270.9999627 (AB3), 0.99999950.9999995 (AB4). On the oscillator to T=20T = 20 the final E/E0−1E/E_0 - 1 is +1.025×10−2+1.025\times10^{-2} (AB2, 203203 evaluations), −1.465×10−2-1.465\times10^{-2} (AB3), −2.123×10−4-2.123\times10^{-4} (AB4), +1.553×10−3+1.553\times10^{-3} (PECE AB3+AM3, 405405) and −2.774×10−6-2.774\times10^{-6} (RK4, 800800). AB2’s gain is the growth factor at work: (1+2.5507×10−5)400−1=1.026×10−2(1 + 2.5507\times10^{-5})^{400} - 1 = 1.026\times10^{-2} (200200 steps, energy is ξ2\xi^2 per step).

◆ Interactive Run AB2, AB3, AB4, PECE pairs, RK4 and an unstable two-step scheme on an oscillator or on y' = -y

Loading simulation…

Things to try (a headless run reproduced these):

  1. AB2, oscillator, h=0.1h = 0.1, T=20T = 20: energy +1.025×10−2+1.025\times10^{-2}, largest root 1.00002551.0000255. At h=0.5h = 0.5: +6.878+6.878 (root 1.02671941.0267194).
  2. “unstable 2-step” on y′=−yy' = -y (T=1T = 1), starting values exact: h=0.1,0.05,0.025h = 0.1, 0.05, 0.025 give 7.0457.045, 4.652×1064.652\times10^{6}, 2.883×10192.883\times10^{19} and root moduli 0.904830.90483, 5.304835.30483 at h=0.1h = 0.1. With RK4 starts the first is 7.2787.278.

IMEX: implicit where stiff, explicit elsewhere

Split y′=S(t,y)+N(t,y)y' = S(t, y) + N(t, y) with SS stiff and NN not. All-implicit is expensive and all-explicit unstable (4.5 Stability Regions & Stiffness); IMEX treats SS implicitly and NN explicitly. Block F: y′=−1000 (y−cos⁡t)+Ny' = -1000\,(y - \cos t) + N, N=−sin⁡t+y2−cos⁡2tN = -\sin t + y^2 - \cos^2 t, so the exact solution is cos⁡t\cos t and NN has slope 2y2y, at most 22. IMEX Euler is (1+1000h) yn+1=yn+1000hcos⁡tn+1+hN(tn,yn)(1 + 1000h)\,y_{n+1} = y_n + 1000h\cos t_{n+1} + hN(t_n, y_n): the implicit part is linear, a division. At T=2T = 2 explicit Euler overflows at h=0.05h = 0.05 and 0.010.01 and has error 226226 at h=0.0025h = 0.0025 (it needs h<2/1000h \lt 2/1000). IMEX Euler has errors 9.610×10−69.610\times10^{-6}, 2.044×10−62.044\times10^{-6}, 5.167×10−75.167\times10^{-7} at those three steps, observed orders 0.96, 0.98, 0.990.96,\ 0.98,\ 0.99 from h=0.04h = 0.04 to 0.0050.005. The step limit now comes from NN alone. A second-order IMEX pairs BDF2 for SS with the AB2-type extrapolation 2Nn−Nn−12N_n - N_{n-1} for NN (from memory, not run here).

Weaknesses

The step cannot change freely. The coefficients assume equal spacing. With steps hnh_n, hn−1h_{n-1} the line through the last two values has slope (fn−fn−1)/hn−1(f_n - f_{n-1})/h_{n-1}; integrating it over hnh_n gives yn+1=yn+hn[(1+r2)fn−r2fn−1]y_{n+1} = y_n + h_n\big[(1 + \tfrac r2) f_n - \tfrac r2 f_{n-1}\big], r=hn/hn−1r = h_n/h_{n-1} (3/23/2 and −1/2-1/2 at r=1r = 1). The equal-spacing weights used anyway are off by O(h) (fn−fn−1)O(h)\,(f_n - f_{n-1}), an O(h2)O(h^2) local error instead of O(h3)O(h^3). Block G lets the steps wander between 0.50.5 and 1.51.5 times the mean; equal-spacing weights give observed orders 0.99, 1.04, 1.02, 1.010.99,\ 1.04,\ 1.02,\ 1.01 (error 5.400×10−35.400\times10^{-3} at N=800N = 800), the variable-step formula 1.97, 1.98, 1.99, 2.01.97,\ 1.98,\ 1.99,\ 2.0 (1.449×10−41.449\times10^{-4}). Variable-step codes must recompute coefficients or interpolate the history at every change, which is why adaptive solvers lean on Runge–Kutta (4.4 Adaptive Step Size & RK45).

Discontinuities. The history polynomial assumes ff is smooth. A jump in ff (a contact, a switch) makes the interpolation error O(1)O(1) for the next kk steps; stop at the event and restart with RK steps.

The lab

The lab cell computes every number above (blocks A to G) and runs in your browser.

🐍 PythonLab: Adams weights, orders, PECE, starting values, roots, stability limits, IMEX, step changes (blocks A to G)
⌘/Ctrl + Enter

Exercise: AB2 with an RK2 start

Implement AB2 on y′=−y+sin⁡ty' = -y + \sin t, y(0)=0y(0) = 0, to T=4T = 4: first step by Heun (RK2), then AB2 with one new call of ff per step, counting calls. Then measure the observed order from the errors at N=10,20,…,160N = 10, 20, \dots, 160.

🧪 Coding exerciseExercise: AB2 with an RK2 start, and its observed order
⌘/Ctrl + Enter

The reference solution makes 2121 calls for N=20N = 20 and finds orders 1.770, 1.894, 1.951, 1.9761.770,\ 1.894,\ 1.951,\ 1.976.

✅ Concept check

AB2 is applied to x'' = -x with a small step h. What happens to the energy over a long run?

✅ Concept check

The fastest eigenvalue of a linearised system is -50. What is the largest step h for which AB4 is stable on it? (AB4's real-axis limit is 0.3.)

Problems

✏️ Pen & paperAM3 from three conditions●●○

The formula yn+1=yn+h(w0fn+1+w1fn+w2fn−1)y_{n+1} = y_n + h(w_0 f_{n+1} + w_1 f_n + w_2 f_{n-1}) uses nodes s=1,0,−1s = 1, 0, -1. Require it exact for y=t,t2,t3y = t, t^2, t^3.

  1. Write the three equations and solve for w0,w1,w2w_0, w_1, w_2.
  2. Apply the formula to y=t4y = t^4 at tn=0t_n = 0, h=1h = 1: the residual, and the error constant.
Show worked solution
  1. At tn=0t_n = 0, h=1h = 1, exactness on y=tqy = t^q reads 1=q (w0+w10q−1+w2(−1)q−1)1 = q\,(w_0 + w_1 0^{q-1} + w_2 (-1)^{q-1}). So w0+w1+w2=1w_0 + w_1 + w_2 = 1, 2(w0−w2)=12(w_0 - w_2) = 1, 3(w0+w2)=13(w_0 + w_2) = 1. Hence w0−w2=12w_0 - w_2 = \tfrac12, w0+w2=13w_0 + w_2 = \tfrac13: w0=512w_0 = \tfrac5{12}, w2=−112w_2 = -\tfrac1{12}, w1=23w_1 = \tfrac23.
  2. y(1)−y(0)=1y(1) - y(0) = 1; the formula gives 4(512+112)=24(\tfrac5{12} + \tfrac1{12}) = 2. Residual −1-1, so C4=−1/24C_4 = -1/24 and the order is 33 (block A agrees).
✏️ Pen & paperThe AB2 limit by hand●●○
  1. Show that for AB2 on y′=λyy' = \lambda y, ξ2−(1+32z)ξ+12z=0\xi^2 - (1 + \tfrac32 z)\xi + \tfrac12 z = 0.
  2. Show both roots are real for real zz; put ξ=−1\xi = -1 to find the stability limit.
  3. Find the roots at z=−0.9z = -0.9 and z=−1.1z = -1.1.
Show worked solution
  1. yn=ξny_n = \xi^n in yn+1=yn+z(32yn−12yn−1)y_{n+1} = y_n + z(\tfrac32 y_n - \tfrac12 y_{n-1}) gives the quadratic.
  2. The discriminant 2.25z2+z+12.25z^2 + z + 1 is positive for all real zz (1−9<01 - 9 \lt 0). The roots start at 11 and 00 and move continuously as zz decreases; the first to reach modulus 11 does so at ±1\pm1, and ξ=1\xi = 1 needs z=0z = 0. So ξ=−1\xi = -1: 2+2z=02 + 2z = 0, z=−1z = -1.
  3. z=−0.9z = -0.9: ξ2+0.35ξ−0.45=0\xi^2 + 0.35\xi - 0.45 = 0, roots 0.51830.5183, −0.8683-0.8683 (stable). z=−1.1z = -1.1: ξ2+0.65ξ−0.55=0\xi^2 + 0.65\xi - 0.55 = 0, roots 0.48470.4847, −1.1347-1.1347 (unstable).
✏️ Pen & paperLeapfrog: zero-stable, stable only for waves●●●

The leapfrog rule is yn+1=yn−1+2hfny_{n+1} = y_{n-1} + 2h f_n.

  1. Find ρ\rho, σ\sigma. Is it consistent? Zero-stable?
  2. Find the boundary locus and the stability region.
  3. On y′=−yy' = -y with h=0.1h = 0.1: both growth factors, and the parasitic one after 5050 steps (to t=5t = 5) against the true e−5e^{-5}.
Show worked solution
  1. ρ=ξ2−1\rho = \xi^2 - 1, σ=2ξ\sigma = 2\xi; ρ(1)=0\rho(1) = 0, ρ′(1)=2=σ(1)\rho'(1) = 2 = \sigma(1). The roots ±1\pm1 are simple: zero-stable.
  2. z(θ)=(e2iθ−1)/(2eiθ)=isin⁡θz(\theta) = (e^{2i\theta} - 1)/(2e^{i\theta}) = i\sin\theta, the segment from −i-i to ii. The roots of ξ2−2zξ−1\xi^2 - 2z\xi - 1 have product −1-1, so both are in the closed disc only if both are on the circle: the region is that segment, so leapfrog is stable on pure oscillations and nowhere else. 4.7 Energy & Symplectic Integrators builds on that.
  3. ξ=−h±1+h2\xi = -h \pm \sqrt{1 + h^2}: 0.90500.9050 and −1.1050-1.1050. After 5050 steps the parasitic factor is 1.105050=147.21.1050^{50} = 147.2, while the true solution has shrunk to e−5=0.0067e^{-5} = 0.0067.

Key Takeaways

  • Multistep methods reuse past ff: one new evaluation per step at any order, against four for RK4.
  • Adams–Bashforth integrates the polynomial through the last kk values of ff (AB2: yn+1=yn+h(3fn−fn−1)/2y_{n+1} = y_n + h(3f_n - f_{n-1})/2); Adams–Moulton includes fn+1f_{n+1}, is implicit, and has error constants 55 to 1313 times smaller.
  • PECE has order min(corrector, predictor + 1) at two evaluations per step; starting errors O(hq)O(h^q) give order min⁡(p,q)\min(p, q).
  • Root condition: roots of ρ\rho in the closed unit disc, those on the circle simple. A root at −5-5 makes a consistent scheme diverge; consistent plus zero-stable is convergent (Dahlquist, from memory). BDF7 fails.
  • AB regions shrink with order and AB2 grows every oscillation. A changed step needs new coefficients, a jump in ff a restart, and IMEX keeps the stiff part implicit.

What comes next

4.7 Energy & Symplectic Integrators asks for energy that stays bounded for millions of steps, which none of these guarantee.

Finished this lesson?

Mark it complete to track your progress (saved in this browser). Reading every section does this for you.