TeachingSpecial Functions – Orthogonal polynomials – General theory
Three-term recurrence relation
Theorem: A sequence of orthogonal polynomials \(\{p_n(x)\}_{n=0}^{\infty}\) satisfies
\[p_{n+1}(x)=(A_nx+B_n)p_n(x)+C_np_{n-1}(x),\quad n=1,2,3,\ldots,\]where
\[A_n=\frac{k_{n+1}}{k_n},\quad n=0,1,2,\ldots\quad\text{and}\quad C_n=-\frac{A_n}{A_{n-1}}\cdot\frac{h_n}{h_{n-1}},\quad n=1,2,3,\ldots.\]Proof: Since \(\text{degree}\left[p_n(x)\right]=n\) for each \(n\in\{0,1,2,\ldots\}\) the sequence of orthogonal polynomials \(\left\{p_n(x)\right\}_{n=0}^{\infty}\) is linearly independent. Let \(A_n=k_{n+1}/k_n\). Then \(p_{n+1}(x)-A_nxp_n(x)\) is a polynomial of degree \(\leq n\). Hence
\[p_{n+1}(x)-A_nxp_n(x)=\sum_{k=0}^nc_kp_k(x).\]The orthogonality property now gives
\[\langle p_{n+1}(x)-A_nxp_n(x),\,p_k(x)\rangle =\sum_{m=0}^nc_m\langle p_m(x),\,p_k(x)\rangle=c_k\langle p_k(x),\,p_k(x)\rangle=c_k\,h_k.\]This implies
\[h_k\,c_k=\langle p_{n+1}(x)-A_nxp_n(x),\,p_k(x)\rangle=\langle p_{n+1}(x),\,p_k(x)\rangle-A_n\langle xp_n(x),\,p_k(x)\rangle =-A_n\langle p_n(x),\,xp_k(x)\rangle.\]For \(k < n-1\) we have \(\text{degree}\left[xp_k(x)\right] < n\) which implies that \(\langle p_n(x),\,xp_k(x)\rangle=0\). Hence: \(c_k=0\) for \(k < n-1\). This proves that the polynomials satisfy the three-term recurrence relation
\[p_{n+1}(x)-A_nxp_n(x)=c_np_n(x)+c_{n-1}p_{n-1}(x),\quad n=1,2,3,\ldots.\]Further we have
\[h_{n-1}\,c_{n-1}=-A_n\langle p_n(x),\,xp_{n-1}(x)\rangle=-A_n\,\frac{k_{n-1}}{k_n}\,h_n \quad\Longrightarrow\quad c_{n-1}=-\frac{A_n}{A_{n-1}}\cdot\frac{h_n}{h_{n-1}}.\]This proves the theorem.
Note that the three-term recurrence relation for a sequence of monic (\(k_n=1\)) orthogonal polynomials \(\{p_n(x)\}_{n=0}^{\infty}\) has the form
\[p_{n+1}(x)=xp_n(x)+B_np_n(x)+C_np_{n-1}(x)\quad\text{with}\quad C_n=-\frac{h_n}{h_{n-1}},\quad n=1,2,3,\ldots.\]Christoffel-Darboux formula
Theorem: A sequence of orthogonal polynomials \(\left\{p_n(x)\right\}_{n=0}^{\infty}\) satisfies
\[\sum_{k=0}^n\frac{p_k(x)p_k(y)}{h_k}=\frac{k_n}{h_n\,k_{n+1}}\cdot \frac{p_{n+1}(x)p_n(y)-p_{n+1}(y)p_n(x)}{x-y},\quad n=0,1,2,\ldots\]and
\[\sum_{k=0}^n\frac{\left\{p_k(x)\right\}^2}{h_k}=\frac{k_n}{h_n\,k_{n+1}}\cdot \left(p_{n+1}'(x)p_n(x)-p_{n+1}(x)p_n'(x)\right),\quad n=0,1,2,\ldots.\]The first formula is called the Christoffel-Darboux formula and the second one its confluent form.
Proof: The three-term recurrence relation implies that
\[p_{n+1}(x)p_n(y)=(A_nx+B_n)p_n(x)p_n(y)+C_np_{n-1}(x)p_n(y)\]and
\[p_{n+1}(y)p_n(x)=(A_ny+B_n)p_n(y)p_n(x)+C_np_{n-1}(y)p_n(x).\]Subtraction gives
\[p_{n+1}(x)p_n(y)-p_{n+1}(y)p_n(x)=A_n(x-y)p_n(x)p_n(y)+C_n\left[p_{n-1}(x)p_n(y)-p_{n-1}(y)p_n(x)\right].\]This leads to the telescoping sum
\begin{align*} (x-y)\sum_{k=1}^n\frac{p_k(x)p_k(y)}{h_k}&=\sum_{k=1}^n\frac{p_{k+1}(x)p_k(y)-p_{k+1}(y)p_k(x)}{A_k\,h_k} -\sum_{k=1}^n\frac{p_k(x)p_{k-1}(y)-p_k(y)p_{k-1}(x)}{A_{k-1}\,h_{k-1}}\\[2.5mm] &=\frac{p_{n+1}(x)p_n(y)-p_{n+1}(y)p_n(x)}{A_n\,h_n}-\frac{k_0^2(x-y)}{h_0}. \end{align*}This implies that
\[(x-y)\sum_{k=0}^n\frac{p_k(x)p_k(y)}{h_k}=\frac{p_{n+1}(x)p_n(y)-p_{n+1}(y)p_n(x)}{A_n\,h_n} =\frac{k_n}{h_n\,k_{n+1}}\left(p_{n+1}(x)p_n(y)-p_{n+1}(y)p_n(x)\right),\]which proves the Christoffel-Darboux formula. The confluent form then follows by taking the limit \(y\rightarrow x\):
\begin{align*} \lim\limits_{y\rightarrow x}\frac{p_{n+1}(x)p_n(y)-p_{n+1}(y)p_n(x)}{x-y}&=\lim\limits_{y\rightarrow x} \frac{p_n(x)\left(p_{n+1}(x)-p_{n+1}(y)\right)-p_{n+1}(x)\left(p_n(x)-p_n(y)\right)}{x-y}\\[2.5mm] &=p_n(x)p_{n+1}'(x)-p_{n+1}(x)p_n'(x). \end{align*}Zeros
Theorem: If \(\{p_n(x)\}_{n=0}^{\infty}\) is a sequence of orthogonal polynomials on the interval \((a,b)\) with respect to the weight function \(w(x)\), then the polynomial \(p_n(x)\) has exactly \(n\) real simple zeros in the interval \((a,b)\).
Proof: Since \(\text{degree}[p_n(x)]=n\) the polynomial has at most \(n\) real zeros. Suppose that \(p_n(x)\) has \(m\leq n\) distinct real zeros \(x_1,x_2,\ldots,x_m\) in \((a,b)\) of odd multiplicity. Then the polynomial
\[p_n(x)(x-x_1)(x-x_2)\cdots(x-x_m)\]does not change sign on the interval \((a,b)\). This implies that
\[\int_a^bw(x)p_n(x)(x-x_1)(x-x_2)\cdots(x-x_m)\,dx\neq 0.\]By orthogonality this integral equals zero if \(m < n\). Hence: \(m=n\), which implies that \(p_n(x)\) has \(n\) distinct real zeros of odd multiplicity in \((a,b)\). This proves that all \(n\) zeros are distinct and simple (have multiplicity equal to one).
Theorem: If \(\{p_n(x)\}_{n=0}^{\infty}\) is a sequence of orthogonal polynomials on the interval \((a,b)\) with respect to the weight function \(w(x)\), then the zeros of \(p_n(x)\) and \(p_{n+1}(x)\) separate each other.
Proof: This follows from the confluent form of the Christoffel-Darboux formula. Note that
\[h_n=\int_a^bw(x)\left\{p_n(x)\right\}^2\,dx>0,\quad n=0,1,2,\ldots.\]This implies that
\[\frac{k_n}{h_n\,k_{n+1}}\cdot\left(p_{n+1}'(x)p_n(x)-p_{n+1}(x)p_n'(x)\right)=\sum_{k=0}^n\frac{\left\{p_k(x)\right\}^2}{h_k}>0.\]Hence
\[\frac{k_n}{k_{n+1}}\cdot\left(p_{n+1}'(x)p_n(x)-p_{n+1}(x)p_n'(x)\right)>0.\]Now suppose that \(x_{n,k}\) and \(x_{n,k+1}\) are two consecutive zeros of \(p_n(x)\) with \(x_{n,k} < x_{n,k+1}\). Since all \(n\) zeros of \(p_n(x)\) are real and simple \(p_n'(x_{n,k})\) and \(p_n'(x_{n,k+1})\) should have opposite signs. Hence we have
\[p_n(x_{n,k})=0=p_n(x_{n,k+1})\quad\text{and}\quad p_n'(x_{n,k})\cdot p_n'(x_{n,k+1})<0.\]This implies that \(p_{n+1}(x_{n,k})\cdot p_{n+1}(x_{n,k+1})\) should be negative too. Then the continuity of \(p_{n+1}(x)\) implies that there should be at least one zero of \(p_{n+1}(x)\) between \(x_{n,k}\) and \(x_{n,k+1}\). However, this holds for each two consecutive zeros of \(p_n(x)\). This proves the theorem.
Moreover, if \(\{x_{n,k}\}_{k=1}^n\) and \(\{x_{n+1,k}\}_{k=1}^{n+1}\) denote the consecutive zeros of \(p_n(x)\) and \(p_{n+1}(x)\) respectively, then we have
\[a < x_{n+1,1} < x_{n,1} < x_{n+1,2} < x_{n,2} < \cdots < x_{n+1,n} < x_{n,n} < x_{n+1,n+1} < b.\]Gauss quadrature
If \(f\) is a continuous function on \((a,b)\) and \(x_1 < x_2 < \cdots < x_n\) are \(n\) distinct points in \((a,b)\), then there exists exactly one polynomial \(P\) with degree \(\leq n-1\) such that \(P(x_i)=f(x_i)\) for all \(i=1,2,\ldots,n\). This polynomial \(P\) can easily be found by using Lagrange interpolation as follows. Define
\[p(x)=(x-x_1)(x-x_2)\cdots(x-x_n)\]and consider
\[P(x)=\sum_{i=1}^nf(x_i)\frac{p(x)}{(x-x_i)p'(x_i)} =\sum_{i=1}^nf(x_i)\frac{(x-x_1)\cdots(x-x_{i-1})(x-x_{i+1})\cdots(x-x_n)}{(x_i-x_1)\cdots(x_i-x_{i-1})(x_i-x_{i+1})\cdots(x_i-x_n)}.\]Let \(\{p_n(x)\}_{n=0}^{\infty}\) be a sequence of orthogonal polynomials on the interval \((a,b)\) with respect to the weight function
\(w(x)\). Then for \(x_1 < x_2 < \cdots < x_n\) we take the \(n\) distinct real zeros of the polynomial \(p_n(x)\). If \(f\) is a polynomial of degree
\(\leq 2n-1\), then \(f(x)-P(x)\) is a polynomial of degree \(\leq 2n-1\) with at least the zeros \(x_1 where \(r(x)\) is a polynomial of degree \(\leq n-1\). This can also be written as This implies that Since \(\text{degree}[r(x)]\leq n-1\) the orthogonality property implies that the latter integral equals zero. This implies that This is the Gauss quadrature formula. This gives the value of the integral in the case that \(f\) is a polynomial of degree
\(\leq 2n-1\) if the value of \(f(x_i)\) is known for the \(n\) zeros \(x_1 < x_2 < \cdots < x_n\) of the polynomial \(p_n(x)\). If \(f\) is not a polynomial of degree \(\leq 2n-1\) this leads to an approximation of the integral: The coefficients \(\{\lambda_{n,i}\}_{i=1}^n\) are called Christoffel numbers. Note that these numbers do not depend on the
function \(f\). These Christoffel numbers are all positive. This can be shown as follows. We have Then \(\ell_{n,i}^2(x)-\ell_{n,i}(x)\) is a polynomial of degree \(\leq 2n-2\) which vanishes at the zeros \(\{x_{n,k}\}_{k=1}^n\) of
\(p_n(x)\). Hence This implies that by orthogonality. Hence we have Now we can also prove Theorem: Let \(\{p_n(x)\}_{n=0}^{\infty}\) be a sequence of orthogonal polynomials on the interval \((a,b)\) with respect to the
weight function \(w(x)\) and let \(m < n\). Then we have: between any two zeros of \(p_m(x)\) there is at least one zero of \(p_n(x)\). Proof: Suppose that \(x_{m,k}\) and \(x_{m,k+1}\) are two consecutive zeros of \(p_m(x)\) and that there is no zero of
\(p_n(x)\) in \((x_{m,k},x_{m,k+1})\). Then consider the polynomial Then we have Now the Gauss quadrature formula gives where \(\{x_{n,i}\}_{i=1}^n\) are the zeros of \(p_n(x)\). Since there are no zeros of \(p_n(x)\) in \((x_{m,k},x_{m,k+1})\) we conclude
that \(g(x_{n,i})p_m(x_{n,i})\geq 0\) for all \(i=1,2,\ldots,n\). Further we have \(\lambda_{n,i}>0\) for all \(i=1,2,\ldots,n\) which implies that
the sum at the right-hand side cannot vanish. However, the integral at the left-hand side is zero by orthogonality. This contradiction proves that
there should be at least one zero of \(p_n(x)\) between the two consecutive zeros of \(p_m(x)\).
Last modified on May 22, 2021
