The Romberg Method¶
The Romberg method generates a triangular array of approximations \(R_{i,j}, j \leq i\) of an integral \(I = \int_a^b f(x)\; dx\) with the end-of-row values \(R_{0,0}, R_{1,1}, \dots R_{n,n}\) being the main, successively better (usually) approximations.
It starts with the trapezoid rule \(R_{0,0} := T_1 = \frac{f(a) + f(b)}{2}(b-a)\); the basic trapezoid rule.
Then using \(T_{2n} = \frac{T_n + M_n}{2}\), one defines
Finally, Richardson extrapolation leads to
and with further extrapolations to the more general formula
Exercise¶
Implement this, using these three formulas plus the function for the composite midpoint rule in section Summation and Integration
One natural data structure is a 2D array with unused entries above the main diagonal. However, you might consider how to store this triangular collection of data as a list of lists, succesively of lengths 1, 2 and so on up to \(n\).