Notes - 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)$.