\documentclass[twoside]{article}

\usepackage{palatino}
\usepackage{camnum}

\newcommand {\ip[1]} {\langle{#1}\rangle}



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

\setcounter{section}{7}
\setcounter{subsection}{2}
\setcounter{equation}{1}

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

  {\Large \textbf{Numerical Analysis -- Lecture
      10\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 three-term recurrence relation}

How to construct orthogonal polynomials? $(7.1)$ might help, but it
suffers from the same problem as the Gram--Schmidt algorithm in
Euclidean spaces: loss of accuracy due to imprecisions in the
calculation of scalar products. A
considerably better procedure follows from our next theorem.

{\bf Lemma.} Let $(p_k)_{k=0}^n$ be the sequence of orthogonal
polynomials. Then, for all $p\in\BB{P}_n$, 
\begin{equation}
   p = \sum_{k=0}^n c_k p_k, \qquad c_k = \frac{\ip[p,p_k]}{\ip[p_k,p_k]}
\label{7.2}
\end{equation}
\hspace*{8pt}{\bf Proof.} By the previous theorem, 
an expansion exists. The scalar product of both sides with $p_k$ gives
$\ip[p,p_k] = c_k \ip[p_k,p_k]$, hence the expression for $a_k$  \QED


{\bf Theorem.} Monic orthogonal polynomials are given by the formula
%
\begin{eqnarray}
   p_{-1}(x) & \equiv& 0, \qquad
   p_0(x)      \equiv  1, \nonumber \\
   p_{n+1}(x) &=& (x-\alpha_n)p_n(x)-\beta_n p_{n-1}(x),\qquad
   n=0,1,\ldots
\label{7.3}
\end{eqnarray}
where
$$
    \alpha_n:=\frac{\ip[xp_n,p_n]}{\ip[p_n,p_n]}, \qquad 
     \beta_n:=\frac{\ip[p_n,p_n]}{\ip[p_{n-1},p_{n-1}]} > 0.
$$
%
\hspace*{8pt}{\bf Proof.} 
Based on $(7.2)$, let us look at the coefficients of the expansion
$$
   x p_n(x) =  \sum_{k=0}^{n+1} c_k p_k(x), \qquad 
   c_k = \frac{\ip[xp_n,p_k]}{\ip[p_k,p_k]}
       = \frac{\ip[p_n,xp_k]}{\ip[p_k,p_k]}
$$
\begin{tabbing}
\hspace*{8pt}
$k=n+1$ \= $\;\leadsto\;$ $c_{n+1}=1$, since both $x p_n(x)$ and $p_{n+1}(x)$ 
are monic polynomials of degree $n+1$.\\
\hspace*{8pt}
$k=n$ \> $\;\leadsto\;$ By definition $c_n = \alpha_n$.\\ 
\hspace*{8pt}
$k=n-1$ \> $\;\leadsto\;$ Because of monicity, we have the equality
$xp_{n-1} = p_n + q$ with some $q\in\BB{P}_{n-1}$, \\
\> \phantom{$\;\leadsto\;$} so that $\ip[p_n,xp_{n-1}] = \ip[p_n,p_n]$, 
hence $c_{n-1} = \beta_n$. \\
\hspace*{8pt}
$k < n-1$ \> $\;\leadsto\;$ Since $xp_k\in\BB{P}_{n-1}$, 
we obtain $\ip[p_n,xp_k]=0$, thus $c_k = 0$.
\end{tabbing}
\vspace*{-2ex}
It folows that 
$
   xp_n(x) = p_{n+1} + \alpha_n p_n + \beta_n p_{n-1},
$
and that is equivalent to $(7.3)$. \QED

{\bf Example} ({\em Chebyshev polynomials\/}). 
We choose the scalar product 
$$
    \langle f,g\rangle
 := \int_{-1}^1 f(x)g(x)\frac{\D x}{\sqrt{1-x^2}},\qquad f,g\in C[-1,1]
$$
and define $T_n\in\BB{P}_n$ by the relation
$T_n(x)=\cos (n\theta)$ where $x = \cos\theta$. 
Hence $T_0(x)\equiv1$, $T_1(x)=x$, $T_2(x)=2x^2-1$ etc. 
Changing the integration variable,
\begin{Eqnarray*}
\langle T_n,T_m\rangle&=&\int_{-1}^1 T_n(x)T_m(x)\frac{\D
x}{\sqrt{1-x^2}} =\int_0^\pi \cos n\theta \cos m\theta \D\theta\\
&=&\Frac12\int_0^\pi [\cos(n+m)\theta+\cos(n-m)\theta]\D\theta=0
\end{Eqnarray*}
whenever $n\neq m$. The recurrence relation for Chebyshev
polynomials is particularly simple,
$$T_{n+1}(x)=2x T_n(x)-T_{n-1}(x),$$
as can be verified at once from the identity
$$\cos[(n+1)\theta]+\cos[(n-1)\theta]=2\cos(\theta)\cos (n\theta).$$
Note that the $T_n$s aren't monic, hence the inconsistency with
\R{7.3}. To obtain monic polynomials take $T_n(x)/2^{n-1}$, $n\geq1$.

\subsection{Least-squares polynomial fitting}

Consider the space $C[a,b]$ with the scalar product 
$\ip[g,h] = \int_a^b g(x)h(x)w(x)\D x$, $w(x) > 0$, and the 
underlying norm $\|f\| := \ip[f,f]^{1/2}$.

Given $f\in C[a,b]$, 
we wish to pick $p\in\BB{P}_n$ so as to minimise $\|f-p\|$. 
Intuitively speaking, $p$ approximates $f$ and is an alternative to an
interpolating polynomial. (The situation is similar to the one that we
have already encountered in numerical linear algebra, least-squares'
fitting {\em vs\/} solving linear equations.)

Let $p_0,p_1,\ldots,p_n$ be ortho{\em normal} polynomials w.r.t.\ 
the underlying inner product, i.e., $p_k\in\BB{P}_k$, 
$\ip[p_k,p_\ell] = \delta_{k\ell}$. 
They form a basis of $\BB{P}_n$, therefore every $p\in\BB{P}_n$ 
can be written as $p=\sum_{k=0}^n c_k p_k$.  
Because of orthonormality,
$$
   \ip[f-p,f-p] 
 = \left\langle f-\sum_{k=0}^n c_k p_k,
                f-\sum_{k=0}^n c_k p_k\right\rangle 
 = \ip[f,f] - 2\sum_{k=0}^n c_k \ip[p_k,f] + \sum_{k=0}^n c_k^2,
$$
and if we set $a_k := \ip[p_k,f]$, then we can rewrite the right-hand side as
$$
   \ip[f-p,f-p] 
 = \ip[f,f] - \sum_{k=0}^n a_k^2 + \sum_{k=0}^n (a_k-c_k)^2
$$
Since $a_k$'s are independent of $p$, 
it is clear that the minimum occurs iff $c_k = a_k$. 
Thus, the optimal $p^* \in \BB{P}_n$ is given by
%
\begin{equation}
   p^* = \sum_{k=0}^n a_k p_k = \sum_{k=0}^n \ip[p_k,f] p_k, \qquad 
   \|p^*\|^2 =  \sum_{k=0}^n \ip[p_k,f]^2,
\label{7.4}
\end{equation} 
%
and
%
\begin{equation}
   \|f-p^*\|^2 = \|f\|^2 - \sum_{k=0}^n \ip[p_k,f]^2 = \|f\|^2 - \|p^*\|^2.
\label{7.5}
\end{equation} 
%
The latter identity is a 
%can be rewritten as  $\|f-p^*\|^2 + \|p^*\|^2 =  \|f\|^2$,
reminiscent of the Pythagoras theorem.

{\bf How to choose $n$?} Note that $a_k=\ip[p_k,f]$ is independent of $n$. 
Thus, we can continue to add terms to \R{7.4} 
until $\|f-p^*\|^2$ is below specified
{\em tolerance\/} $\varepsilon$. Because of \R{7.5}, we need to pick $n$
so that $\sum_{k=0}^n \ip[p_k,f]^2 >  \|f\|^2 - \varepsilon$.

{\bf Theorem} ({\em The Parseval identity\/}). Let $[a,b]$ be finite.
Then
%
\begin{equation}\label{7.6}
   \sum_{k=0}^\infty \ip[p_k,f]^2 = \|f\|^2
\end{equation}
%
\hspace*{8pt} {\bf Incomplete proof.} 
Let 
$$ 
   \sigma_n: = \|p^*\|^2 = \sum_{k=0}^n  \ip[p_k,f]^2,
$$
hence $\inf\limits_{p\in P_n}\|f-p\|^2 = \|f-p^*\|^2 = \|f\|^2 - \sigma_n$. 
%The sequence $\{\sigma\}_{n=0}^\infty$ increases monotonically and
%$\sigma_n \leq \|f\|^2$ implies that $\lim_{n\to\infty}\sigma_n$ exists. 
%
According to the {\em Weierstrass theorem\/}, 
any function in $C[a,b]$ can be approximated arbitrarily close 
by a polynomial, hence $\lim\limits_{n\to\infty}\inf\limits_{p\in P_n} \|f-p\|^2=0$ 
and we deduce  that 
$\sigma_n\stackrel{n\rightarrow\infty}{\longrightarrow}\|f\|^2$
and \R{7.6} is true. \QED 

\end{document}
