Orthogonal polynomials - Numerical Analysis

We go back to orthogonal polynomials and establish some results that are useful for further topics on numerical integration. We recall two results. If $\{\phi_n\}$ are orthogonal polynomials wrt some inner product and degree $\phi_n = n$ , and if $f \in \poly_n$ we can write it as

f(x) = \sum_{j=0}^n c_j \phi_j(x), \qquad c_j = \frac{\ip{f,\phi_j}}{\ip{\phi_j,\phi_j}}

(1)

1Roots of orthogonal polynomials¶

Proof 1

Let $x_1, x_2, \ldots, x_m$ be all the distinct zeros of $\phi_n$ for which

$a < x_i < b$
$\phi_n$ changes sign at $x_i$

i.e., there are $m$ roots each with odd multiplicity in $(a,b)$ . This includes all the simple roots also. There might be other roots outside the interval $(a,b)$ and there could be roots with even multiplicity in $(a,b)$ . Since degree $\phi_n = n$ , we have $m \le n$ . Now since $\phi_n$ is orthogonal to $\phi_0 =$ constant,

\int_a^b w(x) \phi_n(x) \ud x = 0, \qquad n \ge 1

(2)

$\implies$ each $\phi_n$ has atleast one root in $(a,b)$ , i.e., $m \ge 1$ .

Let us assume that $m < n$ and derive a contradiction. We can write

\phi_n(x) = (x-x_1)^{r_1} \ldots (x-x_m)^{r_m} h(x)

(3)

Each $r_i$ is odd and other roots are roots of $h(x)$ . Define

B(x) = (x-x_1) \ldots (x-x_m)

(4)

so that

B(x) \phi_n(x) = (x-x_1)^{r_1+1} \ldots (x-x_m)^{r_m+1} h(x)

(5)

$h(x)$ does not change sign in $(a,b)$ and since each $r_i+1$ is even, $B(x)\phi_n(x)$ does not change sign in $(a,b)$ . Hence

\int_a^b w(x) \phi_n(x) B(x) \ud x = \ip{B, \phi_n} \ne 0

(6)

But degree of $B = m < n$ so that $\ip{B,\phi_n} = 0$ which leads to a contradiction. Hence $m=n$ . Since $\phi_n$ has atmost $n$ roots, the multiplicity of each $x_i$ is one. Hence $\phi_n$ has $n$ distinct roots.

2Triple recursion relation¶

Let $\{ \phi_n \}$ be an orthogonal sequence of polynomials on $[a,b]$ with weight function $w$ and degree $\phi_n = n$ for all $n$ . Define $A_n$ and $B_n$ by

\phi_n(x) = A_n x^n + B_n x^{n-1} + \ldots

(7)

Also write

\phi_n(x) = A_n (x- x_{n,1}) \ldots (x-x_{n,n})

(8)

Let

a_n = \frac{A_{n+1}}{A_n}, \qquad \gamma_n = \ip{\phi_n, \phi_n} > 0

(9)

Proof 2

(a) Consider the polynomial

\begin{aligned} G(x) &= \phi_{n+1}(x) - a_n x \phi_n(x) \\ &= [A_{n+1} x^{n+1} + B_{n+1} x^n + \ldots] - \frac{A_{n+1}}{A_n} x [A_n x^n + B_n x^{n-1} + \ldots ] \\ &= \left[ B_{n+1} - \frac{A_{n+1} B_n}{A_n} \right] x^n + \ldots \end{aligned}

(12)

and hence degree $G \le n$ . We can write $G$ as

G(x) = d_0 \phi_0 + \ldots + d_n \phi_n(x)

(13)

where

d_i = \frac{\ip{G,\phi_i}}{\ip{\phi_i,\phi_i}} = \frac{1}{\gamma_i}[ \ip{\phi_{n+1}, \phi_i} - a_n \ip{x \phi_n, \phi_i} ], \qquad 0 \le i \le n

(14)

But

\begin{align*} \ip{\phi_{n+1},\phi_i} &= 0, \qquad 0 \le i \le n \\ \ip{x\phi_n, \phi_i} &= \ip{\phi_n, x \phi_i} = 0, \qquad i+1 < n \quad i.e., \quad 0 \le i \le n-2 \\ \implies d_i &= 0, \qquad 0 \le i \le n-2 \end{align*}

(15)

so that

G(x) = d_n \phi_n(x) + d_{n-1} \phi_{n-1}(x)

(16)

\phi_{n+1}(x) = (a_n x + d_n) \phi_n(x) + d_{n-1} \phi_{n-1}(x)

(17)

We have a triple recursion formula and it remains to show that $d_{n-1} = -c_n$ and $d_n = b_n$ where $b_n, c_n$ are as defined in the theorem.

(b) $d_{n-1}$ is given by

d_{n-1} = - \frac{a_n}{\gamma_{n-1}} \ip{\phi_n, x\phi_{n-1}}

(18)

Now

\begin{aligned} x\phi_{n-1}(x) &= A_{n-1} x^n + B_{n-1} x^{n-1} + \ldots \\ &= A_{n-1} \frac{1}{A_n}[\phi_n(x) - B_n x^{n-1} - \ldots] + B_{n-1} x^{n-1} + \ldots \end{aligned}

(19)

so that

\ip{\phi_n, x\phi_{n-1}} = \frac{A_{n-1}}{A_n} \ip{\phi_n, \phi_n} = \frac{A_{n-1}\gamma_n}{A_n}

(20)

and hence

d_{n-1} = -\frac{a_n}{\gamma_{n-1}} \frac{A_{n-1}\gamma_n}{A_n} = -\frac{A_{n-1}A_{n+1}}{A_n^2} \frac{\gamma_n}{\gamma_{n-1}} = -c_n

(21)

d_{n} = - \frac{a_n}{\gamma_{n}} \ip{\phi_n, x\phi_{n}}

(22)

Now

\begin{aligned} x\phi_n(x) &= A_n x^{n+1} + B_n x^n + \ldots \\ &= A_n \frac{1}{A_{n+1}}[ \phi_{n+1}(x) - B_{n+1} x^n - \ldots ] + B_n \frac{1}{A_n}[ \phi_n(x) - B_n x^{n-1} - \ldots ] \\ & \quad + ()x^{n-1} + \ldots \end{aligned}

(23)

so that

\ip{\phi_n ,x\phi_n} = - \frac{A_n B_{n+1}}{A_{n+1}} \ip{\phi_n, x^n} + \frac{B_n}{A_n} \underbrace{\ip{\phi_n, \phi_n}}_{=\gamma_n}

(24)

But

\begin{align*} \ip{\phi_n, x^n} &= \ip{\phi_n, \frac{1}{A_n}[\phi_n - B_n x^{n-1} - \ldots]} = \frac{1}{A_n} \ip{\phi_n,\phi_n} = \frac{\gamma_n}{A_n} \\ \implies \ip{\phi_n ,x\phi_n} &= -\frac{B_{n+1} \gamma_n}{A_{n+1}} + \frac{B_n \gamma_n}{A_n} \\ \implies d_n &= a_n \left[ \frac{B_{n+1}}{A_{n+1}} - \frac{B_n}{A_n} \right] = b_n \end{align*}

(25)

3A useful identity¶

We will use the next identity to derive simpler formula for the quadrature weights.

Proof 3

Using the triple recursion relation, we can write

\begin{aligned} \phi_n(y) \cdot [\phi_{n+1}(x) &= (a_n x + b_n) \phi_n(x) - c_n \phi_{n-1}(x) ] \\ \phi_n(x) \cdot [\phi_{n+1}(y) &= (a_n y + b_n) \phi_n(y) - c_n \phi_{n-1}(y) ] \end{aligned}

(27)

Subtracting

\begin{align*} \phi_{n+1}(x) \phi_n(y) - \phi_n(x) \phi_{n+1}(y) &= a_n (x-y) \phi_n(x) \phi_n(y) \\ & \quad + c_n[ \phi_n(x) \phi_{n-1}(y) - \phi_{n-1}(x) \phi_n(y) ] \end{align*}

(28)

and

\begin{aligned} & \frac{\phi_{n+1}(x) \phi_n(y) - \phi_n(x) \phi_{n+1}(y)}{a_n \gamma_n (x-y)} \\ &= \frac{\phi_n(x) \phi_n(x)}{\gamma_n} + \frac{c_n}{a_n \gamma_n} \frac{ \phi_n(x) \phi_{n-1}(y) - \phi_{n-1}(x) \phi_n(y) }{x-y} \\ &= \frac{\phi_n(x) \phi_n(x)}{\gamma_n} + \frac{ \phi_n(x) \phi_{n-1}(y) - \phi_{n-1}(x) \phi_n(y) }{a_{n-1} \gamma_{n-1} (x-y)} \end{aligned}

(29)

since

\frac{c_n}{a_n \gamma_n} = \frac{1}{a_{n-1} \gamma_{n-1}}

(30)

Repeating this process, we get

\frac{\phi_{n+1}(x) \phi_n(y) - \phi_n(x) \phi_{n+1}(y)}{a_n \gamma_n (x-y)} = \sum_{k=1}^n \frac{\phi_k(x) \phi_k(y)}{\gamma_k} + \frac{ \phi_1(x) \phi_{0}(y) - \phi_{0}(x) \phi_1(y) }{a_{0} \gamma_{0} (x-y)}

(31)

But

\begin{align*} \frac{ \phi_1(x) \phi_{0}(y) - \phi_{0}(x) \phi_1(y) }{a_{0} \gamma_{0} (x-y)} &= \frac{(A_1 x + B_1) A_0 - A_0 (A_1 y + B_1)}{(A_1/A_0) \gamma_0 (x-y)} \\ &= \frac{A_0^2}{\gamma_0} \\ &= \frac{\phi_0(x) \phi_0(y)}{\gamma_0} \end{align*}

(32)

which completes the proof.

Numerical Analysis

Gauss quadrature - I

Numerical Analysis

Gauss quadrature - II