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:

$$ \begin{array}{ccccc} T _ {00} &T _ {01} &\dots &T _ {0, n- 1 } &T _ {0n} \\ T _ {10} &T _ {11} &\dots &T _ {1 , n- 1 } &{} \\ \dots &\dots &\dots &{} &{} \\ T _ {n- 2 ,0 } &T _ {n- 2 ,1 } &{T _ {n-2},2 } &{} &{} \\ T _ {n- 1 , 0 } &T _ {n- 1 ,1 } &{} &{} &{} \\ T _ {n0} &{} &{} &{} &{} \\ \end{array} $$

where in the first column one finds the quadrature sums (3) of the 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 _ {k, 0} }{3} ,\ \ k = 0 \dots n- 1 . $$

$ T _ {k1} $ turns out to be a quadrature sum of the 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