%
%
%


\section{Elements of Numerical Integration}  \label{sec_int02}

\begin{frame}
\frametitle{Elements of Numerical Integration}

The basic method involved in approximating the integration
\begin{equation}   \label{eq_int02001}
   \int_{a}^{b} f(x) \, dx,
\end{equation}
is called numerical quadrature and uses a sum of the type
\begin{equation}    \label{eq_int02004}
    \int_{a}^{b} f(x) \, dx \approx \sum_{i=0}^{n} c_{i} f(x_{i}).
\end{equation}
%
The method of quadrature in this section is based on the
polynomial interpolation. We first select a set of distinct nodes
$\{ x_{0}, x_{1}, \ldots, x_{n} \}$ from the interval $[a,b]$.
Then the Lagrange polynomial
%
\[
    P_{n}(x) = \sum_{i=0}^{n} f(x_{i}) L_{i} (x)
    = \sum_{i=0}^{n} f(x_{i}) \prod_{\stackrel{j=0}{j \neq i}}^{n}
    \frac{x - x_{j}}{x_{i} - x_{j}}
\]
%
is used to approximate $f(x)$. With the error term we have
\end{frame}

\begin{frame}
%
\[
    f(x) = P_{n}(x) + E_{n}(x)
    = \sum_{i=0}^{n} f(x_{i}) L_{i} (x) +
    \frac{f^{(n+1)}(\zeta_{x})}{(n+1)!} \prod_{i=0}^{n}(x- x_{i}),
\]
%
where $\zeta_{x} \in [a,b]$ and depends on $x$, and
%
\begin{eqnarray}
   \int_{a}^{b} f(x) \, dx
%   & = &
%   \int_{a}^{b} \sum_{i=0}^{n} f(x_{i}) L_{i}(x) \, dx +
%   \int_{a}^{b} \frac{f^{(n+1)}(\zeta_{x})}{(n+1)!} \prod_{i=0}^{n}(x- x_{i})
%   \nonumber  \\
   & = &
   \int_{a}^{b} P_{n}(x) \, dx + \int_{a}^{b} E_{n}(x) \, dx
   \nonumber  \\
   & = &
   \sum_{i=0}^{n} f(x_{i}) \int_{a}^{b} L_{i}(x) \, dx +
   \frac{1}{(n+1)!} \int_{a}^{b} f^{(n+1)}(\zeta_{x})
   \prod_{i=0}^{n} (x - x_{i}) \, dx.
\end{eqnarray}



%
The quadrature formula is, therefore,
%
\begin{equation}
   \int_{a}^{b} f(x) \, dx \approx \int_{a}^{b} P_{n}(x) \, dx
   = \sum_{i=0}^{n} f(x_{i}) \int_{a}^{b} L_{i}(x) \, dx
   \equiv \sum_{i=0}^{n} c_{i} f(x_{i}),
\end{equation}
%
where
%
\begin{equation}   \label{eq_int02009}
    c_{i} = \int_{a}^{b} L_{i}(x) \, dx
    = \int_{a}^{b} \prod_{\stackrel{j=0}{j \neq i}}^{n}
    \frac{x - x_{j}}{x_{i} - x_{j}} \, dx.
\end{equation}
\end{frame}

%
\begin{frame}
Moreover, the error in the quadrature formula is given by
%
\begin{equation}
   E =  \frac{1}{(n+1)!} \int_{a}^{b} f^{(n+1)}(\zeta_{x})
   \prod_{i=0}^{n} (x - x_{i})  \, dx,
\end{equation}
%
for some $\zeta_{x} \in [a,b]$.

Let us consider formulas produced by using first and second Lagrange
polynomials with equally spaced nodes. This gives the
{\textcolor{red}{Trapezoidal rule}} and {\textcolor{red}{Simpson's
rule}}, respectively.

{\bf Trapezoidal rule}: Let $x_0 = a, x_1 = b, h = b - a$ and use
the linear Lagrange polynomial:
\begin{eqnarray*}
    P_1(x) = \frac{(x-x_1)}{(x_0-x_1)} f(x_0) +
    \frac{(x-x_0)}{(x_1-x_0)} f(x_1).
\end{eqnarray*}
Then
\begin{eqnarray}
    \int_a^b f(x) dx &=& \int_{x_0}^{x_1} \left[
    \frac{(x-x_1)}{(x_0-x_1)} f(x_0) + \frac{(x-x_0)}{(x_1-x_0)}
    f(x_1) \right] dx  \nonumber \\
    && + \frac{1}{2} \int_{x_0}^{x_1}
    f^{\prime\prime}(\zeta(x)) ( x - x_0) ( x - x_1 ) dx.
    \label{eq:NumInt_1}
\end{eqnarray}
\end{frame}

\begin{frame}
    \begin{theorem}[Weighted Mean Value Theorem for Integrals]
        Suppose $f \in C[a,b]$, the Riemann integral of $g(x)$
        \begin{eqnarray*}
            \int_a^b g(x) dx = \lim_{\max \triangle x_i \to 0}
            \sum_{i=1}^n g(x_i) \triangle x_i,
        \end{eqnarray*}
        exists and $g(x)$ does not change sign on $[a, b]$. Then
        $\exists \ c \in (a,b)$ with
        \begin{eqnarray*}
            \int_a^b f(x) g(x) dx = f(c) \int_a^b g(x) dx.
        \end{eqnarray*}
    \end{theorem}

    Since $(x-x_0)( x - x_1)$ does not change sign on $[x_0, x_1]$,
    by the Weighted Mean Value Theorem, $\exists \ \zeta \in ( x_0,
    x_1 )$ such that
    \begin{eqnarray*}
        && \int_{x_0}^{x_1}
        f^{\prime\prime}(\zeta(x)) ( x - x_0) ( x - x_1 ) dx =
        f^{\prime\prime}(\zeta) \int_{x_0}^{x_1} ( x - x_0) ( x
        -x_1) dx \\
        &=& f^{\prime\prime}(\zeta) \left[ \frac{x^3}{3} -
        \frac{x_1+x_0}{2} x^2 + x_0 x_1 x \right]_{x_0}^{x_1} = -
        \frac{h^3}{6} f^{\prime\prime}( \zeta ).
    \end{eqnarray*}
\end{frame}

\begin{frame}
    Consequently, Eq. \eqref{eq:NumInt_1} implies that
    \begin{eqnarray*}
        \int_a^b f(x) dx &=& \left[ \frac{(x-x_1)^2}{2(x_0-x_1)}
        f(x_0) + \frac{(x-x_0)^2}{2(x_1-x_0)} f(x_1)
        \right]_{x_0}^{x_1} - \frac{h^3}{12} f^{\prime\prime}(\zeta)
        \\
        &=& \frac{x_1-x_0}{2} \left[ f(x_0) + f(x_1) \right] -
        \frac{h^3}{12} f^{\prime\prime}(\zeta) \\
        &=& \frac{h}{2}\left[ f(x_0) + f(x_1) \right] -
        \frac{h^3}{12} f^{\prime\prime}(\zeta),
    \end{eqnarray*}
    which is called the Trapezoidal rule.

    \begin{figure}[t] %\sidecaption
        \centering
        \resizebox{4.5cm}{!}{\includegraphics{TrapRul.pdf}}
    \end{figure}
\end{frame}

\begin{frame}


If we choose $x_{0} = a$, $x_{1} = \frac{1}{2}(a + b)$, $x_{2} = b$,
$ h = (b - a)/2$, and the second order Lagrange polynomial
%
\begin{eqnarray*}
   P_{2}(x) &=&
   f(x_{0}) \frac{(x - x_{1})(x - x_{2})}{(x_{0} - x_{1})(x_{0} - x_{2})}
   + f(x_{1}) \frac{(x - x_{0})(x - x_{2})}{(x_{1} - x_{0})(x_{1} -
   x_{2})} \\
   && + f(x_{2}) \frac{(x - x_{0})(x - x_{1})}{(x_{2} - x_{0})(x_{2} - x_{1})}
\end{eqnarray*}
%
to interpolate $f(x)$, then

    \begin{figure}[t] %\sidecaption
        \centering
        \resizebox{5.5cm}{!}{\includegraphics{SimpRul.pdf}}
    \end{figure}
\end{frame}

\begin{frame}
    \begin{eqnarray*}
        \int_a^b f(x) dx &=& \int_{x_0}^{x_2} \left[
        \frac{(x - x_{1})(x - x_{2})}{(x_{0} - x_{1})(x_{0} -
        x_{2})} f(x_{0}) + \frac{(x - x_{0})(x - x_{2})}{(x_{1} - x_{0})(x_{1} -
        x_{2})} f(x_{1}) \right. \\
        && \left. + \frac{(x - x_{0})(x - x_{1})}{(x_{2} - x_{0})(x_{2} -
        x_{1})} f(x_{2}) \right] dx \\
        && + \int_{x_0}^{x_2} \frac{(x-x_0)(x-x_1)(x-x_2)}{6}
        f^{(3)}  ( \zeta(x) ) dx.
    \end{eqnarray*}
    Since, letting $x = x_0 + t h$,
    \begin{eqnarray*}
        \int_{x_0}^{x_2} \frac{(x - x_{1})(x - x_{2})}{(x_{0} - x_{1})(x_{0} -
        x_{2})} dx &=& h \int_{0}^{2}
        \frac{t - 1}{0 - 1} \cdot \frac{t - 2}{0 - 2} \, dt \\
        &=& \frac{h}{2} \int_{0}^{2} (t^{2} - 3 t + 2) \, dt
        = \frac{h}{3}, \\
        \int_{x_0}^{x_2} \frac{(x - x_{0})(x - x_{2})}{(x_{1} - x_{0})(x_{1} -
        x_{2})} dx &=& h \int_{0}^{2}
        \frac{t - 0}{1 - 0} \cdot \frac{t - 2}{1 - 2} \, dt \\
        &=& -h \int_{0}^{2} (t^{2} - 2 t) \, dt
        = \frac{4 h}{3},
    \end{eqnarray*}
\end{frame}

\begin{frame}
\begin{eqnarray*}
   \int_{x_0}^{x_2} \frac{(x - x_{0})(x - x_{1})}{(x_{2} - x_{0})(x_{2} -
        x_{1})} dx & = & h \int_{0}^{2}
   \frac{t - 0}{2 - 0} \cdot \frac{t - 1}{2 - 1} \, dt \\
   &=& \frac{h}{2} \int_{0}^{2} (t^{2} - t) \, dt
   = \frac{h}{3},
\end{eqnarray*}
%
it implies that
\begin{eqnarray*}
   \int_a^b f(x) dx
   &=& h \left[ \frac{1}{3} f(x_0) + \frac{4}{3} f(x_1)
     + \frac{1}{3} f(x_2) \right] \\
   && + \int_{x_0}^{x_2} \frac{(x-x_0)(x-x_1)(x-x_2)}{6}
        f^{(3)}  ( \zeta(x) ) dx,
\end{eqnarray*}
%
which is called the Simpson's rule and
provides only an
$O(h^{4})$ error term involving $f^{(3)}$. A higher order error
analysis can be derived by expanding $f$ in the third Taylor's
formula about $x_{1}$. $\forall \ x \in [a,b]$, $\exists$
$\zeta_{x} \in (a,b)$ such that
%
\begin{eqnarray*}
   f(x) &=& f(x_{1}) + f'(x_{1})(x - x_{1})
      + \frac{f''(x_{1})}{2} (x - x_{1})^{2} \\
   && + \frac{f'''(x_{1})}{6} (x - x_{1})^{3}
      + \frac{f^{(4)}(\zeta_{x})}{24} (x - x_{1})^{4}.
\end{eqnarray*}
\end{frame}
%

\begin{frame}
Then
%
\begin{eqnarray*}
   \int_{a}^{b} f(x) \, dx
   &=& \left[ f(x_{1}) (x - x_{1})
     + \frac{f'(x_{1})}{2} (x - x_{1})^{2}
     + \frac{f''(x_{1})}{6} (x - x_{1})^{3} \right. \\
   && \left.  + \frac{f'''(x_{1})}{24} (x - x_{1})^{4} \right] \Bigg|_{a}^{b}
     + \frac{1}{24} \int_{a}^{b} f^{(4)}(\zeta_{x}) (x - x_{1})^{4} \, dx.
\end{eqnarray*}
%
Note that $(b - x_{1}) = h$, $(a - x_{1}) = -h$, and since $(x -
x_{1})^{4}$ does not change sign in $[a,b]$, by the Weighted
Mean-Value Theorem for Integral, there exists $\xi_{1} \in (a,b)$
such that
%
\[
   \int_{a}^{b} f^{(4)}(\zeta_{x}) (x - x_{1})^{4} \, dx
   = f^{(4)}(\xi_{1}) \int_{a}^{b} (x - x_{1})^{4} \, dx
   = \frac{2 f^{(4)}(\xi_{1})}{5} h^{5}.
\]
%
Consequently,
%
\[
   \int_{a}^{b} f(x) \, dx
   = 2 f(x_{1}) h + \frac{f''(x_{1})}{3}  h^{3}
   + \frac{f^{(4)}(\xi_{1})}{60} h^{5}.
\]
\end{frame}
%

\begin{frame}
Finally we replace $f''(x_{1})$ by the central finite difference
formulation
%
\[
   f''(x_{1}) = \frac{f(x_{0}) - 2 f(x_{1}) + f(x_{2})}{h^{2}}
   - \frac{f^{(4)}(\xi_{2})}{12} h^{2},
\]
%
for some $\xi_{2} \in (a,b)$, to obtain
%
\begin{eqnarray*}
   \int_{a}^{b} f(x) \, dx
   & = &
   2 h f(x_{1}) + \frac{h}{3} \left( f(x_{0}) - 2 f(x_{1}) + f(x_{2})
   \right) \\
   && - \frac{f^{(4)}(\xi_{2})}{36} h^{5}
   + \frac{f^{(4)}(\xi_{1})}{60} h^{5}  \\
   & = &
   h \left[ \frac{1}{3} f(x_{0}) + \frac{4}{3} f(x_{1})
   + \frac{1}{3} f(x_{2}) \right] \\
   && + \frac{1}{90} \left[ \frac{3}{2} f^{(4)}(\xi_{1})
   - \frac{5}{2} f^{(4)}(\xi_{2})  \right] h^{5}.      %    \\
%   & = &
%   h \left[ \frac{1}{3} f(x_{0}) + \frac{4}{3} f(x_{1})
%   + \frac{1}{3} f(x_{2}) \right]
%   + \frac{f^{(4)}(\xi)}{90} h^{5}.
\end{eqnarray*}
%
It can show that there exists $\xi \in (a,b)$ such that
\[
   \int_{a}^{b} f(x) \, dx =
   \frac{h}{3} \left[ f(x_{0}) + 4 f(x_{1})
   + f(x_{2}) \right]
   - \frac{f^{(4)}(\xi)}{90} h^{5}.
\]
%
This gives the {\textcolor{blue}{Simpson's rule formulation}}.
\end{frame}



%If $|f^{(n+1)}(x)| \leq M$ on $[a,b]$, then
%%
%\begin{equation}
%   \left| \int_{a}^{b} f(x) \, dx - \sum_{i=0}^{n} c_{i} f(x_{i}) \right|
%   \leq
%   \frac{M}{(n+1)!} \int_{a}^{b} \prod_{i=0}^{n} (x - x_{i}) \, dx.
%\end{equation}
%%
%The choice of nodes that makes the right-hand side of this
%error bound as small as possible is know to be
%%
%\begin{equation}
%   x_{i} = \frac{a+b}{2} + \frac{b-a}{2}
%   \cos \left[ \frac{(i+1) \pi}{n+2} \right],
%   \qquad i = 0, 1, \ldots, n.
%\end{equation}
%
%
%
%Of course, a polynomial interpolation to $f$ can be obtained in
%other ways, for example, polynomial in Newton's form using
%divided-difference method,
%%
%\[
%    P_{n}(x) = f(x_{0}) +
%    \sum_{i=1}^{n} f[x_{0}, x_{1}, \ldots, x_{i}]
%     \prod_{j=0}^{i-1} (x - x_{j})
%\]
%%
%where $f[x_{0}, x_{1}, \ldots, x_{i}]$ are evaluated with
%the divided difference algorithm. Then
%%
%\begin{equation}
%   \int_{a}^{b} f(x) \, dx \approx
%   f(x_{0})(b - a) +
%   \sum_{i=1}^{n} f[x_{0}, x_{1}, \ldots, x_{i}]
%   \int_{a}^{b} \prod_{j=0}^{i-1} (x - x_{j}) \, dx.
%\end{equation}
%%


%The standard derivation of quadrature error formulas is based on
%determining the class of polynomials for which theses formulas
%produce exact results. The next definition is used to facilitate
%the discussion of this derivation.

\begin{frame}
\begin{definition}
   The degree of accuracy, or precision, of a quadrature formula
   is the largest positive integer $n$ such that the formula is
   exact for $x^{k}$, when $k=0, 1, \ldots, n$.
\end{definition}

\begin{block}{}
\begin{itemize}
    \item The Trapezoidal and Simpson's rules have degrees of precision one and three, respectively.
    \item The degree of accuracy of a quadrature
formula is $n$ if and only if the error $E = 0$ for all polynomials
$P(x)$ of degree less than or equal to $n$, but $E \neq 0$ for some
polynomials of degree greater than $n$.
\end{itemize}
\end{block}
\end{frame}


\subsection{Newton-Cotes Formulas}

\begin{frame}
\frametitle{Newton-Cotes Formulas}
\begin{definition}[Newton-Cotes formula]
A quadrature formula of the form
\begin{eqnarray*}
    \int_a^b f(x) dx \approx \sum_{i=0}^n c_i f(x_i)
\end{eqnarray*}
is called
a Newton-Cotes formula if the nodes $\{ x_{0}, x_{1}, \ldots, x_{n} \}$
are equally spaced.
\end{definition}

Consider a uniform partition of the closed interval $[a,b]$ by
%
\[
    x_{i} = a + i h, \quad i = 0, 1, \ldots, n, \quad
    h = \frac{b - a}{n},
\]
%
where $n$ is a positive integer and $h$ is called the step length.

\end{frame}

\begin{frame}
By introduction a new variable $t$ such that $x = a + h t$,
the fundamental Lagrange polynomial becomes
%
\[
   L_{i}(x)
   = \prod_{\stackrel{j=0}{j \neq i}}^{n} \frac{x - x_{j}}{x_{i} - x_{j}}
   = \prod_{\stackrel{j=0}{j \neq i}}^{n}
     \frac{a + h t - a - j h}{a + i h - a - j h}
   = \prod_{\stackrel{j=0}{j \neq i}}^{n} \frac{t - j}{i - j}
   \equiv \varphi_{i}(t).
\]
%
Therefore, the integration (\ref{eq_int02009}) gives
\begin{equation}  \label{eq_02015}
   c_{i} = \int_{a}^{b} L_{i}(x) \, dx
   = \int_{0}^{n} \varphi_{i}(t) h \, dt
   = h \int_{0}^{n} \prod_{\stackrel{j=0}{j \neq i}}^{n}
     \frac{t - j}{i - j} \, dt,
\end{equation}
%
and the general Newton-Cotes formula has the form
%
\begin{equation} \label{eq_02016}
   \int_{a}^{b} f(x) \, dx = h \sum_{i=0}^{n} f(x_{i})
   \int_{0}^{n} \prod_{\stackrel{j=0}{j \neq i}}^{n}
     \frac{t - j}{i - j} \, dt
   + \frac{1}{(n+1)!} \int_{a}^{b} f^{(n+1)}(\zeta_{x})
     \prod_{i=0}^{n} (x - x_{i})  \, dx.
\end{equation}
%
\end{frame}

\begin{frame}
\begin{theorem}[Closed Newton-Cotes Formulas]
   Suppose that $\sum_{i=0}^n a_i f(x_i)$ denotes the $(n+1)$-point closed
   Newton-Cotes formula with $x_0 = a, x_n = b$ and $h = (b-a)/n$.
   If $n$ is even and $f \in C^{n+2}[a,b]$, then
   \begin{equation}
      \int_{a}^{b} f(x) \, dx = h \sum_{i=0}^{n} \alpha_{i} f(x_{i})
      + \frac{h^{n+3} f^{(n+2)}(\xi)}{(n+2)!}
        \int_{0}^{n} t^{2} (t - 1) \cdots (t - n) \, dt,
   \end{equation}
   and if $n$ is odd and $f \in C^{n+1}[a,b]$, then
   \begin{equation}
      \int_{a}^{b} f(x) \, dx = h \sum_{i=0}^{n} \alpha_{i} f(x_{i})
      + \frac{h^{n+2} f^{(n+1)}(\xi)}{(n+1)!}
        \int_{0}^{n} t (t - 1) \cdots (t - n) \, dt,
   \end{equation}
   where $\xi \in (a,b)$ and
   %\begin{equation}
      $\alpha_{i} = \int_{0}^{n} \prod_{j=0, \ j \neq i}^{n}
                   \frac{t - j}{i - j} \, dt$ for
      $i = 0, 1, \ldots, n$.
   %\end{equation}
   Consequently,
   the degree of accuracy is $n+1$ when $n$ is an even integer, and
   $n$ when $n$ is an odd integer.
\end{theorem}
\end{frame}

\begin{frame}

\begin{itemize}
    \item $n=1$: Trapezoidal rule
        \[
            \int_{a}^{b} f(x) \, dx
            = \frac{b-a}{2} \left[ f(a) + f(b) \right]
            - \frac{h^{3}}{12} f''(\xi),\ a < \xi < b.
        \]
    \item $n=2$: Simpson's rule
        \[
           \int_{a}^{b} f(x) \, dx =
           h \left[ \frac{1}{3} f(x_{0}) + \frac{4}{3} f(x_{1})
           + \frac{1}{3} f(x_{2}) \right]
           - \frac{f^{(4)}(\xi)}{90} h^{5},\ a < \xi < b.
        \]
    \item The error term of the Trapezoidal rule is
          $O(h^{3})$.
    \item Since the rule involves $f''$, it gives the exact result
when applied to any function whose second derivative is identically
zero, e.g., any polynomial of degree $1$ or less.
    \item The
degree of accuracy of Trapezoidal rule is one.
    \item The Simpson's rule is an $O(h^{5})$
scheme and the degree of accuracy is three.
\end{itemize}

\end{frame}


%\begin{frame}
%\frametitle{Trapezoidal rule}
% The simplest case is to choose $n=1$,
%$x_{0} = a$, $x_{1} = b$, $h = b - a$, and use the linear Lagrange
%polynomial
%%
%\[
%    P_{1}(x) = f(x_{0}) \frac{x - x_{1}}{x_{0} - x_{1}} +
%    f(x_{1}) \frac{x - x_{0}}{x_{1} - x_{0}}
%    = f(a) \frac{x - b}{a - b} + f(b) \frac{x - a}{b - a}.
%\]
%%
%to interpolate $f(x)$. Then
%%
%\[
%   c_{0} = h \int_{0}^{1} \frac{t - 1}{0 - 1} \, dt = \frac{h}{2},
%   \qquad
%   c_{1} = h \int_{0}^{1} \frac{t - 0}{1 - 0} \, dt = \frac{h}{2},
%\]
%and
%\[
%   \int_{a}^{b} P_{1}(x) \, dx = c_{0} f(x_{0}) + c_{1} f(x_{1})
%   = \frac{h}{2} \left[ f(a) + f(b) \right].
%\]
%%
%\end{frame}
%
%\begin{frame}
%Since $(x - x_{0})(x - x_{1}) = (x - a)(x - b)$ does not change sign
%on $[a,b]$, by the Weighted Mean-Value Theorem for integrals,
%there exists some $\xi \in (a,b)$ such that
%%
%\begin{eqnarray*}
%   \int_{a}^{b} f''(\zeta_{x}) (x - x_{0})(x - x_{1}) \, dx
%   & = &
%   f''(\xi) \int_{a}^{b} (x - x_{0})(x - x_{1}) \, dx \\
%   & = &
%   f''(\xi) \int_{a}^{b} (x - a)(x - b) \, dx  \\
%   & = &
%   f''(\xi) \left[ \frac{1}{3} x^{3} - \frac{1}{2} (a + b) x^{2}
%   + a b x \right] \Bigg|_{a}^{b}  \\
%   & = &
%   -\frac{1}{6} f''(\xi) (b - a)^{3}
%   = -\frac{1}{6} f''(\xi) h^{3}.
%\end{eqnarray*}
%%
%Consequently,
%%
%\[
%   \int_{a}^{b} f(x) \, dx
%   = \frac{b-a}{2} \left[ f(a) + f(b) \right]
%   - \frac{h^{3}}{12} f''(\xi).
%\]
%%
%This gives the so-called Trapezoidal rule.
%\end{frame}
%
%\begin{frame}
%\begin{itemize}
%    \item The error term of the Trapezoidal rule is
%          $O(h^{3})$.
%    \item Since the rule involves $f''$, it gives the exact result
%when applied to any function whose second derivative is identically
%zero, e.g., any polynomial of degree $1$ or less.
%    \item The
%degree of accuracy of Trapezoidal rule is one.
%\end{itemize}
%\end{frame}
%
%\begin{frame}
%
%\frametitle{Simpson's rule}
%If we choose $n=2$, $x_{0} = a$, $x_{1}
%= \frac{1}{2}(a + b)$, $x_{2} = b$, $ h = (b - a)/2$, and the second
%order Lagrange polynomial
%%
%\begin{eqnarray*}
%   P_{2}(x) &=&
%   f(x_{0}) \frac{(x - x_{1})(x - x_{2})}{(x_{0} - x_{1})(x_{0} - x_{2})}
%   + f(x_{1}) \frac{(x - x_{0})(x - x_{2})}{(x_{1} - x_{0})(x_{1} -
%   x_{2})} \\
%   && + f(x_{2}) \frac{(x - x_{0})(x - x_{1})}{(x_{2} - x_{0})(x_{2} - x_{1})}
%\end{eqnarray*}
%%
%to interpolate $f(x)$, then
%\begin{eqnarray*}
%   c_{0} & = & h \int_{0}^{2}
%   \frac{t - 1}{0 - 1} \cdot \frac{t - 2}{0 - 2} \, dt
%   = \frac{h}{2} \int_{0}^{2} (t^{2} - 3 t + 2) \, dt
%   = \frac{h}{3},  \\
%   c_{1} & = & h \int_{0}^{2}
%   \frac{t - 0}{1 - 0} \cdot \frac{t - 2}{1 - 2} \, dt
%   = -h \int_{0}^{2} (t^{2} - 2 t) \, dt
%   = \frac{4 h}{3},  \\
%   c_{2} & = & h \int_{0}^{2}
%   \frac{t - 0}{2 - 0} \cdot \frac{t - 1}{2 - 1} \, dt
%   = \frac{h}{2} \int_{0}^{2} (t^{2} - t) \, dt
%   = \frac{h}{3},  \\
%\end{eqnarray*}
%\end{frame}
%
%\begin{frame}
%%
%and
%\begin{eqnarray*}
%   \int_{a}^{b} P_{2} (x) \, dx
%   &=& c_{0} f(x_{0}) + c_{1} f(x_{1}) + c_{2} f(x_{2}) \\
%   &=& h \left[ \frac{1}{3} f(a) + \frac{4}{3} f(\frac{a+b}{2})
%     + \frac{1}{3} f(b) \right].
%\end{eqnarray*}
%
%For each $x \in [a,b]$,
%there exists $\zeta_{x} \in (a,b)$ such that
%%
%\begin{eqnarray*}
%   f(x) &=& f(x_{1}) + f'(x_{1})(x - x_{1})
%   + \frac{f''(x_{1})}{2} (x - x_{1})^{2}
%   + \frac{f'''(x_{1})}{6} (x - x_{1})^{3} \\
%   && + \frac{f^{(4)}(\zeta_{x})}{24} (x - x_{1})^{4}.
%\end{eqnarray*}
%%
%Then
%%
%\begin{eqnarray*}
%   \int_{a}^{b} f(x) \, dx
%   &=& \left[ f(x_{1}) (x - x_{1})
%     + \frac{f'(x_{1})}{2} (x - x_{1})^{2}
%     + \frac{f''(x_{1})}{6} (x - x_{1})^{3} \right. \\
%     && \left. + \frac{f'''(x_{1})}{24} (x - x_{1})^{4} \right] \Bigg|_{a}^{b}
%     + \frac{1}{24} \int_{a}^{b} f^{(4)}(\zeta_{x}) (x - x_{1})^{4} \, dx.
%\end{eqnarray*}
%\end{frame}
%
%%
%\begin{frame}
%Note that $(b - x_{1}) = h$, $(a - x_{1}) = -h$, and since
%$(x - x_{1})^{4}$ does not change sign in $[a,b]$, by the
%Weighted Mean-Value Theorem for Integral, there exists
%$\xi_{1} \in (a,b)$ such that
%%
%\[
%   \int_{a}^{b} f^{(4)}(\zeta_{x}) (x - x_{1})^{4} \, dx
%   = f^{(4)}(\xi_{1}) \int_{a}^{b} (x - x_{1})^{4} \, dx
%   = \frac{2 f^{(4)}(\xi_{1})}{5} h^{5}.
%\]
%%
%Consequently,
%%
%\[
%   \int_{a}^{b} f(x) \, dx
%   = 2 f(x_{1}) h + \frac{f''(x_{1})}{3}  h^{3}
%   + \frac{f^{(4)}(\xi_{1})}{60} h^{5}.
%\]
%%
%Finally we replace $f''(x_{1})$ by the central finite difference
%formulation
%%
%\[
%   f''(x_{1}) = \frac{f(x_{0}) - 2 f(x_{1}) + f(x_{2})}{h^{2}}
%   - \frac{f^{(4)}(\xi_{2})}{12} h^{2}
%\]
%%
%for some $\xi_{2} \in (a,b)$, to obtain
%\end{frame}
%%
%
%\begin{frame}
%\begin{eqnarray*}
%   \int_{a}^{b} f(x) \, dx
%   & = &
%   2 h f(x_{1}) + \frac{h}{3} \left( f(x_{0}) - 2 f(x_{1}) + f(x_{2})
%   \right) \\
%   && - \frac{f^{(4)}(\xi_{2})}{36} h^{5}
%   + \frac{f^{(4)}(\xi_{1})}{60} h^{5}  \\
%   & = &
%   h \left[ \frac{1}{3} f(x_{0}) + \frac{4}{3} f(x_{1})
%   + \frac{1}{3} f(x_{2}) \right] \\
%   && + \frac{1}{90} \left[ \frac{3}{2} f^{(4)}(\xi_{1})
%   - \frac{5}{2} f^{(4)}(\xi_{2})  \right] h^{5}.
%\end{eqnarray*}
%%
%One can show that there exists
%$\xi \in (a,b)$ such that
%\[
%   \int_{a}^{b} f(x) \, dx =
%   h \left[ \frac{1}{3} f(x_{0}) + \frac{4}{3} f(x_{1})
%   + \frac{1}{3} f(x_{2}) \right]
%   + \frac{f^{(4)}(\xi)}{90} h^{5}.
%\]
%%
%This gives the Simpson's rule formulation.
%
%
%\begin{itemize}
%  \item The Simpson's rule is an $O(h^{5})$
%scheme and the degree of accuracy is three.
%
%  \item The Trapezoidal and Simpson's rules are examples of closed Newton-Cotes formula.
%\end{itemize}
%\end{frame}

%
%
%The weights $\alpha_{i}$ in the Newton-Cotes formula has the
%property
%%
%\begin{equation}
%    \sum_{i=0}^{n} \alpha_{i} = n.
%\end{equation}
%%
%This can be shown by applying the formula to $f(x) = 1$ with
%interpolating polynomial $P_{n}(x) = 1$. Let $s$ be the common
%denominator of $\alpha_{i}$, that is,
%%
%\[
%    \alpha_{i} = \frac{\sigma_{i}}{s}
%    \qquad (\Rightarrow \sigma_{i} = s \alpha_{i})
%\]
%%
%such that $\sigma_{i}$ are integers, then the formulation for
%approximating the definite integral can be expressed as
%%
%\begin{equation}
%   \int_{a}^{b} f(x) \, dx  \approx
%   h \sum_{i=0}^{n} \alpha_{i} f(x_{i})
%   = \frac{h}{s} \sum_{i=0}^{n} \sigma_{i} f(x_{i}).
%\end{equation}
%%
%Some of the most common closed Newton-Cotes formulas with their
%error terms are listed in the following table.
%
%\begin{center}
%\renewcommand{\arraystretch}{1.25}
%\begin{tabular}{|l|c|r|l|r|}
%   \hline
%   \multicolumn{1}{|c|}{Name}
%   &  $n$  &  $s$  &  $\sigma_{i}$  &
%   \multicolumn{1}{|c|}{Error}  \\
%   \hline
%   Trapezoidal rule  &  $1$  &  $2$  &  $1, 1$  &
%   $-\frac{1}{12} f^{(2)}(\xi) h^{3}$  \\
%%
%   Simpson's rule  &  $2$  &  $3$  &  $1, 4, 1$  &
%   $-\frac{1}{90} f^{(4)}(\xi) h^{5}$  \\
%%
%   $3/8$-rule  &  $3$  &  $\frac{8}{3}$  &  $1, 3, 3, 1$  &
%   $-\frac{3}{80} f^{(4)}(\xi) h^{5}$  \\
%%
%   Milne's rule  &  $4$  &  $\frac{45}{2}$  &  $7, 32, 12, 32, 7$  &
%   $-\frac{8}{945} f^{(6)}(\xi) h^{7}$  \\
%%
%     &  $5$  &  $\frac{288}{5}$  &  $19, 75, 50, 50, 75, 19$  &
%   $-\frac{275}{12096} f^{(6)}(\xi) h^{7}$  \\
%%
%   Weddle's rule  &  $6$  &  $140$  &  $41, 216, 27, 272, 27, 216, 41$  &
%   $-\frac{9}{1400} f^{(8)}(\xi) h^{9}$  \\
%%
%   \hline
%\end{tabular}
%\end{center}

\begin{frame}
Another class of Newton-Cotes formulas is the open Newton-Cotes
formulas in which the nodes
\begin{eqnarray*}
   x_{i} = x_{0} + i h, \quad i = 0, 1, \ldots, n,
\end{eqnarray*}
where
\begin{eqnarray*}
   x_{0} = a + h \quad \text{and} \quad
   h = \frac{b - a}{n+2},
\end{eqnarray*}
are used. This implies that $x_{n} = b - h$, and the endpoints,
$a$ and $b$, are not used. Hence we label $a = x_{-1}$ and
$b = x_{n+1}$. The formulas become
\begin{eqnarray*}
    \int_a^b f(x) dx = \int_{x_{-1}}^{x_{n+1}} f(x) dx \approx \sum_{i=0}^n a_i f(x_i),
\end{eqnarray*}
where
\begin{eqnarray*}
    a_i = \int_a^b L_i(x) dx.
\end{eqnarray*}
The following theorem summarizes the
open Newton-Cotes formulas.
\end{frame}

\begin{frame}
\begin{theorem}[Open Newton-Cotes Formulas]
   Suppose that $\sum_{i=0}^n a_i f(x_i)$ denotes the $(n+1)$-point open Newton-Cotes formula with $x_{-1} = a$, $x_{n+1} = b$ and $h = ( b-a)/(n+2)$.
   If $n$ is even and $f \in C^{n+2}[a,b]$, then
   \begin{equation}
      \int_{a}^{b} f(x) \, dx = h \sum_{i=0}^{n} \alpha_{i} f(x_{i})
      + \frac{h^{n+3} f^{(n+2)}(\xi)}{(n+2)!}
        \int_{-1}^{n+1} t^{2} (t - 1) \cdots (t - n) \, dt,
   \end{equation}
   and if $n$ is odd and $f \in C^{n+1}[a,b]$, then
   \begin{equation}
      \int_{a}^{b} f(x) \, dx = h \sum_{i=0}^{n} \alpha_{i} f(x_{i})
      + \frac{h^{n+2} f^{(n+1)}(\xi)}{(n+1)!}
        \int_{-1}^{n+1} t (t - 1) \cdots (t - n) \, dt,
   \end{equation}
   where $\xi \in (a,b)$ and
   %\begin{equation}
      $\alpha_{i} = \int_{-1}^{n+1} \prod_{j=0, j \neq i}^{n}
                   \frac{t - j}{i - j} \, dt$ for
      $ i = 0, 1, \ldots, n.$
   %\end{equation}
   Consequently,
   the degree of accuracy is $n+1$ when $n$ is an even integer, and
   $n$ when $n$ is an odd integer.
\end{theorem}
\end{frame}

\begin{frame}
The simplest open Newton-Cotes formula is choosing $n=0$ and
only using the midpoint $x_{0} = \frac{a+b}{2}$. Then the
coefficient and the error term can be computed easily as
%
\[
   \alpha_{0} = \int_{1}^{-1} \, dt = 2,
   \quad \text{and} \quad
   \frac{h^{3} f''(\xi)}{2!} \int_{-1}^{1} t^{2} \, dt
   = \frac{1}{3} f''(\xi) h^{3}.
\]
These gives the so-called Midpoint rule or Rectangular rule.


\noindent Midpoint Rule:
\begin{equation}
   \int_{a}^{b} f(x) \, dx = 2 h f(x_{0}) + \frac{1}{3} f''(\xi) h^{3}
   = (b - a) f(\frac{a+b}{2}) + \frac{1}{3} f''(\xi) h^{3},
\end{equation}
for some $\xi \in (a,b)$.
\end{frame}




\section{Composite Numerical Integration}

\begin{frame}
\frametitle{Composite Numerical Integration}
\begin{itemize}
    \item The Newton-Cotes formulas are generally not
suitable for numerical integration over large interval.
Higher degree formulas would be required, and the coefficients
in these formulas are difficult to obtain.
    \item Also the Newton-Cotes
formulas which are based on polynomial interpolation would be
inaccurate over a large interval because of the oscillatory
nature of high-degree polynomials.
    \item Now we discuss a piecewise
approach, called composite rule, to numerical integration
over large interval that uses the low-order Newton-Cotes formulas.
    \begin{itemize}
    \item A composite rule is one obtained by applying an integration
formula for a single interval to each subinterval of a partitioned
interval.
    \end{itemize}
\end{itemize}

%\vspace{-45mm}

\begin{figure}[ht]
\begin{center}
\resizebox{5cm}{!}{\includegraphics{CompNumInt.pdf}}
\end{center}
\end{figure}

\end{frame}

\begin{frame}
To illustrate the procedure, we choose an even integer
$n$ and partition the interval $[a,b]$ into $n$ subintervals
by nodes $a = x_{0} < x_{1} < \cdots < x_{n} = b$, and apply
Simpson's rule on each consecutive pair of subintervals.
With
%
\[
   h = \frac{b - a}{n} \quad \text{and} \quad
   x_{j} = a + j h, \quad j = 0, 1, \ldots, n,
\]
%
we have on each interval $[x_{2j-2}, x_{2j}]$,
%
\[
   \int_{x_{2j-2}}^{x_{2j}} f(x) \, dx
   = \frac{h}{3} \left[ f(x_{2j-2}) + 4 f(x_{2j-1}) + f(x_{2j}) \right]
    - \frac{h^{5}}{90} f^{(4)}(\xi_{j}),
\]
for some $\xi_{j} \in (x_{2j-2},x_{2j})$, provided that
$f \in C^{4}[a,b]$.


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

\end{frame}

\begin{frame}
The composite rule is obtained by summing up
over the entire interval, that is,
%
\begin{eqnarray*}
   \int_{a}^{b} f(x) \, dx
   & = &
   \sum_{j=1}^{n/2} \int_{x_{2j-2}}^{x_{2j}} f(x) \, dx  \\
%
   & = &
   \sum_{j=1}^{n/2} \left[ \frac{h}{3} \left( f(x_{2j-2})
   + 4 f(x_{2j-1}) + f(x_{2j}) \right)
   - \frac{h^{5}}{90} f^{(4)}(\xi_{j}) \right]  \\
%
   & = &
   \frac{h}{3} \left[ f(x_{0}) + 4 f(x_{1}) + f(x_{2})  \right. \\
   && \hspace{2mm} + f(x_{2})
   + 4 f(x_{3}) + f(x_{4}) \\
   && \hspace{2mm} + f(x_{4}) + 4 f(x_{5}) + f(x_6) \\
   & & \hspace{22mm} \vdots \\
   && \left. \hspace{2mm}
   + f(x_{n-2}) + 4 f(x_{n-1}) + f(x_{n})  \right]
   - \frac{h^{5}}{90} \sum_{j=1}^{n/2} f^{(4)}(\xi_{j})
\end{eqnarray*}
\end{frame}

\begin{frame}
Hence
\begin{eqnarray*}
%
   \int_{a}^{b} f(x) \, dx& = &
   \frac{h}{3} \left[ f(x_{0}) + 4 f(x_{1}) + 2 f(x_{2})
   + 4 f(x_{3}) + 2 f(x_{4}) + 4 f(x_{5})  \right.  \\
   & &
   \left. + \cdots
   + 2 f(x_{n-2}) + 4 f(x_{n-1}) + f(x_{n})  \right]
   - \frac{h^{5}}{90} \sum_{j=1}^{n/2} f^{(4)}(\xi_{j})   \\
%
   & = &
   \frac{h}{3} \left[ f(x_{0}) + 4 \sum_{j=1}^{n/2} f(x_{2j-1})
   + 2 \sum_{j=1}^{(n/2)-1} f(x_{2j}) + f(x_{n}) \right] \\
   && - \frac{h^{5}}{90} \sum_{j=1}^{n/2} f^{(4)}(\xi_{j}).
\end{eqnarray*}
%
To estimate the error associated with
approximation, since $f \in C^{4}[a,b]$, we have, by the
Extreme Value Theorem,
%
\[
   \min_{x \in [a,b]} f^{(4)}(x) \leq f^{(4)}(\xi_{j})
   \leq \max_{x \in [a,b]} f^{(4)}(x),
\]
%
for each $\xi_{j} \in (x_{2j-2},x_{2j})$.
\end{frame}

\begin{frame}
Hence
%
\[
   \frac{n}{2} \min_{x \in [a,b]} f^{(4)}(x)
   \leq \sum_{j=1}^{n/2} f^{(4)}(\xi_{j})
   \leq \frac{n}{2} \max_{x \in [a,b]} f^{(4)}(x),
\]
%
and
%
\[
   \min_{x \in [a,b]} f^{(4)}(x)
   \leq \frac{2}{n} \sum_{j=1}^{n/2} f^{(4)}(\xi_{j})
   \leq \max_{x \in [a,b]} f^{(4)}(x).
\]
%
By the Intermediate Value Theorem, there exists $\mu \in (a,b)$
such that
%
\[
   f^{(4)}(\mu) = \frac{2}{n} \sum_{j=1}^{n/2} f^{(4)}(\xi_{j}).
\]
%
Thus, by replacing $n = (b - a)/h$,
%
\[
    \sum_{j=1}^{n/2} f^{(4)}(\xi_{j})
    = \frac{n}{2} f^{(4)}(\mu)
    = \frac{b - a}{2h} f^{(4)}(\mu).
\]
%
Consequently, the composite Simpson's rule is derived.
\end{frame}
%

\begin{frame}
\begin{block}{Composite Simpson's Rule}
%
\begin{eqnarray*}
   \int_{a}^{b} f(x) \, dx
   &=& \frac{h}{3} \left[ f(a) + 4 \sum_{j=1}^{n/2} f(x_{2j-1})
     + 2 \sum_{j=1}^{(n/2)-1} f(x_{2j}) + f(b) \right] \\
   &&  - \frac{b - a}{180} f^{(4)}(\mu) h^{4},
\end{eqnarray*}
%
where $n$ is an even integer, $h = (b - a)/n$, $x_{j} = a + j h$,
for $j = 0, 1, \ldots, n$, and some $\mu \in (a,b)$.
\end{block}
\end{frame}

\begin{frame}
The composite Midpoint rule can be derived in a similar way, except
the midpoint rule is applied on each subinterval $[x_{2j-1}, x_{2j+1}]$
instead. That is,
%
\[
   \int_{x_{2j-1}}^{x_{2j+1}} f(x) \, dx
   = 2 h f(x_{2j}) + \frac{h^{3}}{3} f''(\xi_{j}),
   \qquad j = 1, 2, \ldots, \frac{n}{2}.
\]
%
Note that $n$ must again be even. Consequently,
%
\[
   \int_{a}^{b} f(x) \, dx = 2 h \sum_{j=1}^{n/2} f(x_{2j})
   + \frac{h^{3}}{3} \sum_{j=1}^{n/2} f''(\xi_{j}).
\]
%
%\vspace{-5mm}

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

\begin{frame}
The error term can be written as
%
\[
   \sum_{j=1}^{n/2} f''(\xi_{j}) = \frac{n}{2} f''(\mu)
   = \frac{b - a}{2h} f''(\mu),
\]
%
for some $\mu \in (a, b)$.

\begin{block}{Composite Midpoint Rule}
%
\begin{equation}
   \int_{a}^{b} f(x) \, dx
   =  2 h \sum_{j=1}^{n/2} f(x_{2j})
     + \frac{b - a}{6} f''(\mu) h^{2},
\end{equation}
%
where $n$ is an even integer, $h = (b - a)/n$, $x_{j} = a + j h$,
for $j = 0, 1, \ldots, n$, and some $\mu \in (a,b)$.
\end{block}
\end{frame}

\begin{frame}
To derive the composite Trapezoidal rule, we partition $[a,b]$ by
$n$ equally spaced nodes $a = x_{0} < x_{1} < \cdots < x_{n} = b$,
where $n$ can be either odd or even. Apply the trapezoidal rule on
$[x_{j-1}, x_{j}]$ and sum them up to obtain
%
\begin{eqnarray*}
   \int_{a}^{b} f(x) \, dx
   & = &
   \sum_{j=1}^{n} \int_{x_{j-1}}^{x_{j}} f(x) \, dx  \\
   & = &
   \sum_{j=1}^{n} \left\{ \frac{h}{2} \left[ f(x_{j-1}) + f(x_{j})
   \right] - \frac{h^{3}}{12} f''(\xi_{j}) \right\}  \\
   & = &
   \frac{h}{2} \left\{ \left[ f(x_{0}) + f(x_{1}) \right] + \left[ f(x_{1}) +
   f(x_{2}) \right]
   + \cdots \right. \\
   && \left. + \left[ f(x_{n-1}) + f(x_{n}) \right] \right\}
   - \frac{h^{3}}{12} \sum_{j=1}^{n} f''(\xi_{j})
\end{eqnarray*}

\vspace{-5mm}

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

\begin{frame}
Hence,
\begin{eqnarray*}
   \int_{a}^{b} f(x) \, dx & = &
   \frac{h}{2} \left[ f(x_{0}) + 2 f(x_{1}) + 2 f(x_{2})
   + \cdots + 2 f(x_{n-1}) + f(x_{n}) \right] \\
   && - \frac{h^{3}}{12} \sum_{j=1}^{n} f''(\xi_{j})  \\
   & = &
   \frac{h}{2} \left[ f(a) + 2\sum_{j=1}^{n-1} f(x_{j}) + f(b) \right]
   - \frac{h^{3}}{12} \sum_{j=1}^{n} f''(\xi_{j})  \\
   & = &
   \frac{h}{2} \left[ f(a) + 2\sum_{j=1}^{n-1} f(x_{j}) + f(b) \right]
   - \frac{b - a}{12}  f''(\mu) h^{2},
\end{eqnarray*}
%
where each $\xi_{j} \in (x_{j-1}, x_{j})$ and $\mu \in (a,b)$.
\end{frame}

\begin{frame}
\begin{block}{Composite Trapezoidal Rule}
%
\begin{equation}
   \int_{a}^{b} f(x) \, dx
   = \frac{h}{2} \left[ f(a) + 2 \sum_{j=1}^{n-1} f(x_{j}) + f(b) \right]
     - \frac{b - a}{12}  f''(\mu) h^{2}, \label{eq:CompTrapRul}
\end{equation}
where $n$ is an integer, $h = (b - a)/n$, $x_{j} = a + j h$,
for $j = 0, 1, \ldots, n$, and some $\mu \in (a,b)$.
\end{block}
\end{frame}
