The error formula for the Romberg integration

Question

I am just wondering if there exists a error formula for the Romberg integration. Since it just applies Richardson extrapolation to Trapezoidal rule, is its error formula the same as that of the trapezoidal rule, which is $(b-a)^3 f^{(2)}(\sigma)/12n^2$?

Answer 1

The point of the Richardson extrapolation procedure used in Romberg integration is that you have an asymptotic expansion for the error with a step size of $h$. You then want to combine two methods with different step sizes in such a way as to cancel the leading term of this expansion. Typically the situation is like this:

$$T(h) \sim I+a_1 h^{p_1} + a_2 h^{p_2} + o(h^{p_2})$$

Hence

$$T(h/2) \sim I+2^{-p_1} a_1 h^{p_1} + 2^{-p_2} a_2 h^{p_2} + o(h^{p_2})$$

(Note that one can use, say, $h/3$ instead, but we usually use $h/2$. One reason is that if $T$ has uniformly spaced nodes, then nodes wind up shared between the two methods, which keeps the total number of nodes down.)

So you can combine these to cancel out the $h^{p_1}$ term while preserving the leading term:

$$\frac{2^{p_1} T(h/2)-T(h)}{2^{p_1}-1}=I+\frac{2^{p_1-p_2}-1}{2^{p_1}-1} a_2 h^{p_2} + o(h^{p_2})$$

So your error estimate is $\frac{2^{p_1-p_2}-1}{2^{p_1}-1} a_2 h^{p_2}$. To use it, you need to know at least $p_2$ (the new order) and preferably also $a_2$.

In the case where $T$ is the trapezoidal rule, this procedure yields the Simpson rule, and you can either compute this error term directly from the Simpson rule, or you can obtain it directly from the asymptotic expansion of the trapezoidal rule (which is a case of the Euler-Maclaurin summation formula). In any case the new method is actually of order 4, and in fact each extrapolation procedure increases the order by 2, when beginning with the trapezoidal rule. This is a special feature of the trapezoidal rule, however!

Answer 2

The error of one Richardson extrapolation of the trapezoidal rule is the error of the Simpson rule, since Simpson is the extrapolation of Richardson, $$S(n)=\dfrac13(4T(2n)-T(n))$$ for subdivisions into $n$ resp. $2n$ sub-intervals. The most important fact is that Simpson is order 4, so the error has the power $n^4$ in the denominator and $f^{(4)}(σ)$ in the numerator.

Analogously, the next extrapolation with formula $$ \frac1{15}(16·S(2n)-S(n)) $$ has error order 6 etc.