RK4 evaluates 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 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.
Transcript
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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 , integrate exactly
Integrate over a step: . The integrand is unknown on the interval, but known at earlier points: replace by the polynomial through the last values and integrate that exactly. For the line through and is , and
This is Adams–Bashforth 2 (AB2); a constant () gives forward Euler, and AM1 will be backward Euler. In general put nodes at steps from and give the weight of its Lagrange basis polynomial. Block A does this in exact fractions, also for the Adams–Moulton nodes (weights on ), with the error constant defined below:
| method | weights | |
|---|---|---|
| AB2 | ||
| AB3 | ||
| AB4 | ||
| AM2 (trapezoid) | ||
| AM3 | ||
| AM4 |
Why order . A degree polynomial through points misses a smooth by ; integrating over length gives local error , global order (4.1 Local Error, Global Error & Order). Block A checks: on at each order- formula has residual for and a nonzero one at ( for AB2). The error constant is defined by local error , so it is that residual over : . Block B measures global orders , , (AB2 to AB4).
Adams–Moulton: add the new point
Include among the nodes. The polynomial now interpolates across the interval instead of extrapolating past it, and the formula is implicit: is on the right. AM1 is backward Euler, AM2 the trapezoid rule. Against its Bashforth twin the constant is smaller by for orders (block A), with opposite sign. The implicit equation can be solved by Newton (4.5 Stability Regions & Stiffness) or by fixed-point sweeps , a contraction when ( the Lipschitz constant).
Predictor–corrector: PECE
Predict with an Adams–Bashforth step, Evaluate at the prediction, Correct with Adams–Moulton using that value as , 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 to with to ; the observed order at the last halving is AB1+AM2 , AB2+AM3 , AB3+AM3 , AB3+AM2 , AB1+AM1 . All fit order = min(corrector order, predictor order + 1). Mechanism: the predictor’s local error enters the corrector multiplied by , adding , while the corrector itself contributes .
Is the second evaluation worth it? Not here. At about evaluations RK4 reaches (), AB4 () and PECE AB3+AM3 (): AB4 beats RK4 by a factor 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 -step method needs values and the ODE gives one; a one-step method supplies the rest. One step of size has error from Euler, from RK2 and from RK4: , , . Block C runs AB on the oscillator with each starter; observed order at the last halving:
- AB2: with an Euler start (error ) and with RK4 ().
- AB3: with Euler (rising: ), with RK2.
- AB4: with Euler, with RK2 (rising: ), with RK4.
The rule: starting errors of give global order . A start error perturbs the solution itself, which travels along the principal root, so it arrives at times a bounded factor and must be to keep order . One Euler step is enough for AB2, caps AB3 and AB4 at ; RK2 points AB4 toward ; only RK4 reaches .
Zero-stability and the root condition
Write a linear -step method as with characteristic polynomials and (AB2: , ). It is consistent when it solves and exactly: and .
Set : then , solved by for each root of ( for a double root). Since , these must stay bounded: the root condition says all roots of have , and those on the circle are simple. The root is the real solution; the other have no counterpart in a first-order ODE and are parasitic. An Adams method has , roots and (block D): parasitic roots die at once, every free parameter goes into . The scheme of 4.1 Local Error, Global Error & Order, , spends them in : has roots and . It gains an order, breaks the condition. Block D, to , exact starts:
| steps | unstable scheme | AB2 |
|---|---|---|
AB2’s error falls by about per halving; the unstable scheme’s is multiplied by , then , then .
Dahlquist equivalence theorem (from memory): with Lipschitz and starting values converging to , 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 ; block D finds its largest parasitic root for BDF1 to BDF8: . 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 -step method has order at most for even , for odd , and if explicit. Second: an A-stable multistep method has order at most , and the trapezoid rule has the smallest error constant among them (block A shows its , not that it is smallest).
Stability regions of the Adams methods
On , , the growth factor satisfies and the method is stable when every root is in the unit disc. A root reaches the circle, , on the boundary locus . 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 : AB2 , AB3 (), AB4 . AM2 (trapezoid) has no limit up to (block E): its locus is on the imaginary axis.
Raising the order of an Adams–Bashforth method shrinks its region, the opposite of RK. RK4’s limit is for evaluations, so the evaluations per unit of at the limit are (AB2), (AB3), (AB4) and (RK4): at the stability edge AB2 beats RK4 and AB3 and AB4 lose.
Oscillations. Advection and waves have imaginary eigenvalues. For AB2 at , for : ratios , , about . AB2 has no stable interval there. At the largest is (AB2), (AB3), (AB4). On the oscillator to the final is (AB2, evaluations), (AB3), (AB4), (PECE AB3+AM3, ) and (RK4, ). AB2’s gain is the growth factor at work: ( steps, energy is per step).
Things to try (a headless run reproduced these):
- AB2, oscillator, , : energy , largest root . At : (root ).
- “unstable 2-step” on (), starting values exact: give , , and root moduli , at . With RK4 starts the first is .
IMEX: implicit where stiff, explicit elsewhere
Split with stiff and not. All-implicit is expensive and all-explicit unstable (4.5 Stability Regions & Stiffness); IMEX treats implicitly and explicitly. Block F: , , so the exact solution is and has slope , at most . IMEX Euler is : the implicit part is linear, a division. At explicit Euler overflows at and and has error at (it needs ). IMEX Euler has errors , , at those three steps, observed orders from to . The step limit now comes from alone. A second-order IMEX pairs BDF2 for with the AB2-type extrapolation for (from memory, not run here).
Weaknesses
The step cannot change freely. The coefficients assume equal spacing. With steps , the line through the last two values has slope ; integrating it over gives , ( and at ). The equal-spacing weights used anyway are off by , an local error instead of . Block G lets the steps wander between and times the mean; equal-spacing weights give observed orders (error at ), the variable-step formula (). 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 is smooth. A jump in (a contact, a switch) makes the interpolation error for the next 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.
Exercise: AB2 with an RK2 start
Implement AB2 on , , to : first step by Heun (RK2), then AB2 with one new call of per step, counting calls. Then measure the observed order from the errors at .
The reference solution makes calls for and finds orders .
Problems
The formula uses nodes . Require it exact for .
- Write the three equations and solve for .
- Apply the formula to at , : the residual, and the error constant.
Show worked solution
- At , , exactness on reads . So , , . Hence , : , , .
- ; the formula gives . Residual , so and the order is (block A agrees).
- Show that for AB2 on , .
- Show both roots are real for real ; put to find the stability limit.
- Find the roots at and .
Show worked solution
- in gives the quadratic.
- The discriminant is positive for all real (). The roots start at and and move continuously as decreases; the first to reach modulus does so at , and needs . So : , .
- : , roots , (stable). : , roots , (unstable).
The leapfrog rule is .
- Find , . Is it consistent? Zero-stable?
- Find the boundary locus and the stability region.
- On with : both growth factors, and the parasitic one after steps (to ) against the true .
Show worked solution
- , ; , . The roots are simple: zero-stable.
- , the segment from to . The roots of have product , 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.
- : and . After steps the parasitic factor is , while the true solution has shrunk to .
Key Takeaways
- Multistep methods reuse past : one new evaluation per step at any order, against four for RK4.
- Adams–Bashforth integrates the polynomial through the last values of (AB2: ); Adams–Moulton includes , is implicit, and has error constants to times smaller.
- PECE has order min(corrector, predictor + 1) at two evaluations per step; starting errors give order .
- Root condition: roots of in the closed unit disc, those on the circle simple. A root at 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 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.