Numerical Analysis HT24, Orthogonal polynomials
Flashcards
Suppose:
- We are in the inner product space where $\langle f, g \rangle = \int^b _ a w(x) f(x) g(x) \text dx$
- $\phi _ 0, \cdots, \phi _ k$ with $\phi _ i \in \Pi _ i$ are an orthogonal collection of polynomials
Can you give an expression for the next orthogonal polynomial?
Suppose:
\[f \in L _ 2^2(a, b)\]
and we are trying to approximate it by some polynomial function
\[p _ n(x) = \sum^n _ {k = 0} \alpha _ k \phi _ k(x)\]
Where $\phi _ k$ is a basis. Then we can form the normal equations for the coefficients, i.e.
\[A \pmb \alpha = \pmb \varphi\]
where
\[(A) _ {ik} := \int^b _ a w(x) \phi _ k(x) \phi _ i(x) \text d x\]
\[\pmb \alpha = (\alpha _ 0, \cdots, \alpha _ n)^\top\]
\[\pmb \varphi _ i = \int^b _ a w(x) f(x) \phi _ i(x) \text d x\]
Why does choosing an orthogonal basis of polynomials make our life easier?
It means $A$ is diagonal, which makes the system of equations easier to solve.
Suppose that $\{\phi _ 0, \phi _ 1, \cdots, \phi _ k, \cdots\}$ are orthogonal polynomials for an inner product $\langle \cdot, \cdot \rangle$. What can you say about $\langle \phi _ k, q \rangle$ for $q \in \Pi _ {k - 1}$?
Suppose $\{\phi _ 0, \phi _ 1, \cdots, \phi _ n, \cdots\}$ is a set of orthogonal polynomials. Quickly prove that there exists sequences of real numbers $(\alpha _ k)^\infty _ {k = 1}$, $(\beta _ k)^\infty _ {k = 1}$, $(\gamma _ k)^\infty _ {k = 1}$ such that a three-term recurrence relation holds of the form
\[\phi _ {k + 1}(x) = \alpha _ k(x - \beta _ k) \phi _ k - \gamma _ k\phi _ {k-1}(x)\]
for $k = 1, 2, \ldots$
(note as stated this makes it seem like the three sequences are not related, they are actually all really derived from a single sequence).
.
Overall idea: Expand $x\phi _ k(x)$ in the orthonormal basis. Then taking the inner product on each side with different $\phi _ j$ means lots of the coefficients (in fact, all but the ones for $\phi _ {k+1}, \phi _ k$ and $\phi _ {k-1}$ disappear and you can rearrange.
Since $x \phi _ k(x) \in \Pi _ {k+1}$, so there exists real numbers
\[C _ {k}^{(0)}, C _ {k}^{(1)}, \cdots, C _ {k}^{(k+1)}\]such that
\[x\phi _ k(x) = \sum^{k + 1} _ {i = 0} C _ {k}^{(i)} \phi _ i (x)\]Taking the inner product on both sides with $\phi _ j$ for $0 \le j \le k - 2$
\[\begin{aligned} \langle x \phi _ k, \phi _ j \rangle &= \int^b _ a w(x) x\phi _ k(x) \phi _ j(x) \text d x \\ &= \int^b _ a w(x) \phi _ k(x)x\phi _ j(x) \text d x \\ &= \langle \phi _ k, x \phi _ j \rangle \\ &= 0 \end{aligned}\]with the last $= 0$ since $x \phi _ j \in \Pi _ {k - 1}$ and so can be expanded in a basis of polynomials orthogonal to $\phi _ k$. But note also
\[\begin{aligned} \langle x\phi _ k, \phi _ j\rangle &= \left\langle \sum^{k + 1} _ {i = 0}C _ {k}^{(i)} \phi _ i, \phi _ j\right\rangle \\ &= \sum^{k+ 1} _ {i = 0} C _ {k}^{(i)} \langle \phi _ i, \phi _ j \rangle \\ &= C _ {k}^{(j)} \langle \phi _ j, \phi _ j \rangle \end{aligned}\]So overall we get that
\[C _ {k}^{(j)} \langle \phi _ j, \phi _ j \rangle = 0\]which implies for all $0 \le j \le k - 2$, $C _ {k}^{(j)} = 0$. Then going back to the original expansion of $x \phi _ k(x)$,
\[x\phi _ k(x) = C _ {k}^{(k+1)} \phi _ {k + 1}(x) + C _ {k}^{(k)} \phi _ k (x) + C _ {k}^{(k-1)} (x) \phi _ {k-1}(x)\]We would like to be able to rearrange to
\[\phi _ {k+1}(x) = \frac{x - C _ {k}^{(k)} }{C _ {k}^{(k+1)}\,} \phi _ k(x) - \frac{C _ {k}^{(k-1)}\,}{C _ {k}^{(k+1)}\,} \phi _ {k-1}(x)\]But we might have $C _ {k}^{(k+1)} = 0$. But this is not the case, since if we consider
\[\langle x \phi _ k, \phi _ {k+1} \rangle = C _ {k}^{(k+1)} \langle \phi _ {k+1}, \phi _ {k+1} \rangle\]Hence $C _ {k}^{(k+1)} \ne 0$, since $x \phi _ k$ is of degree $k + 1$. Hence setting
\[\alpha _ k = \frac{1}{C _ {k}^{(k+1)}\,}\] \[\beta _ k = C _ {k}^{(k)}\] \[\gamma _ k = \frac{C _ {k}^{(k-1)}\\,}{C _ {k}^{(k+1)}\\,}\]Suppose $\{\phi _ 0, \phi _ 1, \cdots, \phi _ n, \cdots\}$ is a set of orthogonal polynomials. Can you state a result that gives you a recurrence for these?
There exists sequences of real numbers $(\alpha _ k)^\infty _ {k = 1}$, $(\beta _ k)^\infty _ {k = 1}$, $(\gamma _ k)^\infty _ {k = 1}$ such that a three-term recurrence relation holds of the form
\[\phi _ {k + 1}(x) = \alpha _ k(x - \beta _ k) \phi _ k(x) - \gamma _ k\phi _ {k-1}(x)\]for $k \ge 1$.
(as stated this makes it seem like the three sequences are not related, they are actually all derived from a single sequence where $\alpha _ k = \frac{1}{C _ {k}^{(k+1)}\,}, \beta _ k = C _ {k}^{(k)}, \gamma _ k = \frac{C _ {k}^{(k-1)}\,}{C _ {k}^{(k+1)}\,}$ and $C _ k^{(i)}$ is the $i$-th coefficient of expanding $x\phi _ {k}(x)$ in the orthonormal basis).
Suppose:
- $\langle f, g \rangle = \int^b _ a w(x) f(x) g(x) \text d x$
- $\{\phi _ 0, \cdots, \phi _ n, \cdots\}$ are corresponding orthogonal polynomials
Quickly prove that each $\phi _ k$ has $k$ distinct roots in the interval $(a, b)$.
The result is trivially true for $\phi _ 0$, since $\phi _ 0 = c _ 0 \ne 0$ for some $c _ 0$. Hence we can suppose that $k \ge 1$.
Note that
\[\langle \phi _ k, \phi _ 0\rangle = \int^b _ a w(x) \phi _ k(x) \phi _ 0(x) \text d x = 0\]implies that $\phi _ k$ changes sign (and so has a root) in $(a, b)$, since $w(x) > 0$ and $\phi _ 0$ is constant. Suppose that there are $\ell$ such points where $\phi _ k$ changes sign:
\[a < r _ 1< \cdots< r _ \ell < b\]Then consider
\[q(x) := (\pm 1 \text{ to make }\phi _ k(x)q(x) >0 \text{ on }(a, b)) \times \prod^\ell _ {j = 1} (x - r _ j)\]Hence
\[\langle \phi _ k, q \rangle = \int^b _ a w(x) \phi _ k(x) q(x) \text d x > 0\]This implies that degree $q$ is greater than $k$, since this inner product would be zero (consider the expansion of $q$ in the basis of orthogonal polynomials). But then we get
\[\ell = \deg q \ge k = \deg \phi _ k \ge \ell\](with $\deg \phi _ k \ge \ell$ following from the fact $\phi _ k$ can’t have more sign changes than it has roots). Hence $\ell = k$, so $\phi _ k$ has $k$ distinct roots in $(a, b)$.