%
%
%


\section{Romberg Integration}

\begin{frame}

\frametitle{Romberg Integration}
 Recall the trapezoidal rule
integral formulation
%
\begin{eqnarray*}
    \int_{a}^{b} f(x) \, dx
    & \approx&    T(n)    \\
    & = &
    \frac{h}{2} [ f(a) + 2 f(a+h) + 2 f(a+2h) + \cdots \\
    && +
    2 f(a + (n-1)h) + f(a + nh) ],
\end{eqnarray*}
%
where $h = \frac{b-a}{n}$.  Let $n=2$ and $h = \frac{b-a}{2n}$.

$\bullet$ If we only consider the partitions by {\textcolor{blue}{$x_{0}, x_{2}$}}, and
{\textcolor{blue}{$x_{4}$}}, and apply the Trapezoidal rule, we have the approximation
%
\[
   T(n) = \frac{2h}{2} [ f(a) + 2 f(a + 2h) + f(a + 4h) ]
   = h [ f(a) + 2 f(a + 2h) + f(a + 4h) ].
\]
%
$\bullet$ If we apply Trapezoidal rule by ${\textcolor{blue}{x_{0}}}, {\textcolor{red}{x_{1}}}, {\textcolor{blue}{x_{2}}},
{\textcolor{red}{x_{3}}}$, and {\textcolor{blue}{$x_{4}$}}, then we have
%
\begin{eqnarray*}
   T(2n)
   & = &
   \frac{h}{2} [ f(a) + 2 f(a + h) + 2 f(a + 2h)
           + 2 f(a + 3h) + f(a + 4h) ]  \\
   & = &
   \frac{1}{2} T(n) + {\color{red} h [ f(a + h) + f(a + 3h) ]}.
\end{eqnarray*}
%
\end{frame}

\begin{frame}
This observation shows that
\begin{itemize}
    \item if we have computed $T(n)$ and the step
size is half, we don't have to compute all the function values all
over again, but just at those newly added points.
    \item In general,
suppose $T(n)$ has been computed and the step size becomes $h =
\frac{b - a}{2n}$, then
%
\begin{equation}
   T(2n) = \frac{1}{2} T(n) + h \sum_{i=1}^{n} f(a + (2i-1)h).
\end{equation}
%
\end{itemize}

With this idea in mind, we can apply the trapezoidal rule
recursively, i.e., we partition the interval $[a,b]$ into $2^{n}$
subintervals with $n = 1,2,3, \ldots$,

\begin{figure}[ht]
%\begin{center}
\resizebox{8cm}{!}{\includegraphics{romberg.pdf}}
%\resizebox{5cm}{!}{\includegraphics{CompSimpRule.pdf}}
%\end{center}
\end{figure}
\end{frame}

\begin{frame}
and the integral formulation
becomes
%
\begin{equation}
   T(2^{n}) = \frac{1}{2} T(2^{n-1}) + \frac{b-a}{2^{n}}
   \sum_{i=1}^{2^{n-1}} f(a + (2i-1) \frac{b-a}{2^{n}}).
\end{equation}
%
Let
\begin{eqnarray*}
    R_{k,1} = T(2^k).
\end{eqnarray*}
If $f \in C^{\infty}[ a, b]$, then
\begin{eqnarray}
    \int_a^b f(x) dx - R_{k,1} = K_1 h_k^2 + \sum_{i=2}^{\infty} K_i h_k^{2^i}, \label{eq:romberg_1}
\end{eqnarray}
where each $K_i$ is independent of $h_k$ and depends only on $f^{(2i-1)}(a)$ and $f^{(2i-1)}(b)$. Replacing $h_k$ with $h_{k+1} = h_k / 2$, we get
\begin{eqnarray}
    \int_a^b f(x) dx - R_{k+1,1} = \frac{K_1 h_k^2}{4} + \sum_{i=2}^{\infty} \frac{K_i h_k^{2^i}}{4^i}. \label{eq:romberg_2}
\end{eqnarray}
\end{frame}

\begin{frame}
Subtracting Eq. \eqref{eq:romberg_1} from 4 times Eq. \eqref{eq:romberg_2}, we have
\begin{eqnarray*}
    \int_{a}^b f(x) dx - \left[ R_{k+1,1} + \frac{R_{k+1,1} - R_{k,1}}{3} \right] = -\frac{K_2}{4} h_k^4 + \sum_{i=3}^{\infty} \frac{K_i}{3} \left( \frac{1-4^{i-1}}{4^{i-1}} \right) h_k^{2i}.
\end{eqnarray*}
Define
\begin{eqnarray*}
    R_{k,2} = R_{k,1} + \frac{R_{k,1} - R_{k-1,1}}{3}, \ \mbox{ for } k = 2, 3, \ldots, n.
\end{eqnarray*}
Apply the extrapolation procedure to those values. Continuing this notation, we  have, for each $k = 2, 3, 4, \ldots, n$ and $j = 2, \ldots, k$, an $O(h_k^{2j})$ approximation formula defined by
\begin{eqnarray*}
    R_{k,j} = R_{k,j-1} + \frac{R_{k,j-1}-R_{k-1,j-1}}{4^{j-1}-1}.
\end{eqnarray*}

This is called the Romberg algorithm.
\end{frame}

\begin{frame}
\begin{algorithm}[Romberg Integration Algorithm]
Use the Romberg algorithm to evaluate $\int_{a}^{b} f(x) \, dx$.

   $R(0,0) = \frac{1}{2} (b - a)[f(a) + f(b)]$ \\
   For {$n = 1, 2, \ldots, M$} \\
      \hspace{7mm}  $R(n,0) = \frac{1}{2} R(n-1,0)
              + \frac{b-a}{2^{n}} \sum_{i=1}^{2^{n-1}}
              f(a + (2i-1) \frac{b - a}{2^{n}})$ \\
   End for \\
   For $k=1,2, \ldots, M$ \\
      \hspace{7mm} For $n = k, k+1, \ldots, M$ \\
         \hspace{12mm}  $R(n,k) = R(n,k-1) + \frac{1}{4^{k} - 1}
                 [R(n,k-1) - R(n-1,k-1)]$ \\
      \hspace{7mm} End for \\
   End for
\end{algorithm}
\end{frame}
%\begin{remark}
%   \begin{enumerate}
%      \item  The Romberg algorithm produces a table looks like the
%             following.
%      \item  $M$ is modest, not too large.
%      \item  No duplicate function evaluations in
%             $R(0,0), R(1,0), \ldots, R(M,0)$.
%      \item  No function evaluation is needed im computing
%             $R(m,k)$ when $k \geq 1$.
%   \end{enumerate}
%\end{remark}


\begin{frame}
\begin{theorem}
   If $f \in C[a,b]$, then for each column $k$,
   \begin{equation}
      \lim_{n \rightarrow \infty} R(n,k) = \int_{a}^{b} f(x) \, dx.
   \end{equation}
   Moreover, if $f \in C^{2m}[a,b]$, then $R(n,m)$ converges to
   $\int_{a}^{b} f(x) \, dx$ with a rate of $O(h^{2m})$, where
   $h = \frac{b-a}{2^{n}}$.
\end{theorem}
\end{frame} 