Romberg's method
|
In numerical analysis, Romberg's method generates a triangular array consisting of numerical estimates of the definite integral
- <math> \int_a^b f(x) \, dx. <math>
by using Richardson extrapolation repeatedly on the trapezium rule.
The method can be defined inductively in this way:
- <math>R(0,0) = \frac{1}{2} (b-a) (f(a) + f(b))<math>
- <math>R(n,0) = \frac{1}{2} R(n-1,0) + h\sum_{k=1}^{2^{n-1}} f(a + (2k-1)h)<math>
- <math>R(n,m) = R(n,m-1) + \frac{1}{4^m-1} (R(n,m-1) - R(n-1,m-1))<math>
where
- <math> n \ge 1 <math>
- <math> m \ge 1 <math>
- <math> h = \frac{b-a}{2^n}. <math>
In big O notation, the error for R(n,m) is:
- <math> O\left(h^{2^{m+1}}\right). <math>