DerivationDifferentiationadvanced

Derivation: Richardson raises the order

From the error form to the extrapolation formula: why combining $N_1(h)$ and $N_1(h/2)$ removes the $\mathcal{O}(h)$ term.

Eliminating the O(h) term

Start from the all-powers error and also evaluate with step $h/2$ :
$\begin{aligned} M&=N_1(h)+k_1 h+k_2 h^2+\cdots\\ M&=N_1\!\left(\tfrac{h}{2}\right)+k_1\tfrac{h}{2}+k_2\tfrac{h^2}{4}+\cdots \end{aligned}$
Compute $2\cdot(\text{second})-(\text{first})$ . The $k_1h$ term cancels and an $\mathcal{O}(h^2)$ error remains:
$M=N_1\!\left(\tfrac{h}{2}\right)+\left[N_1\!\left(\tfrac{h}{2}\right)-N_1(h)\right]-k_2\tfrac{h^2}{2}-\cdots$
Call the known part $N_2(h)$ : it is an order-2 approximation. Repeating with weights $\tfrac13$ , $\tfrac{1}{15}$ , … raises the order further.
$N_2(h)=N_1\!\left(\tfrac{h}{2}\right)+\left[N_1\!\left(\tfrac{h}{2}\right)-N_1(h)\right]$