GuideODEsadvanced

Adams-Bashforth methods

Explicit multistep methods that integrate the ODE by approximating f with its interpolating polynomial over already-computed nodes: full derivation of AB2 with Lagrange, the AB3 and AB4 formulas, their order and how to start them.

From one-step to multistep

One-step methods use only the previous node's information; moving to the next subinterval, they throw everything else away. Multistep methods reuse the slopes fj=f(tj,yj)f_j=f(t_j,y_j) of several already-computed nodes, making better use of the work done: each step costs only one new evaluation of ff. Start from the integral form of the IVP:

y(tk+1)=y(tk)+∫tktk+1f(τ,y(τ)) dτy(t_{k+1})=y(t_k)+\int_{t_k}^{t_{k+1}} f(\tau,y(\tau))\,d\tau

The integral cannot be computed because the integrand depends on the unknown solution. Adams-Bashforth replaces ff by the polynomial that interpolates it at the previous nodes tk,tk−1,…t_k, t_{k-1},\dots, where its values are known, and integrates that polynomial. Since it uses already-computed values, the resulting method is explicit.

Derivation of AB2

The two-step case concentrates all the mechanics: interpolate ff linearly at tk−1t_{k-1} and tkt_k, integrate and read off the coefficients.

tₖ₋₁tₖtₖ₊₁fₖ₋₁fₖknown slopesextrapolationintegrate herep₁(t)
AB2 interpolates the known slopes fk−1f_{k-1} and fkf_k and extrapolates that line over the new interval [tk,tk+1][t_k,t_{k+1}].
Expand diagram

AB2 interpolates the known slopes fk−1f_{k-1} and fkf_k and extrapolates that line over the new interval [tk,tk+1][t_k,t_{k+1}].

DerivationDerivation: two-step Adams-Bashforth (AB2)View as its own page →

Step 1: the integral form

tₖ₋₁tₖtₖ₊₁fₖ₋₁fₖknown slopesextrapolationintegrate herep₁(t)
The Lagrange line is built from already-computed slopes and then used beyond its nodes: this is why Adams-Bashforth is explicit and extrapolatory.
Expand diagram

The Lagrange line is built from already-computed slopes and then used beyond its nodes: this is why Adams-Bashforth is explicit and extrapolatory.

  1. Start from the IVP y′(t)=f(t,y(t))y'(t)=f(t,y(t)). Integrate both sides between tkt_k and tk+1t_{k+1}:

    ∫tktk+1y′(τ) dτ=∫tktk+1f(τ,y(τ)) dτ\int_{t_k}^{t_{k+1}} y'(\tau)\,d\tau=\int_{t_k}^{t_{k+1}} f\bigl(\tau,y(\tau)\bigr)\,d\tau

  2. Applying the Fundamental Theorem of Calculus to the left-hand side gives the exact integral form. There is still no approximation:

    y(tk+1)=y(tk)+∫tktk+1f(τ,y(τ)) dτy(t_{k+1})=y(t_k)+\int_{t_k}^{t_{k+1}} f\bigl(\tau,y(\tau)\bigr)\,d\tau

  3. The full integrand is unknown because it depends on the exact solution, but its approximate values at previous nodes are known: fk−1=f(tk−1,yk−1)f_{k-1}=f(t_{k-1},y_{k-1}) and fk=f(tk,yk)f_k=f(t_k,y_k). AB2 comes from approximating f(τ,y(τ))f(\tau,y(\tau)) with those two data points.

Step 2: interpolate f with Lagrange

  1. Build the degree-1 polynomial interpolating the values fk−1f_{k-1} and fkf_k using the Lagrange basis. Since tk−tk−1=ht_k-t_{k-1}=h and tk−1−tk=−ht_{k-1}-t_k=-h, the bases are:

    Lk−1(τ)=τ−tktk−1−tk=tk−τh,Lk(τ)=τ−tk−1tk−tk−1=τ−tk−1hL_{k-1}(\tau)=\frac{\tau-t_k}{t_{k-1}-t_k}=\frac{t_k-\tau}{h},\qquad L_k(\tau)=\frac{\tau-t_{k-1}}{t_k-t_{k-1}}=\frac{\tau-t_{k-1}}{h}

  2. The Lagrange interpolant is the combination of the values with their bases. It is the line that matches the known slopes at the two nodes:

    p1(τ)=fk−1 tk−τh+fk τ−tk−1h=fk τ−tk−1h−fk−1 τ−tkhp_1(\tau)=f_{k-1}\,\frac{t_k-\tau}{h}+f_k\,\frac{\tau-t_{k-1}}{h}=f_k\,\frac{\tau-t_{k-1}}{h}-f_{k-1}\,\frac{\tau-t_k}{h}

  3. The interpolation nodes are tk−1t_{k-1} and tkt_k, but the integration interval is [tk, tk+1][t_k,\,t_{k+1}]. Extrapolating the polynomial beyond its nodes makes the method explicit.

Step 3: change of variable and integration

  1. To integrate, use the change of variable from the notes: s=τ−tks=\tau-t_k, that is, τ=tk+s\tau=t_k+s and dτ=dsd\tau=ds. When τ=tk\tau=t_k, s=0s=0; when τ=tk+1\tau=t_{k+1}, s=hs=h. Also:

    τ−tk−1=s+h,τ−tk=s\tau-t_{k-1}=s+h,\qquad \tau-t_k=s

  2. Replace f(τ,y(τ))f(\tau,y(\tau)) by the interpolant p1p_1 in the integral. With the previous change of variable, the line becomes:

    p1(tk+s)=fk s+hh−fk−1 shp_1(t_k+s)=f_k\,\frac{s+h}{h}-f_{k-1}\,\frac{s}{h}

  3. Integrate the two parts separately. The fkf_k part contributes 3h2\frac{3h}{2} and the fk−1f_{k-1} part contributes h2\frac{h}{2} with a negative sign:

    ∫0hfks+hh ds=fk1h[s22+hs]0h=3h2fk∫0hfk−1sh ds=fk−11h[s22]0h=h2fk−1\begin{aligned} \int_0^h f_k\frac{s+h}{h}\,ds&=f_k\frac{1}{h}\Bigl[\frac{s^2}{2}+hs\Bigr]_0^h=\frac{3h}{2}f_k\\ \int_0^h f_{k-1}\frac{s}{h}\,ds&=f_{k-1}\frac{1}{h}\Bigl[\frac{s^2}{2}\Bigr]_0^h=\frac{h}{2}f_{k-1} \end{aligned}

  4. Therefore, the approximate integral over the new step is:

    ∫tktk+1f(τ,y(τ)) dτ≈∫tktk+1p1(τ) dτ=h2(3fk−fk−1)\int_{t_k}^{t_{k+1}} f\bigl(\tau,y(\tau)\bigr)\,d\tau\approx\int_{t_k}^{t_{k+1}} p_1(\tau)\,d\tau=\frac{h}{2}\bigl(3f_k-f_{k-1}\bigr)

  5. Substituting into the exact integral form and using y(tk)≈yky(t_k)\approx y_k gives the two-step Adams-Bashforth formula:

    yk+1=yk+h2(3fk−fk−1)y_{k+1}=y_k+\frac{h}{2}\bigl(3f_k-f_{k-1}\bigr)

Step 4: error and order

  1. The local error is the integral of the interpolation error of p1p_1. For the linear interpolant, f(τ)−p1(τ)=f′′(ξ)2(τ−tk−1)(τ−tk)f(\tau)-p_1(\tau)=\frac{f''(\xi)}{2}(\tau-t_{k-1})(\tau-t_k); with the change of variable, (τ−tk−1)(τ−tk)=h2 s(s+1)(\tau-t_{k-1})(\tau-t_k)=h^2\,s(s+1) and ∫01s(s+1) ds=56\int_0^1 s(s+1)\,ds=\frac{5}{6}:

    ek+1=h⋅y′′′(ξ)2⋅h2⋅56=512 h3 y′′′(ξ)=O(h3)e_{k+1}=h\cdot\frac{y'''(\xi)}{2}\cdot h^2\cdot\frac{5}{6}=\frac{5}{12}\,h^3\,y'''(\xi)=\mathcal{O}(h^3)

  2. The global error loses one power when accumulating N∝1/hN\propto 1/h steps: AB2 is order 2, like Heun, but with a single new evaluation of ff per step. The numerical order estimation confirms it.

From AB2 to AB3 and AB4

The same recipe with more nodes produces the whole family: interpolating ff at tk,tk−1,tk−2t_k,t_{k-1},t_{k-2} with a quadratic polynomial and repeating steps 3-4 gives AB3 (with integrals like ∫01(s+1)(s+2)2ds=2312\int_0^1\frac{(s+1)(s+2)}{2}ds=\frac{23}{12}); with four nodes and a cubic, AB4 comes out. Each extra node raises the interpolant's degree and, with it, the method's order.

AB2, AB3 and AB4

Interpolating ff with polynomials of degree 2 and 3 over three and four previous nodes (same mechanics, longer integrals) yields AB3 and AB4:

yk+1=yk+h2(3fk−fk−1)y_{k+1}=y_k+\frac{h}{2}\bigl(3f_k-f_{k-1}\bigr)
AB2, order 2.
yk+1=yk+h12(23fk−16fk−1+5fk−2)y_{k+1}=y_k+\frac{h}{12}\bigl(23f_k-16f_{k-1}+5f_{k-2}\bigr)
AB3, order 3.
yk+1=yk+h24(55fk−59fk−1+37fk−2−9fk−3)y_{k+1}=y_k+\frac{h}{24}\bigl(55f_k-59f_{k-1}+37f_{k-2}-9f_{k-3}\bigr)
AB4, order 4.

Starting the method

An mm-step method needs mm starting values, but the IVP only provides y0y_0. The values y1,…,ym−1y_1,\dots,y_{m-1} are computed with a one-step method of the same order, so as not to pollute the error: AB2 is started with Heun (order 2) and AB4 with RK4 (order 4). The AB2 exercise shows the startup and numerically confirms order 2.