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