Mathematical foundations of Adams-Bashforth-Moulton Multistep.
When solving computationally demanding ordinary differential equations—such as orbital trajectories with expensive gravitational N-body force evaluations or atmospheric climate models—evaluating the vector field f(t, y) dominates overall CPU time. In such regimes, four-stage Runge-Kutta methods are computationally wasteful, discarding all previous function values at the end of each step. Linear multistep methods, pioneered by John Couch Adams in 1855 and Francis Bashforth for ballistics computations, exploit previous time steps stored in a history buffer. By coupling an explicit Adams-Bashforth predictor with an implicit Adams-Moulton corrector in a PECE (Predict-Evaluate-Correct-Evaluate) architecture, the solver achieves fourth-order O(h⁴) accuracy using only two function evaluations per step—doubling computational throughput over RK4. In this laboratory, we implement the ABM predictor-corrector method with RK4 bootstrapping and verify fourth-order O(h⁴) convergence.
Viva voce questions & analytical theory
How do linear multistep methods differ fundamentally from Runge-Kutta methods?
Runge-Kutta methods are single-step methods: they discard all past history and compute multiple intermediate stage evaluations per step. Linear multistep methods (LMM) store past solution values and derivatives, requiring only 1 or 2 function evaluations per step to achieve high order, dramatically reducing computational cost when function evaluations are expensive.
What is the PECE (Predict-Evaluate-Correct-Evaluate) mode?
In PECE mode: (P) the explicit Adams-Bashforth formula predicts y*_{n+1}; (E) the derivative f*_{n+1} = f(t_{n+1}, y*_{n+1}) is evaluated; (C) the implicit Adams-Moulton formula corrects to produce y_{n+1}; and (E) the final derivative f_{n+1} = f(t_{n+1}, y_{n+1}) is evaluated for subsequent steps. This yields an explicit algorithm with the enhanced stability and accuracy of an implicit method.
What is the Dahlquist root condition for linear multistep stability?
The Dahlquist root condition states that a linear multistep method is zero-stable if and only if all roots of its first characteristic polynomial ρ(r) lie inside or on the unit circle in the complex plane (|r_i| ≤ 1), and any roots on the unit circle (|r_i| = 1) are simple (non-repeated).
What is the first Dahlquist barrier for linear multistep methods?
Germund Dahlquist (1956) proved that the order of accuracy p of a zero-stable k-step linear multistep method cannot exceed: p ≤ k + 1 if k is odd; p ≤ k + 2 if k is even; and p ≤ k for any explicit method. Thus, a 4-step explicit method has maximum order p = 4.
What is Milne's device for local error estimation?
When an explicit predictor of order p and an implicit corrector of order p are combined, their leading local truncation error terms are proportional to h^{p+1} f^{(p+1)}. Milne showed that the error in the corrector can be estimated directly from the difference |y*_{n+1} - y_{n+1}| without computing any higher derivatives: LTE ≈ [C_c / (C_p - C_c)] · (y_{n+1} - y*_{n+1}).
Why can multistep methods not start themselves?
A k-step method requires k prior solution values (y_n, y_{n-1}, ..., y_{n-k+1}) to compute the next step. At t = 0, only y_0 is known. Therefore, a self-starting single-step method (typically RK4) must be used to generate the first k - 1 points before the multistep engine can engage.
How does changing step size h complicate multistep methods compared to RK4?
Multistep coefficients are derived assuming uniform spacing h. Changing h requires interpolating past history points onto the new spacing (Nordsieck history array) or using variable-coefficient recurrences, whereas RK4 easily changes h at every step without overhead.
Algorithm precautions and stability rules
- Always bootstrap the first 3 history points using a fourth-order single-step method (RK4); using lower-order Euler will degrade overall accuracy to O(h).
- Ensure the history buffer correctly shifts previous values: y_{n-3} ← y_{n-2} ← y_{n-1} ← y_n before each new time step.
- Verify that floating point precision remains 64-bit IEEE 754 during the evaluation of large-coefficient difference stencils (e.g. 55, -59, 37, -9).
- Check for numerical instability when integrating near the boundary of the Adams-Moulton stability domain (h λ ∈ [-3.0, 0]).
- If step size h must be changed dynamically, interpolate the history registers or reset the RK4 bootstrap starter.
- Ensure floating point registers prevent subtractive cancellation during Milne error subtraction.
Theoretical limitations
- Linear multistep methods are not self-starting, requiring auxiliary starter routines whenever integration begins or restarts.
- Changing step size h is mathematically cumbersome compared to single-step Runge-Kutta methods.
- The second Dahlquist barrier proves that no explicit or implicit A-stable linear multistep method can exceed second-order accuracy (p ≤ 2).