10. Orthogonal Polynomials

Gram-Schmidt Orthogonalisation Procedure

Consider normal equation $A\alpha =\phi$

Let $\{{\varphi }_0,{\varphi }_1,\cdots ,{\varphi }_n\}$ be a basis for ${\Pi }_n$ then

$$p_n(x)=\sum _{k=0}^n{\beta }_k{\varphi }_k(x)$$

So normal equations for $A\alpha =\varphi$ are

$${\int }_a^{b}w(x)\left(f(x)-\sum _{k=0}^n{\beta }_k{\varphi }_k(x)\right){\varphi }_i(x)dx=0\text{ for }i=0,1,\cdots ,n$$

So in other words

$$\sum _{k=0}^n\left({\int }_a^{b}w(x){\varphi }_k(x){\varphi }_i(x)dx\right){\beta }_k={\int }_a^{b}w(x)f(x){\varphi }_i(x)dx\text{ for }i=0,1,\cdots ,n$$

Hence

$$A\beta =\phi$$

where $\beta =({\beta }_0,{\beta }_1,\cdots ,{\beta }_n{)}^T$ and $\phi =(f_1,f_2,\cdots ,f_n{)}^T$ and

$$a_{i,k}={\int }_a^{b}w(x){\varphi }_k(x){\varphi }_i(x)dx\text{ and }{f}_i={\int }_a^{b}w(x)f(x){\varphi }_i(x)dx$$

Hence $A$ is diagonal if

$$⟨{\varphi }_i,{\varphi }_k⟩={\int }_a^{b}w(x){\varphi }_i(x){\varphi }_k(x)dx\{\begin{array}{ll}=0& \text{ if }i\ne k\\ \ne 0& \text{ if }i=k\end{array}$$

where set of orthogonal polynomials can be produced below

Link to original

Construction of Orthogonal Polynomials via Gram–Schmidt lemma

Let ${\varphi }_0,\cdots ,{\varphi }_k$ with ${\varphi }_i\in {\Pi }_i$ for each $i$ are orthogonal with respect to inner product

$$⟨f,g⟩={\int }_a^{b}w(x)f(x)g(x)dx$$

Then

$${\varphi }_{k+1}(x)=x^{k+1}-\sum _{i=0}^k{\lambda }_i{\varphi }_i(x)$$

satisfies

$$⟨{\varphi }_{k+1},{\varphi }_j⟩={\int }_a^{b}w(x){\varphi }_{k+1}(x){\varphi }_j(x)dx=0\text{ for }j=0,1,\cdots ,k$$

with

$${\lambda }_j=\frac{⟨x^{k+1},{\varphi }_j⟩}{⟨{\varphi }_j,{\varphi }_j⟩}\text{ for }j=0,1,\cdots ,k$$

Proof

For any $j$ and $0\le j\le k$ then

$$\begin{array}{rl}⟨{\varphi }_{k+1},{\varphi }_j⟩& =⟨x^{k+1},{\varphi }_j⟩-\sum _{i=0}^k{\lambda }_i⟨{\varphi }_i,{\varphi }_j⟩\\ & =⟨x^{k+1},{\varphi }_j⟩-{\lambda }_j⟨{\varphi }_j,{\varphi }_j⟩\\ & \text{ by orthogonality of }{\varphi }_i\text{ and }{\varphi }_j\text{ for }i\ne j\\ & =0\text{ by definition of }{\lambda }_j\end{array}$$

Link to original

Types of Orthogonal Polynomials

Legendre Polynomials

Inner Product defined by

$$⟨f,g⟩={\int }_{-1}^{1}f(x)g(x)dx$$

which gives orthogonal polynomials

$${\varphi }_0(x)\equiv 1,{\varphi }_1(x)=x,{\varphi }_2(x)=x^2-\frac{1}{3},{\varphi }_3(x)=x^3-\frac{3}{5}x,\cdots$$

Chebyshev Polynomials

Inner Product defined by

$$⟨f,g⟩={\int }_{-1}^1\frac{f(x)g(x)}{\sqrt{1-x^2}}dx$$

which gives orthogonal polynomials

$${\varphi }_0(x)\equiv 1,{\varphi }_1(x)=x,{\varphi }_2(x)=2x^2-1,{\varphi }_3(x)=4x^3-3x,\cdots$$

Laguerre Polynomials

Inner Product defined by

$$⟨f,g⟩={\int }_{-1}^1{e}^{-x}f(x)g(x)dx$$

which gives orthogonal polynomials

$${\varphi }_0(x)\equiv 1,{\varphi }_1(x)=1-x,{\varphi }_2(x)=2-4x+x^2,{\varphi }_3(x)=6-18x+9x^2-x^3,\cdots$$

Link to original

Orthogonal Polynomials Annihilate Lower-Degree Polynomials lemma

Let $\{{\varphi }_0,{\varphi }_1,\cdots ,{\varphi }_k,\cdots \}$ be orthogonal polynomials for inner product $⟨\cdot ,\cdot ⟩$

Then

$$⟨{\varphi }_k,q⟩=0\text{ for all }q\in {\Pi }_{k-1}$$

Proof

If $q\in {\Pi }_{k-1}$ then

$$q(x)=\sum _{i=0}^{k-1}{\sigma }_i{\varphi }_i(x)\text{ for }{\sigma }_i\in \mathbb{R},i=0,1,\cdots ,k-1$$

Hence

$$⟨{\varphi }_k,q⟩=\sum _{i=0}^{k-1}{\sigma }_i⟨{\varphi }_k,{\varphi }_i⟩=0$$

Link to original

Three-Term Recurrence Relation for Orthogonal Polynomials

Let $\{{\varphi }_0,{\varphi }_1,\cdots {\varphi }_n,\cdots \}$ be a set of orthogonal polynomials

There exists sequences of real numbers

$$({\alpha }_k{)}_{k=1}^{\infty },({\beta }_k{)}_{k=1}^{\infty },({\gamma }_k{)}_{k=1}^{\infty }$$

such that a three-term recurrence relation holds of form

$${\varphi }_{k+1}(x)={\alpha }_k(x-{\beta }_k){\varphi }_k(x)-{\gamma }_k{\varphi }_{k-1}(x),k=1,2,\cdots$$

Proof

Polynomial $x{\varphi }_k\in {\Pi }_{k+1}$ so exists real numbers

$${\sigma }_{k,0},{\sigma }_{k,1},\cdots ,{\sigma }_{k,k+1}$$

such that

$$x{\varphi }_k(x)=\sum _{i=0}^{k+1}{\sigma }_{k,i}{\varphi }_i(x)$$

as $\{{\varphi }_0,{\varphi }_1,{\varphi }_{k+1}\}$ is a basis for ${\Pi }_{k+1}$

For $j\le k-2$ then

$$⟨x{\varphi }_k,{\varphi }_j⟩={\int }_a^{b}w(x)x{\varphi }_k(x){\varphi }_j(x)dx={\int }_a^{b}w(x){\varphi }_k(x)x{\varphi }_j(x)dx=⟨{\varphi }_k,x{\varphi }_j⟩=0$$

as $x{\varphi }_j\in {\Pi }_{k-1}$ and

$$⟨\sum _{i=0}^{k+1}{\sigma }_{k,i}{\varphi }_i,{\varphi }_j⟩=\sum _{i=0}^{k+1}{\sigma }_{k,i}⟨{\varphi }_i,{\varphi }_j⟩={\sigma }_{k,j}⟨{\varphi }_j,{\varphi }_j⟩$$

by linearity of $⟨\cdot ,\cdot ⟩$ and orthogonality of ${\varphi }_i$ and ${\varphi }_j$ for $i\ne j$

Hence ${\sigma }_{k,j}=0$ for $j\le k-2$ hence

$$x{\varphi }_k(x)={\sigma }_{k,k+1}{\varphi }_{k+1}(x)+{\sigma }_{k,k}{\varphi }_k(x)+{\sigma }_{k,k-1}{\varphi }_{k-1}(x)$$

Thus

$$⟨x{\varphi }_k,{\varphi }_{k+1}⟩={\sigma }_{k,k+1}⟨{\varphi }_{k+1},{\varphi }_{k+1}⟩$$

So ${\sigma }_{k,k+1}\ne 0$ as $x{\varphi }_k$ is of exact degree $k+1$

Thus

$${\varphi }_{k+1}(x)=\frac{1}{{\sigma }_{k,k+1}}(x-{\sigma }_{k,k}){\varphi }_k(x)-\frac{{\sigma }_{k,k-1}}{{\sigma }_{k,k+1}}{\varphi }_{k-1}(x)$$

so

$${\alpha }_k=\frac{1}{{\sigma }_{k,k+1}},{\beta }_k={\sigma }_{k,k},{\gamma }_k=\frac{{\sigma }_{k,k-1}}{{\sigma }_{k,k+1}}\text{ for }k=1,2,\cdots$$

Link to original