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 $\left[a,b\right]$,

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

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.