
% \documentclass[pdf,autumn,slideColor,colorBG]{prosper}
\documentclass[pdf,umbc3,slideColor,colorBG]{prosper}

\usepackage{color}

% definitions for math symbols
\renewcommand{\vec}[1]{\mathbf{#1}}
\renewcommand {\Re}{{\rm I \kern-2pt R}}
\newcommand{\grad}{\mathop{\rm  grad}}


 \title{Change of Basis in Polynomial Interpolation}
      \subtitle{A Prosper Demonstration\\
          Blaegovgrad, September 2003}
      \author{Walter Gander}
      \email{gander@inf.ethz.ch}
      \institution{
             Institute of Computational Science\\
              Department of Computer Science \\
              ETH Z\"urich
      }

      % Optional: text to put in the bottom of each slide.
      % By default, the title of the talk will be placed there.
      \slideCaption{\textit{Walter Gander, ETH}}


\begin{document}

% change font size
% \ptsize{11}

      % make the title slide
      \maketitle

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}{Prof.\ Don Knuth \textcolor{red}{Inventor of \TeX}}
   \includegraphics[angle=-90,width=8cm]{knuth.eps}          
\end{slide}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}{The Interpolating Polynomial}
 \textcolor{red}{(Monomial basis)}

Interpolation condition: 
$      
  P(x_i) = f(x_i), \quad i = 0, \ldots, n
$

$P_n(x)= a_0 + a_1x+  \ldots+ a_{n-1}x^{n-1}+ a_nx^n $
$$
  \begin{array}{cccc}
  \underbrace{
    \left[\begin{array}{ccccc}
     1 &x_0 &\ldots& x_0^{n-1}& x_0^n \\
    1 &  x_1 &\ldots&     x_1^{n-1}&   x_1^n  \\
      \vdots& \vdots   &      &\vdots&\vdots \\
    1 &x_n&\ldots& x_n^{n-1}&       x_n^n  \\
      \end{array}
    \right]
  } &
  \underbrace{
    \left(\begin{array}{c}
      a_0 \\
      \vdots\\
      a_{n-1} \\
      a_n \\
      \end{array}
    \right)
  } & = &
  \underbrace{
    \left(\begin{array}{c}
      f(x_0) \\
      f(x_1) \\
      \vdots\\
      f(x_n) \\
      \end{array}
    \right)
  } \\
  V & \vec{a} & = & \vec{f}
  \end{array}
$$
$$
 \vec{m}(x) = [1, x, x^2, \ldots, x^n]^T, \quad
  \vec{a} = [a_0, a_1, \ldots, a_n]^T 
\quad  
 \textcolor{red}{P_n(x) = \vec{a}^T\vec{m}(x)}
$$
\end{slide}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}{Lagrange Interpolation} 
\textcolor{red}{Basis: Lagrange  Polynomials} 
$$
l_i(x)= \prod_{j=0 \atop j \ne i}^{n}\frac{x-x_j}{x_i-x_j}, \quad
i=0,1,\ldots,n
$$

$$
  P_n(x)=\sum_{j=0}^n f(x_j)\;l_j(x)
$$

$
\vec{l}(x) = [l_0(x), l_1(x),  \ldots, l_n(x)]^T
,\qquad \vec{f} = [f_0, f_1, \ldots, f_n]^T
$

$$\textcolor{red}
{  P_n(x)  = \vec{f}^T\vec{l}(x)  =  \vec{a}^T\vec{m}(x)}
$$
\end{slide}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
\begin{slide}{Newton Interpolation  } 

\textcolor{red}{Basis:  Newton polynomials }

$ 
 \pi_k(x) = \prod_{j=0}^{k-1}(x-x_j), \quad k=0,\ldots, n
$

$
  P_n(x) =  d_0\pi_0(x) + d_1\pi_1(x) + \cdots d_n\pi_{n}(x)
$

Interpolation condition: \quad
$
  \sum_{j=0}^n  d_j\pi_j(x_i) = f(x_i), \quad i = 0, \ldots n.
$  

Matrix of system is lower triangular $U^T \vec{d} = \vec{f}$ since 
$\pi_k(x_j)=0$, $j<k$
{\tiny
$$
 \left(
   \begin{array}{cccc}
      \pi_0(x_0)  & \cdots & \pi_n(x_0)\\
      \pi_0(x_1)  & \cdots & \pi_n(x_1)\\
        \vdots    & \cdots & \vdots \\
  \pi_0(x_n) & \cdots & \pi_n(x_n)
   \end{array}
\right)
= 
 \left(
   \begin{array}{ccccc}
  1 \\
   1 & x_1-x_0\\
 1 &  x_2-x_0  & (x_2-x_0)(x_2-x_1) \\
   \vdots &  \vdots &  \vdots & \ddots \\
  1 &  x_n-x_0 & (x_n-x_0)(x_n-x_1) &  \cdots & \prod_{j=0}^{n-1}(x_n-x_j)
   \end{array}
\right)
$$
}
Solve for $\vec{d}$ by forward substitution: 
$$
   d_0 = f(x_0),\quad 
   d_i = \frac{f(x_i) - \sum_{j=0}^{i-1} d_j \pi(x_i)}{\pi_i(x_i)}, 
   \; i = 1, \ldots, n.
$$
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\overlays{4}{%
\begin{slide}{Newton Interpolation  } 

\onlySlide*{1}{
\textcolor{red}{Basis:  Newton polynomials }
$$
 \pi_k(x) = \prod_{j=0}^{k-1}(x-x_j), \quad k=0,\ldots, n
$$
}% Slide1

\onlySlide*{2}{
$$
  P_n(x) =  d_0\pi_0(x) + d_1\pi_1(x) + \cdots d_n\pi_{n}(x)
$$

\textcolor{red}{Interpolation condition:}

$$
  \sum_{j=0}^n  d_j\pi_j(x_i) = f(x_i), \quad i = 0, \ldots n.
$$ 
}

\onlySlide*{3}{
Matrix of system 
$$
 \left(
   \begin{array}{cccc}
      \pi_0(x_0)  & \cdots & \pi_n(x_0)\\
      \pi_0(x_1)  & \cdots & \pi_n(x_1)\\
        \vdots    & \cdots & \vdots \\
  \pi_0(x_n) & \cdots & \pi_n(x_n)
   \end{array}
\right)
$$
is lower triangular $U^T \vec{d} = \vec{f}$ since 
$\pi_k(x_j)=0$, $j<k$
{\tiny
$$
= 
 \left(
   \begin{array}{ccccc}
  1 \\
   1 & x_1-x_0\\
 1 &  x_2-x_0  & (x_2-x_0)(x_2-x_1) \\
   \vdots &  \vdots &  \vdots & \ddots \\
  1 &  x_n-x_0 & (x_n-x_0)(x_n-x_1) &  \cdots & \prod_{j=0}^{n-1}(x_n-x_j)
   \end{array}
\right)
$$
}
}

\onlySlide*{4}{
Solve for $\vec{d}$ by forward substitution: 
$$
   d_0 = f(x_0),\quad 
   d_i = \frac{f(x_i) - \sum_{j=0}^{i-1} d_j \pi(x_i)}{\pi_i(x_i)}, 
   \; i = 1, \ldots, n.
$$
}
\end{slide}
} % overlays 

\end{document}

