# 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 ${\displaystyle R_{k,0}}$ are obtained by applying either the trapezoid or midpoint rule with ${\displaystyle 2^{k}+1}$ points. In the case of the trapezoid rule on ${\displaystyle \left[a,b\right]}$,

${\displaystyle 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

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

For ${\displaystyle 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

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

and

${\displaystyle 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

${\displaystyle 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 ${\displaystyle O(h^{2j})}$ to ${\displaystyle O(h^{2j+2})}$ at the expense of doubling the number of places the function is evaluated.