I am reading Atkinson's "An Introduction to Numerical Analysis" and I am trying to understand how a certain equation was reached. It is called the "Triple Recursion Relation" for an orthogonal family of polynomials, from page 214.
My difficulty, which may or may not lead to the solution is: how do I calculate $(x\phi_n,\phi_n)$? The context is within $$ d_n = -a_n \frac{\int_a^b x \phi_n \phi_n w(x) \ \mathrm dx}{\int_a^b \phi_n \phi_n w(x) \ \mathrm dx}$$ (This is a different approach than the approach used in the link below).
Relevant information:
The relation is: $$ \phi_{n+1}(x) = (a_n x + b_n) \phi_n(x) – c_n \phi_{n-1}(x)$$ It is our goal to calculate the terms $b_n$ and $c_n$. I think $b_n = d_n$ and $c_n = d_{n-1}$, by comparing equations (4.4.21) and (4.4.24).
$\phi_n(x)$ are polynomials from an orthogonal family with weight function $w(x)$. The interval of interest is $(a,b)$. That means: $$ (\phi_i, \phi_j) = \int_a^b w(x) \phi_i(x) \phi_j(x) \ \mathrm dx = 0, \text{if } i \neq j$$
Also, $$ (\phi_i, \phi_j) \neq 0, \text{if } i = j$$
There is a representation of $\phi_n(x)$, given as: $\phi_n(x) = A_n x^n + B_n x^{n-1} + \ldots = A_n(x – x_{n,1})(x – x_{n,2}) \ldots (x-x_{n,n})$. Also, $$ a_n = \frac{A_{n+1}}{A_n}$$ It is also stated $\gamma_n = (\phi_n, \phi_n) \geq 0$.
The (solution) coefficients are given as $$ b_n = a_n \left[ \frac{B_{n+1}}{A_{n+1}} – \frac{B_n}{A_n} \right]$$ and $$ c_n = \frac{A_{n+1} A_{n-1}}{A_n^2} \cdot \frac{\gamma_n}{\gamma_{n-1}}$$
$G(x)$ is defined as: $$ G(x) = \phi_{n+1}(x) – a_n x \phi_n(x) = \left[ B_{n+1} – \frac{A_{n+1}B_n}{A_n} \right] x^n + \ldots = d_n \phi_n(x) + d_{n-1} \phi_{n-1}(x)$$
The equation for $d_i$ is also given: $$ d_i = \frac{1}{\gamma_i} \left[ (\phi_{n+1}, \phi_i) – a_n(x\phi_n, \phi_i)\right]$$
Note that I also found a external text which shows a proof of how the coefficients are reached. However, I do not understand one of the lines, and also I think the exact solution is a little bit different (it considers orthonormal vs. our orthogonal polynomials). The text is located here (page 64 on the page label). The exact equation there that I do not understand is: $$ x P_{n-1} = \frac{\alpha_{n-1}}{\alpha_n} P_n + q_{n-1}$$ Converting to our notation, the equation is $$ x \phi_{n-1}(x) = \frac{d_{n-1}}{d_n} \phi_n + G_{n-1}(x)$$
I am not sure what the precise meaning of $G_{n-1} (x)$ is.
I think all of the information I need is here, although I may be missing a "connection" step. Can someone give me a hint or some kind of "strategy" approach to solving this type of problem? I can provide more details if necessary.
Thanks.
Best Answer
I'm not entirely sure I'm reading your query correctly; I'll edit this if my interpretation's off the mark.
You're asking how the Stieltjes procedure for generating orthogonal polynomials with respect to some given weight $w(x)$ works. It's a bootstrapping procedure. You usually start with the first two known members, and slowly build up the other members through inner product computations and recursion.
Again, take
$$(f(x),g(x))=\int_a^b w(u)f(u)g(u) \,\mathrm du$$
and let $\phi_k(x)=A_k x^k+\cdots$ be the degree-$k$ polynomial that is orthogonal with respect to the weight function $w(x)$, i.e.
$$(\phi_k(x),\phi_\ell(x))=0,\quad k\neq \ell$$
Consider first
$$q(x)=\phi_{k+1}(x)-\frac{A_{k+1}}{A_k}x\phi_k(x)$$
which is a linear combination precisely designed to have a missing $x^{k+1}$ term.
This can be expanded as a series of orthogonal polynomials of degree $k$ and lower (abbreviating $\frac{A_{k+1}}{A_k}$ as $a_k$):
$$\phi_{k+1}(x)-a_k x\phi_k(x)=\mu_k\phi_k(x)+\mu_{k-1}\phi_{k-1}(x)+\cdots$$
where the $\mu_j$ are given by
$$\mu_j=\frac{(q(x),\phi_j(x))}{(\phi_j(x),\phi_j(x))}$$
Another fact we are going to need is
$$(\phi_k(x),x^\ell)=0,\quad \ell < k$$
We find from these considerations that the coefficients $\mu_j$ for $j < k-1$ vanish. Thus, after renaming $\mu_k$ to $b_k$ and $\mu_{k-1}$ to $c_k$, we have
$$\phi_{k+1}(x)-a_k x\phi_k(x)=b_k\phi_k(x)+c_k\phi_{k-1}(x)$$
At this point, it should be noted that one convenient normalization is to have the $\phi_k(x)$ be monic ($A_k=1$); this means we can set $a_k=1$ and consider the three-term recursion
$$\phi_{k+1}(x)=(x+b_k)\phi_k(x)+c_k\phi_{k-1}(x)$$
If we take inner products of both sides with $\phi_{k+1}(x)$, $\phi_k(x)$, and $\phi_{k-1}(x)$ in turns, we have the system
$$\begin{align*}(\phi_{k+1}(x),\phi_{k+1}(x))&=(\phi_{k+1}(x),x\phi_k(x))\\0&=(x\phi_k(x),\phi_k(x))+b_k(\phi_k(x),\phi_k(x))\\0&=(x\phi_k(x),\phi_{k-1}(x))+c_k(\phi_{k-1}(x),\phi_{k-1}(x))\end{align*}$$
where we've exploited linearity of the inner product and the orthogonality relation.
Solving for $b_k$ and $c_k$ in the last two equations, we have
$$\begin{align*}b_k&=-\frac{(x\phi_k(x),\phi_k(x))}{(\phi_k(x),\phi_k(x))}\\c_k&=-\frac{(x\phi_k(x),\phi_{k-1}(x))}{(\phi_{k-1}(x),\phi_{k-1}(x))}\end{align*}$$
$c_k$ can be expressed in a different way, using the fact that $(x\phi_k(x),\phi_{k-1}(x))=(\phi_k(x),x\phi_{k-1}(x))$ and shifting the index $k$ in the equation for $(\phi_{k+1}(x),\phi_{k+1}(x))$, yielding
$$c_k=-\frac{(\phi_k(x),\phi_k(x))}{(\phi_{k-1}(x),\phi_{k-1}(x))}$$
It's been all theoretical at this point; let me demonstrate the Stieltjes procedure with the monic Chebyshev polynomials (of the first kind) as a concrete example. The associated inner product is
$$(f(x),g(x))=\int_{-1}^1 \frac{f(u)g(u)}{\sqrt{1-u^2}}\mathrm du$$
The usual way of proceeding starts with $\phi_{-1}(x)=0$ and $\phi_0(x)=1$. To find $\phi_1(x)$, we compute
$$b_0=-\frac{(x,1)}{(1,1)}=0$$
and thus $\phi_1(x)=x$. To get $\phi_2(x)$, we compute
$$\begin{align*}b_1&=-\frac{(x\phi_1(x),\phi_1(x))}{(\phi_1(x),\phi_1(x))}=0\\c_1&=-\frac{(\phi_1(x),\phi_1(x))}{(\phi_0(x),\phi_0(x))}=-\frac12\end{align*}$$
and thus $\phi_2(x)=\left(x+b_1\right)\phi_1(x)+c_1\phi_0(x)=x^2-\frac12$. Clearly we can continue this bootstrapping, generating $\phi_3(x),\phi_4(x),\dots$ in turn by computing inner products and recursing. (As it turns out, for this example all the $b_k$ are zero.)