Chebyshev's Method: Recursive Algorithm & Polynomial Form

[MarkFL]

Chebyshev's method is a recursive algorithm for computing the $n$th multiple angle formula for the cosine function. If we define:

\(\displaystyle T_{n}\equiv \cos(n\theta)\)

then the algorithm is given as:

\(\displaystyle T_{n+1}=2xT_{n}-T_{n-1}\)

where:

\(\displaystyle x=\cos(\theta)\)

a) Using trigonometric identities (or otherwise), derive the recursive algorithm.

b) Find a closed polynomial form for $T_{n}$.

c) Compute \(\displaystyle \int_{-1}^1 T_n\,dx\)

d) Compute \(\displaystyle \int_{-1}^1 \frac{T_nT_m}{\sqrt{1-x^2}}\,dx\)

 

[polygamma]

a)

$ \displaystyle T_{n+1}(x) = T_{n+1}(\cos \theta) = \cos \Big((n+1) \theta \Big) = \cos (n \theta) \cos (\theta) - \sin(n \theta) \sin(\theta)$

$ \displaystyle T_{n-1}(x) = T_{n-1}(\cos \theta) = \cos \Big((n-1) \theta \Big) = \cos (n \theta) \cos (\theta) + \sin(n \theta) \sin(\theta) $So $ \displaystyle T_{n+1}(\cos \theta) + T_{n-1} \cos(\theta) = 2 \cos(n \theta) \cos (\theta) = 2 \cos \theta \ T_{n}(\cos \theta) $Or $ \displaystyle T_{n+1}(x) = 2x T_{n}(x) - T_{n-1}(x) $
b)

$ \displaystyle \int_{-1}^{1} T_{n}(x) \ dx $

Let $ x = \cos \theta $

$ \displaystyle = \int_{0}^{\pi} T_{n}(\cos \theta) \sin \theta \ d \theta = \int_{0}^{\pi} \cos(n \theta) \sin \theta \ d \theta = \frac{1}{2} \int_{0}^{\pi} \Big( \sin (n+1) \theta - \sin(n-1) \theta \Big) \ d \theta$

$ \displaystyle = - \frac{1}{2(n+1)} \Big( (-1)^{n+1}- 1 \Big) + \frac{1}{2(n-1)} \Big((-1)^{n-1} -1 \big) $If $n$ is odd, $ \displaystyle \int_{-1}^{1} T_{n}(x) \ dx = 0$

If $n$ is even $ \displaystyle \int_{-1}^{1} T_{n}(x) \ dx = \frac{1}{n+1} - \frac{1}{n-1} = -\frac{2}{n^{2}-1}$

 

[polygamma]

d)$ \displaystyle \int_{-1}^1 \frac{T_n(x)T_m(x)}{\sqrt{1-x^2}}\,dx $

Let $x = \cos \theta $

$ \displaystyle = \int_{0}^{\pi} T_n( \cos \theta)T_m(\cos \theta ) \ d \theta = \int_{0}^{\pi} \cos( n \theta) \cos( m \theta) \ d \theta = \frac{1}{2} \int_{0}^{\pi} \Big(\cos(n+m) \theta + \cos (n-m) \Big) \ d \theta $If $n \ne m$, $ \displaystyle \int_{-1}^1 \frac{T_n(x)T_m(x)}{\sqrt{1-x^2}}\,dx = \frac{1}{2(n+m)} \Big(\sin(n+m) \pi - 0 \Big) + \frac{1}{2(n-m)} \Big( \sin(n-m) \pi - 0 \Big) = 0 $If $n = m$, $ \displaystyle \int_{-1}^1 \frac{T^{2}_n(x)}{\sqrt{1-x^2}}\,dx = \frac{1}{4n} \Big(\sin(2n \pi) - 0 \Big) + \frac{\pi}{2} = \frac{\pi}{2} $

 

[polygamma]

I skipped (b) because I initially thought we were dealing with a recurrence relation with a variable coefficient. (Doh)$ \displaystyle T_{n+1} - 2xT_{n} - T_{n-1} = 0 $ has the associated characteristic polynomial $r^{2}-2xr - 1 = 0$

which has roots $ \displaystyle r = x \pm \sqrt{x^{2}-1} $.So the general solution is $T_{n} = c_{1} \Big(x + \sqrt{x^{2}-1} \Big)^{n} + c_{2} \Big(x - \sqrt{x^{2}-1} \Big)^{n} $.$ \displaystyle T_{0} = 1 = c_{1}+c_{2}$

$\displaystyle T_{1} = x = c_{1} \Big(x + \sqrt{x^{2}-1} \Big) + c_{2} \Big(x - \sqrt{x^{2}-1} \Big) $So just by inspection, $\displaystyle c_{1}=c_{2} = \frac{1}{2} $

And $ \displaystyle T_{n} = \frac{\Big(x + \sqrt{x^{2}-1} \Big)^{n} + \Big(x - \sqrt{x^{2}-1} \Big)^{n}}{2} $ which is evidently a polynomial in $x$ for all values of $n$

 

[MarkFL]

Bravo, Random Variable! (Clapping)

Thank you for taking the time to post such lucid explanations. (Yes)

Here are my solutions:

Spoiler

a) Using trigonometric identities (or otherwise), derive the recursive algorithm.

We may begin with the identity:

\(\displaystyle \cos((n+1)\theta)=\cos((n+1)\theta)\)

Add \(\displaystyle 0=\cos((n-1)\theta)-\cos((n-1)\theta)\) to the right side:

\(\displaystyle \cos((n+1)\theta)=\cos((n+1)\theta)+\cos((n-1)\theta)-\cos((n-1)\theta)\)

To the first two terms on the right, apply the following sum to product identity:

\(\displaystyle \cos(\alpha)+\cos(\beta)=2\cos\left(\frac{\alpha-\beta}{2} \right)\cos\left(\frac{\alpha+\beta}{2} \right)\)

and we have:

\(\displaystyle \cos((n+1)\theta)=2\cos(\theta)\cos(n\theta)-\cos((n-1)\theta)\)

And so we may write:

\(\displaystyle T_{n+1}=2xT_{n}-T_{n-1}\)

b) Find a closed polynomial form for $T_{n}$.

This is a homogeneous recurrence whose associated auxiliary equation is:

\(\displaystyle r^2-2xr+1=0\)

Application of the quadratic formula yields:

\(\displaystyle r=x\pm\sqrt{x^2-1}\)

Thus, the solution is of the form:

\(\displaystyle T_n(x)=c_1\left(x-\sqrt{x^2-1} \right)^n+c_2\left(x+\sqrt{x^2-1} \right)^n\)

Use initial conditions to determine constants:

\(\displaystyle T_0=c_1+c_2=1\)

\(\displaystyle T_1=c_1\left(x-\sqrt{x^2-1} \right)+c_2\left(x+\sqrt{x^2-1} \right)=x\)

Substituting from the first into the second:

\(\displaystyle c_1\left(x-\sqrt{x^2-1} \right)+\left(1-c_1 \right)\left(x+\sqrt{x^2-1} \right)=x\)

\(\displaystyle c_1x-c_1\sqrt{x^2-1}+x+\sqrt{x^2-1}-c_1x-c_1\sqrt{x^2-1}=x\)

\(\displaystyle -2c_1\sqrt{x^2-1}+\sqrt{x^2-1}=0\)

\(\displaystyle c_1=\frac{1}{2}\,\therefore\,c_2=\frac{1}{2}\)

Thus, the closed form for $T_n(x)$ is:

\(\displaystyle T_n(x)=\frac{1}{2}\left(\left(x-\sqrt{x^2-1} \right)^n+\left(x+\sqrt{x^2-1} \right)^n \right)\)

Using the binomial theorem, we may state:

\(\displaystyle T_n(x)=\frac{1}{2}\left(\sum_{k=0}^n\left({n \choose k}x^{n-k}\left(-\sqrt{x^2-1} \right)^k \right)+\sum_{k=0}^n\left({n \choose k}x^{n-k}\left(\sqrt{x^2-1} \right)^k \right) \right)\)

\(\displaystyle T_n(x)=\frac{1}{2}\left(\sum_{k=0}^n\left({n \choose k}x^{n-k}(-1)^k\left(\sqrt{x^2-1} \right)^k \right)+\sum_{k=0}^n\left({n \choose k}x^{n-k}\left(\sqrt{x^2-1} \right)^k \right) \right)\)

\(\displaystyle T_n(x)=\frac{1}{2}\sum_{k=0}^n\left(\left(1+(-1)^k \right){n \choose k}x^{n-k}\left(\sqrt{x^2-1} \right)^k \right)\)

\(\displaystyle T_n(x)=\sum_{k=0}^{\left\lfloor \frac{n}{2} \right\rfloor}\left({n \choose 2k}x^{n-2k}\left(x^2-1 \right)^k \right)\)

c) Compute \(\displaystyle \int_{-1}^1 T_n\,dx\)

From the recurrence relation, we may compute:

\(\displaystyle T_n(x)=\frac{1}{2}\left(\frac{1}{n+1}\cdot\frac{d}{dx}T_{n+1}(x)-\frac{1}{n-1}\cdot\frac{d}{dx}T_{n-1}(x) \right)\)

\(\displaystyle \int_{-1}^1 T_n(x)\,dx=\frac{1}{2}\left[\frac{T_{n+1}(x)}{n+1}-\frac{T_{n-1}(x)}{n-1} \right]_{-1}^1\)

From the definition, we see that $T_n(1)=1$ and $T_n(-1)=1\text{ n even or }-1\text{ n odd}$, thus:

For even $n$:

\(\displaystyle \int_{-1}^1 T_n(x)\,dx=\frac{1}{n+1}-\frac{1}{n-1}=\frac{2}{1-n^2}\)

For odd $n$:

\(\displaystyle \int_{-1}^1 T_n(x)\,dx=0\)

d) Compute \(\displaystyle \int_{-1}^1 \frac{T_nT_m}{\sqrt{1-x^2}}\,dx\)

\(\displaystyle Let x=\cos(\theta)\,\therefore\,dx=-\sin(\theta)\,d\theta\)

\(\displaystyle I=\int_{0}^{\pi} \cos(n\theta)\cos(m\theta)\,d\theta\)

For $n=m=0$:

\(\displaystyle I=\int_{0}^{\pi}\,d\theta=\pi\)

For $n=m\ne0$:

\(\displaystyle I=\int_{0}^{\pi} \cos^2(n\theta)\,d\theta\)

Let \(\displaystyle u=n\theta\,\therefore\,du=n\,d\theta\)

\(\displaystyle I=\frac{1}{n}\int_{0}^{n\pi} \cos^2(u)\,du=\frac{1}{2n}\int_{0}^{n\pi}\cos(2u)+1\,du=\)

\(\displaystyle \frac{1}{2n}\left[\frac{1}{2}\sin(2u)+u \right]_0^{n\pi}=\frac{1}{2n}\left(0+n\pi-0-0 \right)=\frac{\pi}{2}\)

For $n\ne m$:

\(\displaystyle I=\int_{0}^{\pi} \cos(n\theta)\cos(m\theta)\,d\theta=\)

\(\displaystyle \left[\frac{m\sin(m\theta)\cos(n\theta)-n\cos(m\theta)\sin(n\theta)}{m^2-n^2} \right]_{0}^{\pi}=\)

\(\displaystyle \frac{1}{m^n-n^2}(0-0-0+0)=0\)