Methode van Romberg

In de numerieke wiskunde, een deelgebied van de wiskunde, is de methode van Romberg een numerieke methode voor het berekenen van een bepaalde integraal. De methode gaat uit van een reeks opeenvolgende benaderingen met behulp van de trapeziumregel, waarop dan Richardson-extrapolatie wordt toegepast als versnellingsmechanisme.

Methode

De methode benadert de integraal van de functie $f(x)$ over het interval $[a,b]$ door het interval opeenvolgend te verdelen in stappen $h_{n}$ die steeds de helft zijn van de vorige, en voor een bepaalde stapgrootte de uitgebreide trapeziumregel toe te passen. Op de zo verkregen benadering worden vervolgen successievelijke richardson-extrapolaties toegepast.

De stapgroottes vormen een rij $h_{0},h_{1},\ldots ,h_{n},\ldots$, waarvoor geldt:

$h_{0}=b-a$ en $h_{n}={\tfrac {1}{2}}h_{n-1}={\tfrac {1}{2^{n}}}(b-a)$

De trapeziumregel geeft bij de stapgrootte $h_{n}$, dus met $2^{n}$ stappen, de benadering

$R(n,0)={\tfrac {1}{2}}h_{n}(f(a)+2f(a+h_{n})+2f(a+2h_{n})+\ldots +2f(a+(2^{n}-1)h_{n})+f(b))$

In deze formule is het alleen nodig de functiewaarden te berekenen in de nieuwe punten, die midden tussen de punten in de vorige verdeling van het interval liggen.

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

Op deze benadering worden vervolgens successievelijke richardson-extrapolaties toegepast. De getallen in de meest linkse kolom zijn de resultaten van de trapeziumregel. Vervolgens wordt de driehoek vanuit deze linkerzijde horizontaal naar rechts vervolledigd door voor $m=1,\ldots n$ de bijkomende schattingen te berekenen:

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

De benaderingen met $m=1$ stemmen overeen met de regel van Simpson waarbij tussen drie opeenvolgende netpunten parabolische benaderingen geïntegreerd worden. De benaderingen met $m=12$ stemmen overeen met de regel van Boole, die door vijf opeenvolgende punten een vierde graadsveelterm aanpast en deze vervolgens integreert.

De fout in $R(n,m)$ is van de orde $O\left(h_{n}^{2m+2}\right)$.

Implementatie

Het totaal aantal evaluaties van de integrand is $2^{n}+1$. Deze geschieden allemaal bij de berekening van de linkse kolom. Het vervolledigen van de driehoek vereist geen verdere evaluaties. De Engelstalige versie van dit artikel bevat een voorbeeld van implementatie in de programmeertaal C.

Voorbeeld

Als voorbeeld wordt de functie $\sin(x)$ geïntegreerd over het interval $[0,1]$. De rechtstreeks berekende oplossing is 0,4596976941. De resultaten van de rombergintegratie zijn:

$R(n,m)$
$n$	$m=0$	$m=1$	$m=2$	$m=3$
0	0,4207354924
1	0,4500805155	0,4598621899
2	0,4573009375	0,4597077448	0,4596974485
3	0,4590989734	0,4596983187	0,4596976903	0,4596976941

Merk op dat de benadering $R(3,0)$ in feite een benadering met de trapeziumregel met 8 intervallen, slechts tot op drie cijfers correct is, terwijl de rombergmethode, met evenveel evaluaties van de integrand, 10 correcte cijfers haalt.

Referentie

• (en) S. D. Conte, C. de Boor (1981) "Elementary Numerical Analysis", McGraw-Hill International Editions
• Weisstein, Eric W. "Romberg Integration." From MathWorld--A Wolfram Web Resource