Mètode de Romberg

De Viquipèdia

En càlcul numèric, el mètode de Romberg (Romberg 1955) genera una taula triangular que consisteix en estimacions numèriques de la integral definida

$\int_a^b f(x) \, dx$

A base d’utilitzar la extrapolació de Richardson (Richardson 1910) repetidament sobre el el mètode trapezial. El mètode de Romberg avalua l’integrand a punts equidistants. L’integrand ha de tenir derivades contínues tot i que es poden obtenir força bons resultats encara que només existeixin unes quantes derivades. Si és posible avaluar l’integrand en punts desigualment espaiats, llavors altres mètodes com la quadratura de Gauss i la quadratura de Clenshaw-Curtis són, en general, més exactes.

Taula de continguts

1 Mètode
2 Implementació del mètode de Romberg en Pyton
3 Exemple
4 Referències
5 Enllaços externs

[edita] Mètode

El mètode es pot definir per inducció així:

$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))$

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

$n \ge 1$

$m \ge 1$

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

En notació de Landau, l’error de R(n,m) és:

$O\left(h_n^{2^{m+1}}\right).$

La primera extrapolació, $R (n,1)$ , és equivalent al mètode de Simpson amb $n + 2$ points.

Quan les avaluacions de la funció són costoses en termes computacionals, pot ser preferible substituir la interpolació polinòmica de Richardson per la interpolació racional proposada per Plantilla:Harvtxt.

[edita] Implementació del mètode de Romberg en Pyton

Aquesta és una implementació del mètode de Romberg en Python.

def imprimeix_fila(lst):
    print ' '.join('%11.8f' % x for x in lst)
 
def romberg(f, a, b, eps = 1E-8):
    """Approxima la integral definida de f des de a fins a b pel mètode de Romberg.
    eps és la precisió desitjada."""
    R = [[0.5 * (b - a) * (f(a) + f(b))]]  # R[0][0]
    Imprimeix_fila(R[0])
    n = 1
    while True:
        h = float(b-a)/2**n
        R.append((n+1)*[None])  # Afegeix una fila buida.
        R[n][0] = 0.5*R[n-1][0] + h*sum(f(a+(2*k-1)*h) for k in range(1, 2**(n-1)+1)) # per limits adequats
        for m in range(1, n+1):
            R[n][m] = R[n][m-1] + (R[n][m-1] - R[n-1][m-1]) / (4**m - 1)
        Imprimeix_fila(R[n])
        if abs(R[n][n-1] - R[n][n]) < eps:
            return R[n][n]
        n += 1
 
from math import *
 
# En aquest exemple s’avalua la funció error erf(1).
print romberg(lambda t: 2/sqrt(pi)*exp(-t*t), 0, 1)

[edita] Exemple

Com a exemple s’intega la funció de Gauss des de 0 fins a 1, es a dir la funció error ${\rm erf}(1)\doteq 0.842700792949715$ . La taula triangular es calcula file per fila i el càlcul s’acaba si els dos útims nombres de la última fila defereixen menys de 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

El resultat de la cantonada de baix a la dreta de la taula triangular és exacte en tots els dígits que es presenten. És notable que aquest resultat s’ha obtingut a partir de les menys exactes aproximacions obtingudes pel mètode trapezial de la primera columna de la taula triangular.

[edita] Referències

Richardson, L. F. (1911), "The Approximate Arithmetical Solution by Finite Differences of Physical Problems Involving Differential Equations, with an Application to the Stresses in a Masonry Dam", Philosophical Transactions of the Royal Society of London. Series A 210: pp. 307–357, <http://links.jstor.org/sici?sici=0264-3952(1911)210%3C307%3ATAASBF%3E2.0.CO%3B2-J>
Romberg, W. (1955), "Vereinfachte numerische Integration", Norske Videnskabers Selskab Forhandlinger (Trondheim) 28 (7): pp. 30–36
Thacher, Jr., Henry C. (1964), "Remark on Algorithm 60: Romberg integration", Communications of the ACM 7 (7): 420-421, <http://portal.acm.org/citation.cfm?id=364520.364542>
Bauer, F.L.; Rutishauser & Stiefel, E. (1963), Metropolis, N. C., et al., ed., "New aspects in numerical quadrature", Experimental Arithmetic, high-speed computing and mathematics, Proceedings of Symposia in Applied Mathematics (AMS) (no. 15): pp. 199–218
Bulirsch, Roland & Stoer, Josef (1967), "Handbook Series Numerical Integration. Numerical quadrature by extrapolation", Numerische Mathematik 9: 271–278, <http://www-gdz.sub.uni-goettingen.de/cgi-bin/digbib.cgi?PPN362160546_0009>
Mysovskikh, I.P. (2002), "Romberg method", in Hazewinkel, Michiel, Encyclopaedia of Mathematics, Springer-Verlag, ISBN 1-4020-0609-8, <http://eom.springer.de/r/r082570.htm>

[edita] Enllaços externs

ROMBINT -- code for MATLAB (author: Martin Kacenak)
Romberg's method is implemented in Maxima CAS
ROMBERG -- c++ code for romberg integration
Module for Romberg Integration
Romberg's method -- plugin for Yacas

Integració

Càlcul de primitives
$\int_a^b f(x)\,dx$ Integració simbòlica · Integral de Gauß · Integral no elemental · Constant d’integració · Algorisme de Risch · Funcions elementals · Teorema de Fubini · Mètode d'exhaustió
De fraccions racionals · Per canvi de variable · Per parts · Per substitució trigonomètrica · Per sèries · Integral de la secant al cub
Taules d'integrals
Integrals de funcions racionals · Integrals de funcions irracionals · Integrals de funcions exponencials · Integrals de funcions logarítmiques · Integrals de funcions trigonomètriques · Integrals inverses de funcions trigonomètriques · Integrals de funcions hiperbòliques · Integrals de funcions inverses de les funcions hiperbòliques
Definicions d'integració
Integral de Bochner · Integral de Darboux · Integral de Henstock-Kurzwe · Integral de Lebesgue · Integral de Lebesgue-Stieltjes · Sumatori de Riemann · Integral de Riemann · Integral de Riemann-Stieltjes
Extensions de la integral
Integral impròpia · Integral múltiple · Integral multiplicativa · Integral de superfície · Integral curvilínia · Teorema de Fubini
Integració numèrica
Mètode de Simpson · Mètode trapezial · Mètode rectangular · Mètode de Romberg · Integració de Montecarlo · Fórmules de Newton-Cotes · Sumatori de Riemann · Quadratura de Gauss · Quadratura adaptativa

Categoria: Integració numèrica

Mètode de Romberg

De Viquipèdia

Taula de continguts

[edita] Mètode

[edita] Implementació del mètode de Romberg en Pyton

[edita] Exemple

[edita] Referències

[edita] Enllaços externs

Views

Navegació

comunitat

Cerca

En altres llengües