Romberg-módszer

A numerikus analízisben Romberg módszere létrehoz egy olyan háromszöget, amelynek minden sorában az egyes tagok a

$\int _{a}^{b}f(x)\,dx$

határozott integrálnak a numerikus közelítései. A numerikus közelítéseket a trapézszabály Richardson-extrapolációjának ismétléseivel kapjuk. Romberg módszere az integrálandó függvényt egyenlő lépésközök (másképpen ekvidisztáns pontok) segítségével számítja. Az integrálandó függvénynek folytonosnak kell lennie azokban a pontokban, ahol a függvény értékeit kiszámítjuk (azaz az alappontokban), néhány megfelelő (folytonos) pont esetén már elég jó közelítést tudunk végezni.

Ha a függvényértéket meg tudjuk határozni nem egyenlő lépésközű pontokban (azaz nem ekvidisztáns pontokban) is, akkor léteznek pontosabb módszerek is, mint például a Gauss-kvadratúra és a Clenshaw–Curtis-kvadratúra amelyek általában jobb közelítéseket adnak.

Módszer

A módszert az alábbiak szerint definiálhatjuk (és alakíthatjuk ki a „háromszöget”):

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

$R(n,0)={\frac {1}{2}}R(n-1,0)+h\sum _{k=1}^{2^{n-1}}f(a+(2k-1)h)$

Az alábbiakban látható Romberg módszerének implementációja Python programozási nyelven:

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

def romberg(f, a, b, eps = 1E-8):
    """A hatarozott integral kozelitese f fuggvennyel a-tol b-ig Romberg modszerrel.
    eps a kivant pontossag."""
    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((n+1)*[None]) # Adj hozza egy ures sort.
        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)) # a megfelelo/tiszta hatarertekek miatt ?!
        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)
        print_row(R[n])
        if abs(R[n][n-1] - R[n][n]) < eps:
            return R[n][n]
        n += 1

from math import *

# Ebben a peldaban a hibafuggveny kiertekelese, erf(1) tortent meg.
print romberg(lambda t: 2/sqrt(pi)*exp(-t*t), 0, 1)

Példa

Példaként a Gauss-függvényt 0-tól 1-ig integráltuk, ahol a Gauss-függvényhez tartozó hibafüggvény közelítése: ${\rm {erf}}(1)\doteq 0.842700792949715$. A háromszög alakot sorról sorra kiszámítva megkapjuk, hogy az utolsó sor között utolsó két értéke közötti eltérés kisebb, mint 10^-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

A háromszög jobb alsó sarkában található eredmény a kiírt tizedesjegyekig pontosnak tekinthető. Megjegyezzük, hogy az eredményt a kevésbé pontos közelítésű trapéz szabályból vezettük le, amit a háromszög első sorában alkalmaztunk.

Hivatkozások

• 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

Külső hivatkozások

• ROMBINT Archiválva 2008. június 9-i dátummal a Wayback Machine-ben -- kódolás MATLAB-ban (szerző: Martin Kacenak)
• Romberg módszerének megvalósítása Maxima CAS-ben
• ROMBERG -- c++ kódolás romberg integráláshoz
• Module for Romberg Integration
• Romberg's method -- plugin for Yacas