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.
Best Answer
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.