Romberg's method

Using $h\_n\; =\; \backslash frac\{(b-a)\}\{2^n\}$, the method can be inductively defined by

$$\backslash begin\{align\}$$

R(0,0) &= h_0 (f(a) + f(b)) \\

R(n,0) &= \tfrac{1}{2} R(n-1,0) + 2h_n \sum_{k=1}^{2^{n-1}} f(a + (2k-1)h_{n-1}) \\

R(n,m) &= R(n,m-1) + \tfrac{1}{4^m-1} (R(n,m-1) - R(n-1,m-1)) \\

&= \frac{1}{4^m-1} ( 4^m R(n,m-1) - R(n-1, m-1))

\end{align}

where $n\; \backslash ge\; m$ and $m\; \backslash ge\; 1\; \backslash ,$.

In big O notation, the error for R(n, m) is:{{Harvnb|Mysovskikh|2002}} $O\backslash left(h\_n^\{2m+2\}\backslash right).$

The zeroeth extrapolation, {{math|R(n, 0)}}, is equivalent to the trapezoidal rule with {{math|2ⁿ + 1}} points; the first extrapolation, {{math|R(n, 1)}}, is equivalent to Simpson's rule with {{math|2ⁿ + 1}} points. The second extrapolation, {{math|R(n, 2)}}, is equivalent to Boole's rule with {{math|2ⁿ + 1}} points. The further extrapolations differ from Newton-Cotes formulas. In particular further Romberg extrapolations expand on Boole's rule in very slight ways, modifying weights into ratios similar as in Boole's rule. In contrast, further Newton-Cotes methods produce increasingly differing weights, eventually leading to large positive and negative weights. This is indicative of how large degree interpolating polynomial Newton-Cotes methods fail to converge for many integrals, while Romberg integration is more stable.

By labelling our $O(h^2)$ approximations as $A\_0\backslash big(\backslash frac\{h\}\{2^n\}\backslash big)$ instead of $R(n,0)$, we can perform Richardson extrapolation with the error formula defined below:

$$\backslash int\_a^b\; f(x)\; \backslash ,\; dx\; =\; A\_0\backslash bigg(\backslash frac\{h\}\{2^n\}\backslash bigg)+a\_0\backslash bigg(\backslash frac\{h\}\{2^n\}\backslash bigg)^\{2\}\; +\; a\_1\backslash bigg(\backslash frac\{h\}\{2^n\}\backslash bigg)^\{4\}\; +\; a\_2\backslash bigg(\backslash frac\{h\}\{2^n\}\backslash bigg)^\{6\}\; +\; \backslash cdots$$

Once we have obtained our $O(h^\{2(m+1)\})$ approximations $A\_m\backslash big(\backslash frac\{h\}\{2^n\}\backslash big)$, we can label them as $R(n,m)$.

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}}.

To estimate the area under a curve the trapezoid rule is applied first to one-piece, then two, then four, and so on.

File:One-piece Trapezoid Approximation.svg

File:Two-piece Trapezoid Approximation.svg

File:Four-piece Trapezoid Approximation.svg

File:Eight-piece Trapezoid Approximation.svg

After trapezoid rule estimates are obtained, Richardson extrapolation is applied.

• For the first iteration the two piece and one piece estimates are used in the formula {{math|{{sfrac|4 × (more accurate) − (less accurate)|3}}}}. The same formula is then used to compare the four piece and the two piece estimate, and likewise for the higher estimates
• For the second iteration the values of the first iteration are used in the formula {{math|{{sfrac|16 × (more accurate) − (less accurate)|15}}}}
• The third iteration uses the next power of 4: {{math|{{sfrac|64 × (more accurate) − (less accurate)|63}}}} on the values derived by the second iteration.
• The pattern is continued until there is one estimate.

{{Table alignment}}

class="wikitable col1right col2right"
Number of pieces || Trapezoid estimates || First iteration || Second iteration || Third iteration
		{{math|1={{sfrac|4 {{abbr|MA|more accurate}} − {{abbr|LA|less accurate}}|3}}}}	{{math|1={{sfrac|16 MA − LA|15}}}}	{{math|1={{sfrac|64 MA − LA|63}}}}
1	0	{{math|1={{sfrac|4×16 − 0|3}} = 21.333...|size=90%}}	{{math|1={{sfrac|16×34.667 − 21.333|15}} = 35.556...|size=90%}}	{{math|1={{sfrac|64×42.489 − 35.556|63}} = 42.599...|size=90%}}
2	16	{{math|1={{sfrac|4×30 − 16|3}} = 34.666...|size=90%}}	{{math|1={{sfrac|16×42 − 34.667|15}} = 42.489...|size=90%}}
4	30	{{math|1={{sfrac|4×39 − 30|3}} = 42|size=90%}}
8	39

As an example, the Gaussian function is integrated from 0 to 1, i.e. the error function erf(1) ≈ 0.842700792949715. The triangular array is calculated row by row and calculation is terminated if the two last entries in the last row differ less than 10⁻⁸.

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 approximations

obtained by the trapezium rule in the first column of the triangular array.

Here is an example of a computer implementation of the Romberg method (in the C programming language):

1. include
2. include

void print_row(size_t i, double *R) {

printf("R[%2zu] = ", i);

for (size_t j = 0; j <= i; ++j) {

printf("%f ", R[j]);

}

printf("\n");

}

/*

INPUT:

(*f) : pointer to the function to be integrated

a : lower limit

b : upper limit

max_steps: maximum steps of the procedure

acc : desired accuracy

OUTPUT:

Rp[max_steps-1]: approximate value of the integral of the function f for x in [a,b] with accuracy 'acc' and steps 'max_steps'.

• /

double romberg(double (*f)(double), double a, double b, size_t max_steps, double acc)

{

double R1[max_steps], R2[max_steps]; // buffers

double *Rp = &R1[0], *Rc = &R2[0]; // Rp is previous row, Rc is current row

double h = b-a; //step size

Rp[0] = (f(a) + f(b))*h*0.5; // first trapezoidal step

print_row(0, Rp);

for (size_t i = 1; i < max_steps; ++i) {

h /= 2.;

double c = 0;

size_t ep = 1 << (i-1); //2^(n-1)

for (size_t j = 1; j <= ep; ++j) {

c += f(a + (2*j-1) * h);

}

Rc[0] = h*c + .5*Rp[0]; // R(i,0)

for (size_t j = 1; j <= i; ++j) {

double n_k = pow(4, j);

Rc[j] = (n_k*Rc[j-1] - Rp[j-1]) / (n_k-1); // compute R(i,j)

}

// Print ith row of R, R[i,i] is the best estimate so far

print_row(i, Rc);

if (i > 1 && fabs(Rp[i-1]-Rc[i]) < acc) {

return Rc[i];

}

// swap Rn and Rc as we only need the last row

double *rt = Rp;

Rp = Rc;

Rc = rt;

}

return Rp[max_steps-1]; // return our best guess

}

Here is an implementation of the Romberg method (in the Python programming language):

def print_row(i, R):

"""Prints a row of the Romberg table."""

print(f"R[{i:2d}] = ", end="")

for j in range(i + 1):

print(f"{R[j]:f} ", end="")

print()

def romberg(f, a, b, max_steps, acc):

"""

Calculates the integral of a function using Romberg integration.

Args:

f: The function to integrate.

a: Lower limit of integration.

b: Upper limit of integration.

max_steps: Maximum number of steps.

acc: Desired accuracy.

Returns:

The approximate value of the integral.

"""

R1, R2 = [0] * max_steps, [0] * max_steps # Buffers for storing rows

Rp, Rc = R1, R2 # Pointers to previous and current rows

h = b - a # Step size

Rp[0] = 0.5 * h * (f(a) + f(b)) # First trapezoidal step

print_row(0, Rp)

for i in range(1, max_steps):

h /= 2.0

c = 0

ep = 2 ** (i - 1)

for j in range(1, ep + 1):

c += f(a + (2 * j - 1) * h)

Rc[0] = h * c + 0.5 * Rp[0] # R(i,0)

for j in range(1, i + 1):

n_k = 4**j

Rc[j] = (n_k * Rc[j - 1] - Rp[j - 1]) / (n_k - 1) # Compute R(i,j)

# Print ith row of R, R[i,i] is the best estimate so far

print_row(i, Rc)

if i > 1 and abs(Rp[i - 1] - Rc[i]) < acc:

return Rc[i]

# Swap Rn and Rc for next iteration

Rp, Rc = Rc, Rp

return Rp[max_steps - 1] # Return our best guess

{{sfn whitelist|CITEREFMysovskikh2002}}

{{reflist}}

{{refbegin}}

• {{citation|last1=Richardson|first1=L. F.| authorlink=Lewis Fry Richardson| title=The Approximate Arithmetical Solution by Finite Differences of Physical Problems Involving Differential Equations, with an Application to the Stresses in a Masonry Dam |journal= Philosophical Transactions of the Royal Society A |volume=210|issue=459–470|year=1911|pages=307–357|doi=10.1098/rsta.1911.0009|jstor=90994|doi-access=|bibcode=1911RSPTA.210..307R }}
• {{citation|last1=Romberg|first1=W. |title=Vereinfachte numerische Integration |journal=Det Kongelige Norske Videnskabers Selskab Forhandlinger|volume=28|year=1955 |location=Trondheim|pages=30–36|issue=7}}
• {{citation|last=Thacher Jr.|first=Henry C. | title=Remark on Algorithm 60: Romberg integration|journal=Communications of the ACM|volume=7|pages =420–421|date=July 1964|doi=10.1145/364520.364542 |issue=7|doi-access=free}}
• {{citation|last1=Bauer|first1=F.L. |last2=Rutishauser |last3=Stiefel|first3=E. |title=New aspects in numerical quadrature|editor-last=Metropolis|editor-first=N. C.|journal=Experimental Arithmetic, High-speed Computing and Mathematics, Proceedings of Symposia in Applied Mathematics| publisher=AMS | year=1963| pages=199–218 |first2=H.|issue=15| display-editors=etal}}
• {{citation|last1=Bulirsch|first1=Roland| last2=Stoer|first2=Josef|title= Handbook Series Numerical Integration. Numerical quadrature by extrapolation |journal=Numerische Mathematik|volume=9 |year=1967|pages=271–278 |url=http://www-gdz.sub.uni-goettingen.de/cgi-bin/digbib.cgi?PPN362160546_0009 |doi=10.1007/bf02162420|url-access=subscription}}
• {{SpringerEOM|last=Mysovskikh|first=I.P. |title=Romberg method|editor-last=Hazewinkel|editor-first=Michiel |publisher=Springer-Verlag |year=2002 |isbn=1-4020-0609-8}}
• {{Citation |last1=Press|first1=WH | last2=Teukolsky|first2=SA | last3=Vetterling|first3=WT | last4=Flannery|first4=BP | year=2007 |title=Numerical Recipes: The Art of Scientific Computing|edition=3rd | publisher=Cambridge University Press| publication-place=New York| isbn=978-0-521-88068-8 |chapter=Section 4.3. Romberg Integration|chapter-url=http://apps.nrbook.com/empanel/index.html?pg=166}}

{{refend}}

• [http://www.mathworks.com/matlabcentral/fileexchange/loadFile.do?objectId=34&objectType=file ROMBINT] – code for MATLAB (author: Martin Kacenak)
• [http://www.hvks.com/Numerical/webintegration.html Free online integration tool using Romberg, Fox–Romberg, Gauss–Legendre and other numerical methods]
• [https://docs.scipy.org/doc/scipy/reference/generated/scipy.integrate.romberg.html SciPy implementation of Romberg's method]
• [https://github.com/fgasdia/Romberg.jl Romberg.jl] — Julia implementation (supporting arbitrary factorizations, not just $2^n+1$ points)

{{Numerical integration}}

Category:Numerical integration

Category:Articles with example C code