Richardson extrapolation integral

Use Richardson extrapolation to compute $\displaystyle \int_{-4}^4\frac{dx}{1+x^2}$ with the number of subintervals $[n=1,2,4,8,\ldots$].

Compare the results

$\displaystyle I_1^{(0)},I_2^{(1)},I_4^{(2)},I_8^{(3)},\ldots$ to trapezoidal and Simpson rule.

I know that I must refer to Romberg integration table and I must compare it to the exact solution $2\tan^{-1}4$ to calculate the error of each approximation. I know how to do this problem using trapezoidal and Simpson rule, but I don't know how to apply this problem using Richardson extrapolation.

We are given:

$$\displaystyle \int_{-4}^4\frac{dx}{1+x^2}$$

This results in:

$$\displaystyle \int_{-4}^4\frac{dx}{1+x^2} = 2 tan^{-1}(4) \approx 2.6516353273360649301184$$

You said you know how to do Trapezoidal and Simpson's Rule, however, I am assuming you mean the Composite Simpson's and Trapezoidal Rules, given you are comparing these over the requisite subintervals.

Composite Simpson's

$$\int_{a}^b f(x)~dx = \frac{h}{3}\left[f(a) + 2\sum_{j=1}^{m-1}f(x_{2j}) + 4\sum_{j=1}^{m-1}f(x_{2j - 1}) +f(b)\right] - \frac{(b-a)h^4}{180} f^{(4)}(\mu)$$

where $a = x_0 \lt x_1 \lt \cdots \lt x_n = b$, $h = \frac{b-a}{n}$, and $x_j = x_0 + jh$ for each $j = 0, 1, \ldots, n$.

Composite Trapezoidal

$$\int_{a}^b f(x)~dx = \frac{h}{2}\left[f(a) + f(b) + 2\sum_{j=1}^{n-1}f(x_{j}) + \right] - \frac{(b-a)h^2}{12} f''(\mu)$$

where $h = \frac{b-a}{n}$, and $x_j = a + jh$ for each $j = 0, 1, \ldots, n$.

Now, we are asked to use Richardson extrapolation to compute $\displaystyle \int_{-4}^4\frac{dx}{1+x^2}$ with the number of subintervals $[n=1,2,4,8,\ldots]$.

Of course, someone has taken the Richardson extrapolation and incorporated it into the Romberg algorithm for integration.

Romberg

You start off by calculating the first column of the Romberg table using:

$$R_{1,1} = h\frac{\left[ f(a) + f(b) \right]}{2} = \frac{b-a}{2}\left[f(a) + f(b)\right]$$

$$\displaystyle R_{k,1} = \frac{1}{2}\left[R_{1,1} + h\sum_{k=1}^{2^{i-2}}f\left(a + \left(k - \frac{1}{2} \right)h\right) \right].$$

Note: here we are using the Approximation from the Trapezoidal Rule for $R_{k,1}$.

Since you are doing $n = 1, 2, 4, 8$, just calculate $R_{1,1}$ through $R_{8, 1}$ using $(1)$. This is the first column in the Romberg table. So, we calculate:

$R_{1,1} = h\frac{\left[f(a) + f(b)\right]}{2} = \frac{8}{17} = 0.470588$,

$R_{2,1} = \frac{1}{2}\left[R_{1,1} + 8f(-4 + (1-0.5)8)\right] = \frac{1}{2}\left[R_{1,1} +8 f(0)\right] = \frac{1}{2}( \frac{8}{17} + 8) = 4.2352941.$

Continuing in this fashion, we arrive at:

$R_{1,1} = 0.4705882353$

$R_{2,1} = 4.235294118$

$R_{3,1} = 2.917647059$

$R_{4,1} = 2.658823529$

$R_{5,1} = 2.650506805$

$R_{6,1} = 2.651347164$

$R_{7,1} = 2.651563252$

$R_{8,1} = 2.651617306$

Romberg Algorithm

You need to apply this to each of the given $n$'s. It may be the case that if you just create the table for $n = 8$, you get the results for the lower values of $n$, so check to see if that is true.

Step 1: For $i = 2, \ldots, n$ do Steps 2 through 4 (note, we reuse the column numbers for each new column)

Step 2: $$\displaystyle R_{2,1} = \frac{1}{2}\left[R_{1,1} + h\sum_{k=1}^{2^{i-2}}f\left(a + \left(k - \frac{1}{2} \right)h\right) \right].$$

Step 3: For $j = 2, \ldots, i$, set (this is the Richardson Extrapolation step)

$$\displaystyle R_{2,j} = \frac{4^{j-1} R_{2,j-1} - R_{1,j-1}}{4^{j-1} - 1}$$

Step 4: $h = \frac{h}{2}$

Doing this algorithm will generate the Romberg table as:

$$\begin{array}{c|c|c|c|c|c|} & & & & & & & \\ \hline R_{1,1} & & & & & & \\ \hline R_{2,1} & R_{2,2} & & & & & \\ \hline R_{3,1} & R_{3,2} & R_{3,3} & & & & \\ \hline R_{4,1} & R_{4,2} & R_{4,3} & R_{4,4} & & & \\ \hline R_{5,1} & R_{5,2} & R_{5,3} & R_{5,4} & R_{5,5} & & \\ \hline R_{6,1} & R_{6,2} & R_{6,3} & R_{6,4} & R_{6,5} & R_{6,6} & \\ \hline R_{7,1} & R_{7,2} & R_{7,3} & R_{7,4} & R_{7,5} & R_{7,6} & R_{7,7} \\ \hline R_{8,1} & R_{8,2} & R_{8,3} & R_{8,4} & R_{8,5} & R_{8,6} & R_{8,7} & R_{8,8}\\ \hline \end{array}$$

The actual values will be (be careful to note spacing - hard to display values properly!):

$0.4705882353$

$4.235294118 ~ 5.490196078$

$2.917647059 ~ 2.478431373 ~ 2.277647059$

$2.658823529 ~ 2.572549020 ~ 2.57882353 ~ 2.583604109$

$2.650506805 ~ 2.647734564 ~ 2.652746933 ~ 2.653920321 ~ 2.654196071$

$2.651347164 ~ 2.651627283 ~ 2.651886798 ~ 2.651873144 ~ 2.651865116 ~ 2.651862838$

$2.651563252 ~ 2.651635281 ~ 2.651635815 ~ 2.651631831 ~ 2.651630884 ~ 2.651630655 ~ 2.651630599$

$2.651617306 ~ 2.651635325 ~ 2.651635328 ~ 2.65163532 ~ 2.651635333 ~ 2.651635338 ~ 2.651635339 ~ 2.651635339$

Compare the final value to the actual result above and also to the composite results. Also, compare this to the different integration techniques and look at how much better it is. Look at the error between the different methods and the error within each method.

• This is great, thank you very much!!!! Clear and concise, I hope it gets more upvotes! Commented Mar 25, 2013 at 2:36
• @user60514: You are welcome! Make sure you go through it as it is a tricky algorithm and is an example of where people got sloppy of mixing apples and oranges for two very useful techniques! It is a very important algorithm to get your hands around with Richardson's extrapolation. Commented Mar 25, 2013 at 2:48
• Will do, thanks! Commented Mar 25, 2013 at 3:02
• Very thorough, and wonderful to have feedback!! Commented Apr 16, 2013 at 0:54
• @LMartin: Thank you. Te Composite Simpson Rule is actually much simpler to implement than Romberg. See the example on page 367 of mathfaculty.fullerton.edu/mathews//n2003/simpsonsrule/… as a sample. Regards Commented Jan 23, 2015 at 0:51