The technique of Richardson Extrapolation can be applied to any situation in which the error formula can be written as powers of
\(h\text{.}\) Romberg integration uses this with composite trapezoid rule to develop a fast-converging quadrature scheme.
It can be shown that composite trapezoid rule can be written as
\begin{equation*}
\begin{aligned}\int_{a}^{b} f(x) \, dx\amp = \frac{h}{2}\biggl( f(x_{0}) + 2 \sum_{i=1}^{n-1}f(x_{i}) + f(x_{n}) \biggr) + \sum_{i=0}^{\infty}k_{i} h^{2i}\end{aligned}
\end{equation*}
which fits the error scheme from
(5.5.8). Thus Romberg integration creates a table based on the composite trapezoid rule and Richardson extrapolation.
\begin{align*}
R_{1,1}\amp = \frac{h_{1}}{2}\bigl( f(a)+f(b) \bigr) = \frac{b-a}{2}\bigl(f(a)+f(b) \bigr) \\
R_{2,1}\amp = \frac{h_{2}}{2}\bigl(f(a) +f(b) + 2 f(a+h_{2}) \bigr) \\
\amp = \frac{b-a}{4}\biggl( f(a) + f(b) + 2 f\biggl(a+ \frac{b-a}{2}\biggr) \biggr) \notag \\\amp = \frac{1}{2}\bigl( R_{1,1}+ h_{1} f(a+ h_{2}) \bigr) \\
R_{3,1}\amp = \frac{h_{3}}{2}\bigl(f(a)+f(b) + 2 [ f(a+h_{3}) +f(a+2h_{3}) + f(a+3h_{3})]\bigr) \\
\amp = \frac{b-a}{8}\bigl( f(a) + f(b) + 2 f(a+h_{2}) + 2 [ f(a+h_{3}) + f(a+3h_{3})] \bigr) \notag \\\amp = \frac{1}{2}\bigl( R_{2,1}+ h_{2} [f(a+h_{3}) + f(a+3h_{3})]\bigr)
\end{align*}
and extending this in general leads to
\begin{equation}
R_{n,1} = \frac{1}{2}\biggl( R_{n-1,1}+ h_{n-1}\sum_{k=1}^{2^{n-1}}f(a+(2k-1)h_{n}) \biggr).\tag{5.5.12}
\end{equation}
Using this formula along with Richardson extrapolation, which applied in this case to
(5.5.11) results in
\begin{equation}
R_{n,j+1} = \frac{4^{j-1}}{4^{j-1}-1}R_{n,j}- \frac{1}{4^{j-1}-1}R_{n-1,j-1}\tag{5.5.13}
\end{equation}
Typically a table is created using 1)
\(R_{n,1}\) which is the trapezoid rule given in
(5.5.12) and 2) the relation in
(5.5.13). We will see this in the following example.
Generally Romberg integration is performed in a manner that builds up a table until the desired accuracy is found. That is, the table is created row by row until two consecutive numbers on the diagonal are found within the desired level of error. The following example shows this.
Example 5.5.3.
Use Romberg integration to find
\(\int_{0}^{1} e^{-x^2}\, dx\) to within
\(10^{-5}\text{.}\)
First, we start by calculating \(R_{1,1}\) and \(R_{2,1}\) using (eq:romberg:first) and (eq:romberg:first:col)
\begin{equation*}
\begin{aligned}R_{1,1}= \frac{1}{2}\bigl( f(0) + f(1) \bigr) \approx 0.683939720585721 \\ R_{2,1}= \frac{1}{2}\bigl(R_{1,1}+ f(1/2) \bigr) \approx 0.731370251828563 \\\end{aligned}
\end{equation*}
Then use (eq:romberg) to find \(R_{2,2}\text{:}\)
\begin{equation*}
\begin{aligned}R_{2,2}= \frac{4}{3}R_{2,1}- \frac{1}{3}R_{1,1}= 0.747180428909510\end{aligned}
\end{equation*}
Since \(|R_{2,2}-R_{1,1}| \gt 10^{-5}\text{,}\) another row of the table is built using (eq:romberg:first:col)
\begin{equation*}
\begin{aligned}R_{3,1}= \frac{1}{2}\bigl(R_{2,1}+ \frac{1}{2}[f(1/4)+f(3/4)]\bigr) \approx 0.742984097800381\end{aligned}
\end{equation*}
Then \(R_{3,2}\) and \(R_{3,3}\) are computed using (eq:romberg)
\begin{equation*}
\begin{aligned}R_{3,2}\amp = \frac{4}{3}R_{3,1}-\frac{1}{3}R_{2,1}= 0.746855379790987 \\ R_{3,3}\amp = \frac{16}{15}R_{3,2}-\frac{1}{15}R_{2,2}= 0.746833709849753\end{aligned}
\end{equation*}
Since \(|R_{3,3}-R_{2,2}|\approx 3 \cdot 10^{-4}\text{,}\) this is still not within the desired error. At least one more row must be calculated.
\begin{equation*}
\begin{aligned}R_{4,1}\amp = \frac{1}{2}\bigl(R_{3,1}+ \frac{1}{4}[f(1/8)+f(3/8)+f(5/8)+f(7/8)]\bigr) \\\amp \approx 0.745865614845695\end{aligned}
\end{equation*}
Then \(R_{4,2}\text{,}\) \(R_{4,3}\) and \(R_{4,4}\) are computed:
\begin{equation*}
\begin{aligned}R_{4,2}\amp = \frac{4}{3}R_{4,1}-\frac{1}{3}R_{3,1}= 0.746826120527465 \\ R_{4,3}\amp = \frac{16}{15}R_{4,2}-\frac{1}{15}R_{3,2}= 0.746824169909898 \\ R_{4,4}\amp = \frac{64}{63}R_{4,3}-\frac{1}{63}R_{3,3}= 0.746824018482282\\\end{aligned}
\end{equation*}
and now \(|R_{4,4}-R_{3,3}|= 9 \cdot 10^{-6}<10^{-5}\text{,}\) so we can stop here. The approximate value of the integral is \(R_{4,4}\text{.}\)
