Romberg's method

The Romberg integration is a method for the numerical determination of integrals and was developed by Werner Romberg. It is an improvement of ( tendons ) trapezoidal rule by extrapolation.

Basic idea

The Romberg integration is based on the Richardson extrapolation to the limit over the increment of a summed quadrature formula, such as the trapezoidal rule. The trapezoidal rule here is particularly worthy of mention, as it is easy to calculate and also has a development in powers of the square of the step size, so an extrapolation into squares of the increment is possible that converges much faster than the simple extrapolation to the limit. With step size h is meant here in the trapezoidal rule, the width of the trapezoids.

The time-consuming part of the numerical integration are often the function evaluations. To keep the number of minimal, it is therefore advisable to choose a step-size gradient, which allows the re-use of already calculated function values. An example of such an increment would be that at the same time meets the conditions for a convergent extrapolation. so

In this so-called Romberg result, the number of required function evaluations for large n is growing rapidly, which is not always desirable.

To remedy this, the Bulirsch sequence can be used:

Here are links with interposed.

Computation rule

With

Is

And

The error term is equal to:

Method

Thus, the calculation starts ( Romberg sequence) as follows:

  • Calculating according to the trapezoidal rule
  • Major cycle start with n = 1
  • Calculating according to the trapezoidal rule (2 intervals ). It has to be recalculated only the central function value:
  • Sub-cycle: k is 2 to 2
  • New crossing of the main cycle with n = 2
  • Calculating according to the trapezoidal rule (4 intervals, two new function values).
  • Sub-cycle k is 2 to 3
  • And
  • And
  • New crossing of the main cycle with n = third
  • Calculating according to the trapezoidal rule ( 8 intervals, 4 new function values ​​).
  • Sub-cycle k is 2 to 4
  • And
  • And
  • And
  • New crossing of the main cycle with n = 4

Comments

Falling below the error bound defined here does not always mean that the integral has been calculated correctly. This applies particularly to periodic functions, and functions with a periodic component. Thus, for example, which occurs in the Fourier analysis of periodic functions integral

May cause an error if you do not calculate at least n 1 levels of integration. In the first n levels of integration all support points coincide with the zeros of the function. As an integral one, therefore, always has the value zero, regardless of whether it's true or not. A computer program should enforce a minimum number of integration steps so always.

Conclusion

The great advantage of Romberg quadrature over other methods is the ability to control the error in arrears and reuse already achieved results, if the precision is not reached.

Richardson-Extrapolation Approximation error Yacas
691563
de