Romberg integration

from Wikipedia, the free encyclopedia

The Romberg integration is a method for the numerical determination of integrals and was developed by Werner Romberg in 1955. It is an improvement of the (tendon) trapezoid rule through extrapolation .

Basic idea

The Romberg integration is based on the Richardson extrapolation to the Limes over the step size of a summed quadrature formula, such as the trapezoidal rule . The trapezoidal rule is particularly worth mentioning here because it is easy to calculate and also has a development in quadratic powers of the step size, i.e. an extrapolation in squares of the step size is possible, which converges significantly faster than the simple extrapolation to the limit. The step size h here means the width of the trapezoids in the trapezoid rule.

The complex part of numerical integration is often the function evaluations. In order to keep their number to a minimum, it is therefore advisable to choose a step size curve that allows the further use of function values ​​that have already been calculated. An example of such a step size would be that also fulfills the conditions for a convergent extrapolation. So

With this so-called Romberg sequence , the number of function evaluations required increases rapidly with large n, which is not always desirable.

The Bulirsch sequence can also be used to remedy this :

Links are interposed here.

Calculation rule

The integral is approximated with the help of trapezoid sums with different increments . It is assumed that the limit value is met.

The calculation rule of the Romberg integration is now as follows.

  1. Find the trapezoid sums for increments . This defines
  2. The interpolation polynomial is evaluated using the Neville-Aitken scheme at

Remarks

  • The first step is to calculate the data points . Due to the asymptotic error development of the trapezoidal sum (only powers of occur), an interpolation polynomial is used for the data points in the second step .
  • In the second step, the full interpolation is not determined, but only the evaluation at a certain point: . This works particularly efficiently with the Neville-Aitken scheme .
  • The Neville-Aitken scheme provides an approximation of the integral using .
  • The Neville-Aitken scheme must be carried out in the "correct" order. The following extrapolation table should clarify this (one proceeds column-by-column: first determine the first column, then the second, etc.)

Remarks

Falling below the error limit defined here does not always mean that the integral was calculated correctly. This is especially true for periodic functions and functions with a periodic part. So z. B. the integral occurring in the Fourier analysis of periodic functions

u. This can lead to an error if at least n + 1 integration levels are not calculated. In the first n integration stages, all support points coincide with the zeros of the function. As an integral you always get the value zero, regardless of whether it is true or not. A computer program should therefore always enforce a minimum number of integration levels.

Conclusion

The great advantage of Romberg quadrature compared to other methods is the possibility of checking the error afterwards and using results that have already been achieved if the accuracy has not yet been achieved.

literature

  • Martin Hermann: Numerical Mathematics 2nd revised and expanded edition. Oldenbourg Wissenschaftsverlag, Munich et al. 2006, ISBN 3-486-57935-5 , p. 436 ff.
  • Josef Stoer: Numerical Mathematics 1 , 8th revised and expanded edition. Springer textbook, ISBN 3-540-66154-9 , pp. 161 ff.

Web links

Individual evidence

  1. ^ Romberg, Simplified Numerical Integration, Royal Norske Vid. Selsk. Forsk., Vol. 28, 1955, pp. 30-36
  2. ^ Peter Deuflhard; Folkmar Bornemann: Numerical Mathematics / 1. An algorithmic introduction. 4th, revised. and exp. Edition volume 1 . de Gruyter, Berlin, ISBN 3-11-020354-5 , p. 318 .