\centerline{\bf ORTHOGONAL POLYNOMIALS} \bigskip 
Let $w:(a,b)\to E$ be continuous, nonnegative, and integrable, with at
most isolated zeros on $(a,b)$. Then $$\la f,g\ra=\int_a^b
f(x)g(x)w(x)\,dx$$ defines an inner product on the vector space
$V=\left\{f\in C(a,b)\mid \int_a^b [f(x)]^2 w(x)dx<\infty\right\}$.
Given distinct points $x_1$, $\ldots$, $x_M\in[a,b]$ and positive
constants $w_1$, $\ldots$, $w_M$, $$\la f,g\ra= \sum_{i=1}^M
f(x_i)g(x_i)w_i$$ defines a (discrete) inner product on any vector space
of functions $V$ with the property that $f\in V$, $f(x_1)=\cdots=
f(x_M)=0 \Rightarrow f\equiv0$. In the following, $\la f,g\ra$
can be either a continuous (integral) or a discrete (sum) inner product.

\noindent{\bf Definition}. $\{Q_i\}_{i=0}^m$ ($m+1<M$ in the discrete
case) is a sequence of orthogonal polynomials on $(a,b)$ with weight
$w(x)$ (with respect to the points $x_i$ and weights $w_i$, in the
discrete case) if
\item{(1)}$Q_i(x)\in {\cal P}_i$ has exact degree $i$ for $i=0,1,\ldots,
m$; \item{(2)}$\la Q_i,Q_j\ra=0$ for $i\ne j$.

\medskip\noindent{\bf Theorem}. Let $\{Q_k\}_{k=0}^m$ be a sequence of
orthogonal polynomials, and let $\alpha_k\ne0$ be the leading
coefficient of $Q_k$. Then
\item{(1)}any polynomial of degree $n\le m$ is a unique linear
combination of $Q_0$, $\ldots$, $Q_n$;
\item{(2)}$Q_n$, for $0<n\le m$, is orthogonal to any polynomial of
degree $\le n-1$;
\item{(3)}all the zeros of $Q_n$, for $0<n\le m$, are real, distinct,
and lie in $(a,b)$;
\item{(4)}the $Q_n$ satisfy a three term recurrence relation:
$$Q_{n+1}(x)=A_n(x-B_n)Q_n(x)-C_nQ_{n-1}(x),\qquad n=0,1,\ldots,m-1,$$
where $$Q_{-1}(x)\equiv0,\quad A_n={\alpha_{n+1}\over\alpha_n},\quad
B_n={\la xQ_n,Q_n\ra\over S_n},\quad 
C_n={A_nS_n\over A_{n-1}S_{n-1}},\quad S_n=\la Q_n,Q_n\ra.$$

\bigskip\hrule\smallskip
{\sl Examples of orthogonal polynomials (name, weight, interval,
recurrence relation)}: $$\vbox{\tabskip=15pt \baselineskip=15pt
\lineskiplimit=3pt \lineskip=3pt
\halign{&\hfil$\displaystyle#$\hfil\cr
\rm Chebyshev&\rm Legendre\cr
w(x)=1/\sqrt{1-x^2}& w(x)=1\cr
[a,b]=[-1,1]&[a,b]=[-1,1]\cr
T_{n+1}(x)=2x\,T_n(x)-T_{n-1}(x)& P_{n+1}(x)={2n+1\over n+1}x\,P_n(x) -
{n\over n+1}P_{n-1}(x)\cr
1&1\cr
x&x\cr
2x^2-1&{3\over2}\left(x^2-{1\over3}\right)\cr
4x^3-3x&{5\over2}\left(x^3-{3\over5}x\right)\cr
8x^4-8x^2+1&{35\over8}\left(x^4-{6\over7}x^2+{3\over35}\right)\cr
}}$$

\vfil
$$\vbox{\tabskip=15pt \baselineskip=15pt
\lineskiplimit=3pt \lineskip=3pt
\halign{&\hfil$\displaystyle#$\hfil\cr
\rm Hermite&\rm Laguerre\cr
w(x)=e^{-x^2}& w(x)=x^\alpha e^{-x},\quad \alpha>-1\cr
(a,b)=(-\infty,\infty)& [a,b)=[0,\infty)\cr
H_{k+1}(x)=2x\,H_k(x)-2k\,H_{k-1}(x)& L_{k+1}^\alpha(x)={-1\over k+1}
(x-2k-\alpha-1)L_k^\alpha(x) \cr
1& - {k+\alpha\over k+1}L_{k-1}^\alpha(x) \cr
2x\cr 4x^2-2\cr 8x^3-12x\cr 16x^4-48x^2+12\cr}}$$

\hrule\medskip
Given $P_S(f)=R(x)=\sum_{k=0}^n \beta_k Q_k(x)$, where $\beta_k=
\la f,Q_k\ra/\la Q_k,Q_k\ra$, and $\{Q_i\}_{i=0}^n$ are
orthogonal, $R(x)$ can be efficiently evaluated using the three term
recurrence relation from above: $$\vbox{\tt \hbox{$d_{n+2}\: d_{n+1}\:
0$;}\hbox{for $k\:n$ step $-1$ until $0$ do}
\hbox{\qquad$d_k\:\beta_k+A_k\bigl(x-B_k\bigr)d_{k+1} -
C_{k+1}d_{k+2}$; \qquad( $R(x)=d_0Q_0(x)$ )}}$$

\vfil\eject