Romberg method

Romberg rule

A method for calculating a definite integral based on Richardson extrapolation. Suppose a value $I$ of some functional is to be calculated; also, let a calculated approximate value $T ( h)$ depend on a parameter $h$ so that as a result of the computations one obtains an approximate equality $I \cong T ( h)$. Let some information be known concerning the behaviour of the difference $I - T ( h)$ as a function of $h$, namely,

$$\tag{1 } I - T ( h) = \alpha h ^ {m} ,$$

where $m$ is a positive integer and $\alpha$ depends on the functional to be approximated, on the function on which this functional is calculated, on the approximating method, and (weakly) on $h$. If simultaneously with $T ( h)$, $T ( 2h)$ is calculated, then by Richardson's method one obtains for $I$ the approximation

$$\tag{2 } I \cong \ \frac{2 ^ {m} T ( h) - T ( 2h) }{2 ^ {m} - 1 } .$$

This approximation is the better, the weaker the dependence of $\alpha$ in (1) on $h$. In particular, if $\alpha$ is independent of $h$, then (2) becomes an exact equality.

Romberg's method is used to calculate an integral

$$I = \int\limits _ { 0 } ^ { 1 } f ( x) dx .$$

The interval $[ 0 , 1 ]$ is chosen to facilitate the writing; it can be any finite interval, however. Let

$$\tag{3 } T _ {k0} = 2 ^ {-} k- 1 \left [ f ( 0) + 2 \sum _ { j= } 1 ^ { {2 ^ {k}} - 1 } f ( j 2 ^ {-} k ) + f ( 1) \right ] ,$$

$$k = 0 , 1 , . . . .$$

Calculations by Romberg's method reduce to writing down the following table:

$$where in the first column one finds the quadrature sums (3) of the [[Trapezium formula|trapezium formula]]. The elements of the $ ( l+ 2 ) $- nd column are obtained from the elements of the $ ( l+ 1) $- st column by the formula$$ \tag{4 } T _ {k , l+ 1 } = \

\frac{2 ^ {2l + 2 } T _ {k+ 1 , l } - T _ {kl} }{2 ^ {2l + 2 } - 1 }

,\ \ 

k = 0 \dots n- l- 1 . $$When writing down the table, the main calculating effort is concerned with calculating the elements of the first column. The calculation of the elements of the following columns is a bit more complicated than the calculation of finite differences. Each element $ T _ {kl} $ in the table is a quadrature sum approximating the integral:$$ \tag{5 } I \cong T _ {kl} . $$The nodes of the quadrature sum $ T _ {kl} $ are the points $ j 2 ^ {-} k- l $, $ j = 0 \dots 2 ^ {k+} l $, and its coefficients are positive numbers. The quadrature formula (5) is exact for all polynomials of degree not exceeding $ 2l + 1 $. Under the assumption that the integrand has a continuous derivative on $ [ 0 , 1 ] $ of order $ 2l + 2 $, the difference $ I - T _ {kl} $ can be represented in the form (1), where $ m = 2l + 2 $. Hence it follows that the elements of the $ ( l+ 2 ) $- nd column, calculated by formula (4), are better Richardson approximations than the elements of the $ ( l+ 1 ) $- st column. In particular, the following representation is valid for the error of the quadrature trapezium formula$$ I - T _ {k0} = \ - \frac{f ^ { \prime\prime } ( \xi ) }{12}

h  ^ {2} ,\ \ 

h = 2 ^ {-} k ,\ \xi \in [ 0 , 1 ] , $$and the Richardson method provides a better approximation to $ I $:$$ T _ {k1} = \

\frac{4 T _ {k+ 1 , 0 } - T _ {k0} }{3}

,\ \ 

k = 0 \dots n- 1 . $$$ T _ {k1} $ turns out to be a quadrature sum of the [[Simpson formula|Simpson formula]], and since for the error of this formula the following representation holds:$$ I - T _ {k1} = \ - \frac{f ^ { ( iv ) } ( \eta ) }{180}

h  ^ {4} ,\ \ 

h = 2 ^ {-} k- 1 ,\ \eta \in [ 0 , 1 ] , $$

one can again use the Richardson method, etc.

In Romberg's method, to approximate $I$ one takes $T _ {0n}$; also, one assumes the continuous derivative $f ^ { ( 2n) } ( x )$ on $[ 0 , 1 ]$ to exist. A tentative idea of the precision of the approximation $T _ {0n}$ can be obtained by comparing $T _ {0n}$ to $T _ {1 , n- 1 }$.

This method was for the first time described by W. Romberg [1].

References

[1]	W. Romberg, "Vereinfachte numerische Integration" Norske Vid. Sels. Forh. , 28 : 7 (1955) pp. 30–36
[2]	F.L. Bauer, H. Rutishauser, E. Stiefel, "New aspects in numerical quadrature" N.C. Metropolis (ed.) et al. (ed.) , Experimental Arithmetic, high-speed computing and mathematics , Proc. Symp. Appl. Math. , 15 , Amer. Math. Soc. (1963) pp. 199–218