Romberg's method

Romberg's method

In numerical analysis, Romberg's method Harv|Romberg|1955 generates a triangular array consisting of numerical estimates of the definite integral

: int_a^b f(x) , dx

by using Richardson extrapolation Harv|Richardson|1910 repeatedly on the trapezium rule. Romberg's method evaluates the integrand at equally-spaced points.The integrand must have continuous derivatives, though fairly good resultsmay be obtained if only a few derivatives exist.If it is possible to evaluate the integrand at unequally-spaced points, then other methods such as Gaussian quadrature and Clenshaw–Curtis quadrature are generally more accurate.

Method

The method can be defined inductively in this way:

:R(0,0) = frac{1}{2} (b-a) (f(a) + f(b))

:R(n,0) = frac{1}{2} R(n-1,0) + h_n sum_{k=1}^{2^{n-1 f(a + (2k-1)h_n)

:R(n,m) = R(n,m-1) + frac{1}{4^m-1} (R(n,m-1) - R(n-1,m-1))or:R(n,m) = frac{1}{4^m-1} ( 4^m R(n,m-1) - R(n-1,m-1))

where

: n ge 1

: m ge 1

: h_n = frac{b-a}{2^n}.

In big O notation, the error for "R"("n","m") is:

: Oleft(h_n^{2^{m+1 ight).

The zeroeth extrapolation, R(n,0), is equivalent to the Trapezoidal Rule with 2^{n-1}+1 points; the first extrapolation, R(n,1), is equivalent to Simpson's rule with 2^{n-1}+1 points.

When function evaluations are expensive, it may be preferable to replace the polynomial interpolation of Richardson with the rational interpolation proposed by Harvtxt|Bulirsch|Stoer|1967.

Python implementation of Romberg's method

Here is an implementation of Romberg's method in Python.

from math import sqrt, exp

def print_row(lst): print ' '.join('%11.8f' % x for x in lst)

def romberg(f, a, b, eps=1e-8): """Approximate the definite integral of f from a to b by Romberg's method. eps is the desired accuracy.""" R = 0.5 * (b - a) * (f(a) + f(b)) # R [0] [0] print_row(R [0] ) n = 1 while True: h = float(b - a) / 2 ** n R.append( [None] * (n + 1)) # Add an empty row. # for proper limits R [n] [0] = 0.5*R [n-1] [0] + h*sum(f(a+(2*k-1)*h) for k in xrange(1, 2**(n-1)+1)) for m in xrange(1, n+1): R [n] [m] = R [n] [m-1] + (R [n] [m-1] - R [n-1] [m-1] ) / (4 ** m - 1) print_row(R [n] ) if abs(R [n] [n-1] - R [n] [n] ) < eps: return R [n] [n] n += 1

# In this example, the error function erf(1) is evaluated.print romberg(lambda t: 2 / sqrt(pi) * exp(-t * t), 0, 1)

Example

As an example, the Gaussian function is integrated from 0 to 1, i.e.the Error function { m erf}(1)doteq 0.842700792949715.The triangular array is calculated row by row and calculation is terminatedif the two last entries in the last row differ less than 1E-8.

0.77174333 0.82526296 0.84310283 0.83836778 0.84273605 0.84271160 0.84161922 0.84270304 0.84270083 0.84270066 0.84243051 0.84270093 0.84270079 0.84270079 0.84270079

The result in the lower right corner of the triangular array is accurate to the digits shown.It is remarkable that this result is derived from the less accurate approximationsobtained by the trapezium rule in the first column of the triangular array.

References

*
*
*
*
*
*

External links

* [http://www.mathworks.com/matlabcentral/fileexchange/loadFile.do?objectId=34&objectType=file ROMBINT] -- code for MATLAB (author: Martin Kacenak)
* [http://math.fullerton.edu/mathews/n2003/RombergMod.html Module for Romberg Integration]


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • Romberg — is a German surname which may refer to:* Andreas Romberg (1767 – 1821), German composer, violinist * Bernhard Romberg (1767–1841), German cellist and composer * Brett Romberg (born 1979), American football player * Moritz Heinrich Romberg… …   Wikipedia

  • Method (music) — In music, a method is a kind of textbook for a specified musical instrument or a selected problem of playing a certain instrument. A method usually contains fingering charts or tablatures, etc., scales and numerous different exercises, sometimes… …   Wikipedia

  • Método de Romberg — En análisis numérico, el Método de Romberg genera una matriz triangular cuyos elementos son estimaciones numéricas de la integral definida siguiente: usando la extrapolación de Richardson de forma reiterada en la regla del trapecio. El método de… …   Wikipedia Español

  • Adaptive Simpson's method — Adaptive Simpson s method, also called adaptive Simpson s rule, is a method of numerical integration proposed by William M. McKeeman in 1962.William M. McKeeman: Algorithm 145: Adaptive numerical integration by Simpson s rule. Commun. ACM 5(12):… …   Wikipedia

  • Integral — This article is about the concept of integrals in calculus. For the set of numbers, see integer. For other uses, see Integral (disambiguation). A definite integral of a function can be represented as the signed area of the region bounded by its… …   Wikipedia

  • List of numerical analysis topics — This is a list of numerical analysis topics, by Wikipedia page. Contents 1 General 2 Error 3 Elementary and special functions 4 Numerical linear algebra …   Wikipedia

  • List of mathematics-based methods — This is a list of mathematics based methods, by Wikipedia page.See also list of graphical methods.*Adams method (differential equations) *Akra Bazzi method (asymptotic analysis) *Condorcet method (voting systems) *Coombs method (voting systems)… …   Wikipedia

  • List of mathematics articles (R) — NOTOC R R. A. Fisher Lectureship Rabdology Rabin automaton Rabin signature algorithm Rabinovich Fabrikant equations Rabinowitsch trick Racah polynomials Racah W coefficient Racetrack (game) Racks and quandles Radar chart Rademacher complexity… …   Wikipedia

  • Simpson's rule — can be derived by approximating the integrand f (x) (in blue) by the quadratic interpolant P (x) (in red). In numerical analysis, Simpson s rule is a method for numerical integration, the numerical approximation of definite integrals.… …   Wikipedia

  • Adaptive stepsize — is a technique in numerical analysis used for many problems, but mainly for integration; This can be normal integration (that is quadrature ), or the process of solving an ordinary differential equation. This article focuses on the latter. For an …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”