Editing Romberg's method (section)

== Method ==
Using <math display="inline">h_n = \frac{(b-a)}{2^n}</math>, the method can be inductively defined by
<math display="block">\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}</math>
where <math> n \ge m </math> and <math> m \ge 1 \, </math>. 
In [[big O notation]], the error for ''R''(''n'',&nbsp;''m'') is:<ref>{{Harvnb|Mysovskikh|2002}}</ref> <math> O\left(h_n^{2m+2}\right).</math>

The zeroeth extrapolation, {{math|''R''(''n'', 0)}}, is equivalent to the [[trapezoidal rule]] with {{math|2<sup>''n''</sup> + 1}} points; the first extrapolation, {{math|''R''(''n'', 1)}}, is equivalent to [[Simpson's rule]] with {{math|2<sup>''n''</sup> + 1}} points. The second extrapolation, {{math|''R''(''n'', 2)}}, is equivalent to [[Boole's rule]] with {{math|2<sup>''n''</sup> + 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 <math display="inline">O(h^2)</math> approximations as <math display="inline">A_0\big(\frac{h}{2^n}\big)</math> instead of <math display="inline">R(n,0)</math>, we can perform Richardson extrapolation with the error formula defined below:
<math display="block"> \int_a^b f(x) \, dx = A_0\bigg(\frac{h}{2^n}\bigg)+a_0\bigg(\frac{h}{2^n}\bigg)^{2} + a_1\bigg(\frac{h}{2^n}\bigg)^{4} + a_2\bigg(\frac{h}{2^n}\bigg)^{6} + \cdots </math>
Once we have obtained our <math display="inline">O(h^{2(m+1)})</math> approximations <math display="inline">A_m\big(\frac{h}{2^n}\big)</math>, we can label them as <math display="inline">R(n,m)</math>.

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