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

\[ R_{i, 0} := T_{2_i} = \frac{T_{2^{i}/2} + M_{2^{i}/2}}{2} = \frac{T_{2^{i-1}} + M_{2^{i-1}}}{2} = \frac{R_{i-1, 0} + M_{2^{i-1}}}{2}, \quad i \geq 1 \]

Finally, Richardson extrapolation leads to

\[ R_{i,1} := S_{2^i} = \frac{4 T_{2^i} - T_{2^i/2}}{4 - 1} = \frac{4 R_{i,0} - R_{i-1,0}}{4 - 1} = R_{i,0} + \frac{R_{i,0} - R_{i-1,0}}{4 - 1}, \; i \geq 1 \]

and with further extrapolations to the more general formula

\[ R_{i,j} := \frac{4^j R_{i,j-1} - R_{i-1,j-1}}{4^j - 1} = R_{i,j-1} + \frac{R_{i,j-1} - R_{i-1,j-1}}{4^i - 1}, \; 1 \leq j \leq i \]

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\).