Numerical Analysis/Romberg's method

Romberg's method approximates a definite integral by applying Richardson extrapolation to the results of either the trapezoid rule or the midpoint rule.

The initial approximations $R_{k,0}$ are obtained by applying either the trapezoid or midpoint rule with $2^k+1$ points. In the case of the trapezoid rule on $[a,b]$,

$R_{k,0}=h_k(\frac{f(a)+f(b)}{2}+\sum _{i=1}^{2^k-1}f(a+h_{k}i))$

where

$h_k=\frac{b-a}{2^k}$

For $k>0$, we can reduce the number of places the function is evaluated by using our previously obtained approximations instead of re-sampling. For the trapezoid rule, this improvement gives

$R_{0,0}=\left(\frac{b-a}{2}\right)[f(a)+f(b)]$

and

$R(k,0)=\frac{1}{2}R(k-1,0)+h_k\sum _{i=1}^{2^{k-1}}f(a+(2i-1)h_k)$

Richardson's extrapolation is then applied recursively, giving

$R_{k,j}=\frac{4^j{R}_{k,j-1}-R_{k-1,j-1}}{4^j-1}$

Each successive level of improvement increases the order of error term from $O(h^{2j})$ to $O(h^{2j+2})$ at the expense of doubling the number of places the function is evaluated.