\documentclass[twoside]{article}

\usepackage{palatino}
\usepackage{camnum}


\def\s {\begin{array}{@{}c@{}}
       \\[-2ex] 
       \scriptstyle\searrow\\[-1ex]
        \end{array} }
\def\r {\rightarrow}


\textheight=23.5cm
\textwidth=15cm
\topmargin=0cm
\oddsidemargin=0.5cm
\evensidemargin=0.5cm
\parindent=0pt
\parskip=6pt

\setcounter{section}{6}
\setcounter{subsection}{5}
\setcounter{equation}{0}

\begin{document}
\begin{center}
  {\large \textbf{Mathematical Tripos Part IB: Easter 2001}}

  {\Large \textbf{Numerical Analysis -- Lecture
      9\footnote{Corrections and suggestions to these notes should
        be emailed to \texttt{a.shadrin@damtp.cam.ac.uk}. All handouts
        are available on the WWW at the URL 
        \texttt{http://www.damtp.cam.ac.uk/user/na/PartIB/Handouts.html}.}}}
\end{center}

\subsection{The Newton interpolation formula}

The recursive formula allows for fast
evaluation of the {\em divided difference table,\/} in the following
manner: 
{\small
$$
\begin{array}{c*{10}{c@{\,}}}
\hline
\\[-2ex]
x_i & f[\;]=f(\;) & f[,]  && f[,,] && f[,,,] \\[0.5ex]
\hline
\\[-1ex]
x_0 & \r f[x_0]\s & \\
    &        & f[x_0,x_1] &\s& \\
x_1 & f[x_1] &            &  & f[x_0,x_1,x_2] &\s& \\
    &        & f[x_1,x_2] &  &                &  & f[x_0,x_1,x_2,x_3] \\
x_2 & f[x_2] &            &  & f[x_1,x_2,x_3] &\\
    &        & f[x_2,x_3] &  \\
x_3 & f[x_3] & \\[0.5ex] \hline
\end{array}
$$
}         
This can be done in $\O{n^2}$ operations and the outcome are the
numbers $\{f[x_0,\ldots,x_k]\}_{k=0}^n$.

We now provide an alternative representation of the interpolating
polynomial. 

{\bf Theorem.} Suppose that $x_0,\ldots,x_n$ are pairwise distinct
and the polynomial $p_n \in \BB{P}_n$ interpolates $f$ at these points. 
Then it may be written in the ({\em Newton}) form
$$
    p_n(x)
  = f[x_0] + f[x_0,x_1](x-x_0) % + f[x_0,x_1,x_2](x-x_0)(x-x_1) 
  + \cdots + f[x_0,\ldots,x_n]\prod_{i=0}^{n-1}(x-x_i).
$$
\hspace*{8pt}{\bf Proof.} By induction on $n$. The statement is
obvious for $n=0$ and we suppose that it is true for $n$. 
To prove its validity for $n+1$, we have to prove that 
$$ 
   p_{n+1}(x) - p_n(x) 
 = f[x_0,\ldots,x_{n+1}]\prod_{i=0}^{n}(x-x_i).
$$
Set $r := p_{n+1}-p_{n}$. Then $r\in\BB{P}_{n+1}[x]$ 
and $r(x_i)=0$, $i=0,\ldots,n$. Thus, $r(x) = 
\mbox{const}\times\prod_{i=0}^{n}(x-x_i)$, the constant 
being the leading coefficient of $r$. But the leading coefficient
of $r$ is equal to the leading coefficient of $p_{n+1}$
i.e., to $f[x_0,\ldots,x_{n+1}]$ and we are done. \QED

We have derived the {\em Newton interpolation formula,\/} which requires
only the top row of the divided difference table. It has several 
advantages over Lagrange's.
In particular, its evaluation at a given
point $x$ (provided that divided differences are known) requires just
$\O{n}$ operations, as long as we do it by the {\em Horner scheme\/}
%
\begin{Eqnarray*}
    p_n(x)
&=& \left\{\cdots\left\{\left\{ 
    f[x_0,\ldots,x_n](x-x_{n-1})
    + f[x_0,\ldots,x_{n-1}]\right\}\times (x-x_{n-2})
    + f[x_0,\ldots,x_{n-2}]\right\}\right.\\
& & \quad\left.\mbox{}\times(x-x_{n-3}) + \cdots\right\}+f[x_0].
\end{Eqnarray*}
%
On the other hand, the Lagrange formula is often better when we wish
to manipulate the interpolation polynomial as part of a larger
mathematical expression. We'll see an example in the section on {\em
  Gaussian quadrature.\/}

\section{Orthogonal polynomials}

\subsection{Orthogonality in general linear spaces}

We have already seen the scalar product 
$\langle\MM{x},\MM{y}\rangle=\sum_{i=1}^n x_iy_i$, 
acting on $\MM{x},\MM{y}\in\BB{R}^n$. 
Likewise, given arbitrary {\em weights\/} $w_1,w_2,\ldots,w_n>0$, 
we may define $\langle \MM{x},\MM{y}\rangle=\sum_{i=1}^n w_ix_iy_i$. 

In general, a {\em  scalar\/} (or {\em inner\/}) {\em product\/} is any
function  $\BB{V}\times\BB{V}\rightarrow\BB{R}$, where $\BB{V}$ is a 
vector space over the reals, subject to the following three axioms:\\
%
\hspace*{2ex}
\textit{\textbf{Symmetry:}\/} $\langle \MM{x},\MM{y}\rangle=\langle
\MM{y},\MM{x}\rangle$ $\forall \MM{x},\MM{y}\in \BB{V}$;\\
%
\hspace*{2ex}
\textit{\textbf{Nonnegativity:}\/} $\langle \MM{x},\MM{x}\rangle\geq0$ 
$\forall \MM{x}\in\BB{V}$ and $\langle \MM{x},\MM{x}\rangle=0$ iff
$\MM{x}=\MM{0}$; and\\
%
\hspace*{2ex}
\textit{\textbf{Linearity:}\/} 
$\langle a\MM{x}+b\MM{y},\MM{z}\rangle=a\langle\MM{x},\MM{z}\rangle
+b\langle\MM{y},\MM{z}\rangle$ $\forall \MM{x},\MM{y},\MM{z}\in
\BB{V}$, $a,b\in\BB{R}$.\\   
%
Given a scalar product, we may define {\em orthogonality:\/}
$\MM{x},\MM{y}\in\BB{V}$ are orthogonal if
$\langle\MM{x},\MM{y}\rangle=0$.
 
Let $\BB{V}=C[a,b]$, $w\in\BB{V}$ be a fixed {\em positive\/}
function and define $\langle f,g\rangle:=\int_a^b w(x)f(x)g(x)\D x$
for all $f,g\in\BB{V}$. It is easy to verify all three axioms of
the scalar product.

\subsection{Orthogonal polynomials -- definition, existence,
uniqueness}

Given a scalar product in $\BB{V}=\BB{P}_n[x]$,
we say that $p_n\in\BB{P}_n[x]$ is the $n$th {\em orthogonal
polynomial\/} if $\langle p_n,p\rangle=0$ for all $p\in
\BB{P}_{n-1}[x]$. {\em [Note: different inner products lead to
  different orthogonal polynomials.]\/} A polynomial in $\BB{P}_n[x]$
is {\em monic\/} if the coefficient of $x^n$ therein equals one.

{\bf Theorem.} 
For every $n\geq0$ there exists a unique monic
orthogonal polynomial of degree $n$. Moreover, any $p\in\BB{P}_n[x]$
can be expanded as a linear combination of $p_0,p_1,\ldots,p_n$,\\
%
\hspace*{8pt}{\bf Proof.} We let $p_0(x)\equiv1$ and prove the theorem
by induction on $n$. Thus, suppose that $p_0,\ldots,p_n$ have been
already derived consistently with both assertions of the theorem and
let $q(x):=x^{n+1}\in\BB{P}_{n+1}[x]$. Motivated by the {\em
Gram--Schmidt algorithm,\/} we choose
\begin{equation}\label{7.1}
p_{n+1}(x)=q(x)-\sum_{k=0}^n \frac{\langle q,p_k\rangle}{\langle
p_k,p_k\rangle}p_k(x),\qquad x\in\BB{R}.
\end{equation}
Clearly, $p_{n+1}\in\BB{P}_{n+1}[x]$ and it is monic (since all the
terms in the sum are of degree $\leq n$).\\
Let $m\in\{0,1,\ldots,n\}$. It follows from \R{7.1} and the induction
hypothesis that
$$\langle p_{n+1},p_m\rangle=\langle q,p_m\rangle -\sum_{k=0}^n
\frac{\langle q,p_k\rangle}{\langle p_k,p_k\rangle} \langle p_k,p_m
\rangle=\langle q,p_m\rangle-\frac{\langle q,p_m\rangle}{\langle
p_m,p_m\rangle} \langle p_m,p_m\rangle=0.$$
Hence, $p_{n+1}$ is orthogonal to $p_0,\ldots,p_n$. Consequently,
according to the second inductive assertion, it is orthogonal to all
$p\in\BB{P}_n[x]$.\\
%
\hspace*{8pt}
To prove uniqueness, we suppose the existence of two monic orthogonal
polynomials $p_{n+1},\tilde{p}_{n+1}\in\BB{P}_{n+1}[x]$. Let
$p:=p_{n+1}-\tilde{p}_{n+1}\in\BB{P}_n[x]$, hence $\langle
p_{n+1},p\rangle =\langle \tilde{p}_{n+1},p\rangle=0$, and this
implies
$$0=\langle p_{n+1},p\rangle-\langle \tilde{p}_{n+1},p\rangle
=\langle p_{n+1}-\tilde{p}_{n+1},p\rangle=\langle p,p\rangle,$$
and we deduce $p\equiv0$.\\
%
\hspace*{8pt}
Finally, in order to prove that each $p\in\BB{P}_{n+1}[x]$ is a linear
combination of $p_0,\ldots,p_{n+1}$, we note that we can always write
it in the form $p=c p_{n+1}+q$, where $c$ is the coefficient of
$x^{n+1}$ in $p$ and where $q\in\BB{P}_n[x]$. According to the
induction hypothesis, $q$ can be expanded as a linear combination of
$p_0,p_1,\ldots,p_n$, hence our assertion is true. \QED

Well-known examples of orthogonal polynomials include
\begin{center}
\begin{tabular}{|l||c|c|c|} \hline\\[-2ex]
  \multicolumn{1}{|c||}{Name} & Notation & Interval 
  & {Weight function}
  \\\hline\\[-2ex] 
  Legendre  & $P_n$ & $[-1,1]$           & $w(x)\equiv1$\\[1ex]
  Chebyshev & $T_n$ & $[-1,1]$           &$w(x)=(1-x^2)^{-1/2}$\\[1ex]
  Laguerre  & $L_n$ & $[0,\infty)$       & $w(x)=\E^{-x}$\\[1ex]
  Hermite   & $H_n$ & $(-\infty,\infty)$ & $w(x)=\E^{-x^2}$ \\[1ex]\hline 
\end{tabular}
\end{center}

\end{document}


