MHB Chebyshev's Method: Recursive Algorithm & Polynomial Form

  • Thread starter Thread starter MarkFL
  • Start date Start date
  • Tags Tags
    Method
AI Thread Summary
Chebyshev's method is a recursive algorithm for calculating the $n$th multiple angle formula for the cosine function, defined as $T_n \equiv \cos(n\theta)$, with the recursion $T_{n+1} = 2xT_n - T_{n-1}$ where $x = \cos(\theta)$. The closed polynomial form for $T_n$ is derived using the characteristic polynomial method, yielding $T_n = \frac{(x + \sqrt{x^2 - 1})^n + (x - \sqrt{x^2 - 1})^n}{2}$. The integral $\int_{-1}^1 T_n \, dx$ evaluates to zero for odd $n$ and to $-\frac{2}{n^2 - 1}$ for even $n$. Additionally, the integral $\int_{-1}^1 \frac{T_n T_m}{\sqrt{1-x^2}} \, dx$ is zero for $n \neq m$ and equals $\frac{\pi}{2}$ for $n = m$.
MarkFL
Gold Member
MHB
Messages
13,284
Reaction score
12
Chebyshev's method is a recursive algorithm for computing the $n$th multiple angle formula for the cosine function. If we define:

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

then the algorithm is given as:

$$T_{n+1}=2xT_{n}-T_{n-1}$$

where:

$$x=\cos(\theta)$$

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

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

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

d) Compute $$\int_{-1}^1 \frac{T_nT_m}{\sqrt{1-x^2}}\,dx$$
 
Mathematics news on Phys.org
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}$
 
Last edited:
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} $
 
Last edited:
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$
 
Last edited:
Bravo, Random Variable! (Clapping)

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

Here are my solutions:

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

We may begin with the identity:

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

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

$$\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:

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

and we have:

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

And so we may write:

$$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:

$$r^2-2xr+1=0$$

Application of the quadratic formula yields:

$$r=x\pm\sqrt{x^2-1}$$

Thus, the solution is of the form:

$$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:

$$T_0=c_1+c_2=1$$

$$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:

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

$$c_1x-c_1\sqrt{x^2-1}+x+\sqrt{x^2-1}-c_1x-c_1\sqrt{x^2-1}=x$$

$$-2c_1\sqrt{x^2-1}+\sqrt{x^2-1}=0$$

$$c_1=\frac{1}{2}\,\therefore\,c_2=\frac{1}{2}$$

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

$$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:

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

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

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

$$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 $$\int_{-1}^1 T_n\,dx$$

From the recurrence relation, we may compute:

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

$$\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$:

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

For odd $n$:

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

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

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

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

For $n=m=0$:

$$I=\int_{0}^{\pi}\,d\theta=\pi$$

For $n=m\ne0$:

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

Let $$u=n\theta\,\therefore\,du=n\,d\theta$$

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

$$\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$:

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

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

$$\frac{1}{m^n-n^2}(0-0-0+0)=0$$
 
Thread 'Video on imaginary numbers and some queries'
Hi, I was watching the following video. I found some points confusing. Could you please help me to understand the gaps? Thanks, in advance! Question 1: Around 4:22, the video says the following. So for those mathematicians, negative numbers didn't exist. You could subtract, that is find the difference between two positive quantities, but you couldn't have a negative answer or negative coefficients. Mathematicians were so averse to negative numbers that there was no single quadratic...
Insights auto threads is broken atm, so I'm manually creating these for new Insight articles. In Dirac’s Principles of Quantum Mechanics published in 1930 he introduced a “convenient notation” he referred to as a “delta function” which he treated as a continuum analog to the discrete Kronecker delta. The Kronecker delta is simply the indexed components of the identity operator in matrix algebra Source: https://www.physicsforums.com/insights/what-exactly-is-diracs-delta-function/ by...
Thread 'Unit Circle Double Angle Derivations'
Here I made a terrible mistake of assuming this to be an equilateral triangle and set 2sinx=1 => x=pi/6. Although this did derive the double angle formulas it also led into a terrible mess trying to find all the combinations of sides. I must have been tired and just assumed 6x=180 and 2sinx=1. By that time, I was so mindset that I nearly scolded a person for even saying 90-x. I wonder if this is a case of biased observation that seeks to dis credit me like Jesus of Nazareth since in reality...

Similar threads

Back
Top