# 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
How to Cite This Entry:
Romberg method. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Romberg_method&oldid=55131
This article was adapted from an original article by I.P. Mysovskikh (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article