Method of Romberg

In numerical Analysis, the method of integration of Romberg is a recursive method of numerical calculation of integral, based on the application of the process of Extrapolation of Richardson to the Méthode of the trapezoids. This technique of acceleration makes it possible to improve the order of convergence of the method of the trapezoids, by applying the latter to successive dyadic divisions of the interval of study and by forming some a judicious combination.

Principle

One wishes to calculate the integral $I\; =\; \backslash \; int\_a^b\; F\; (X)\; \backslash ,\; dx$ of a function F , continues on $$. One subdivides then $$ in identical N subintervals (even N , $n\; =\; 2^p$ for example), of the $type\; +\; K\; H,\; has\; +\; (k+1)\; h$ for $k\; =\; 0,\dots ,\; n-1$ and $h=\; (Ba)\; /n$. On this regular grid, the Méthode of the trapezoids is defined, noted T (H) :

$T\; (H)\; =\; \backslash \; frac\; \{H\}\; \{2\}\; \backslash \; left\; \backslash \; omega\_i\; F\; (+\; K\; H\; has)\; \backslash \; right$

where weightings $\backslash \; omega\_i$ are equal to 1 for the extreme points, and to 2 for the others. Then, the made error, noted $E\; =\; I-T\; (H)\; \backslash ,$, checks

$E\; (H)\; =\; c\_1\; h^2\; +\; c\_2\; h^4\; +\; c\_3\; h^6\; \backslash \; cdots$

This relation expresses the fact that the method of the trapezoid presents an error proportional to $h^2$; it is said that it is of order $O\; (h^2)$.

Algebraic handling provides an approximation of $I$ of order $O\; (h^4)$. It is with this intention enough to eliminate the term in $h^2$ in the development from the error. One reaches that point while considering rather the quantity T (H) - T (2h) /3 , which is anything else only the Méthode of Simpson. The same process can be taken back, in order to cancel the terms in $h^4,\; h^8,\; \backslash \; ldots$ which correspond to increasingly precise approximations of $I$.

Algorithm

We will formalize the preceding technique of reduction of the error. One notes by R (K, H) the approximation of $I$ to the K ème stage, with a grid of step H . One passes then from the stage K at the stage k+1 while posing

$R\; (k+1,\; H)\; =\; \backslash \; frac\; \{1\}\; \{4^\; \{k+1\}\; -\; 1\}\; \backslash \; times\; \backslash \; left\; 4^\; \{k+1\}\; R\; (K,\; H)\; -\; R\; (K,\; 2h)\; \backslash \; right$

One initializes the algorithm with the method of the trapezoid; in other words, R (0, H) = T (H) . One shows by recurrence that the approximation with the K ème stage, R (K, H) , provides an approximation of $I$ which is $O\; (k^\; \{2k+2\})$.

The algorithm can be represented in the shape of a table; in order to facilitate this representation, it is convenient to replace the $h\; term\; =\; (Ba)\; /2^p$ by p directly. The first diagonal, noted R (K) , corresponds to the successive approximations, while the first line represents the method of the trapezoid, the second the method of Simpson, etc One moves inside the table using the formula of preceding recurrence. In practice, to obtain an approximation of $I$ on the level $\backslash \; epsilon>0$, one fixes oneself as criterion of stop that the absolute value between two successive approximations is smaller than $\backslash \; epsilon$. This generally implies that .

Example

To integrate $f\; (T)\; =\; 2\; (1\; +\; 4t^2)\; \backslash ,$ on ''. One finds $I\; =\; \backslash \; arctan\; (4)\; +\; \backslash \; arctan\; (2)\; \backslash \; simeq\; 2,432966381462123$. The matrix of the algorithm is

from where the consecutive approximations are drawn

See too

• Method of the trapezoids
• Method of Simpson
• Extrapolation of Richardson

External bond

• In English: http://dmpeli.math.mcmaster.ca/Matlab/Math4Q3/NumMethods/Lecture3-5.html

Random links:

Julien Maitron | Josat | Ferzan Özpetek | Frans Bonduel | Pierre Grivolas | Geombinatorics

© 2007-2008 speedlook.com; article text available under the terms of GFDL, from fr.wikipedia.org