Module

for

Chebyshev Polynomials

   

Background for the Chebyshev approximation polynomial.  

    We now turn our attention to polynomial interpolation for  f(x)  over  [-1,1]  based on the
nodes  [Graphics:Images/ChebyshevPolyMod_gr_1.gif].  Both the Lagrange and Newton polynomials satisfy  

        
[Graphics:Images/ChebyshevPolyMod_gr_2.gif],  

where the remainder term  [Graphics:Images/ChebyshevPolyMod_gr_3.gif]  has the form

        
[Graphics:Images/ChebyshevPolyMod_gr_4.gif].  

and  [Graphics:Images/ChebyshevPolyMod_gr_5.gif]  is the polynomial of degree  [Graphics:Images/ChebyshevPolyMod_gr_6.gif]  given by    

        
[Graphics:Images/ChebyshevPolyMod_gr_7.gif]

Using the relationship

            
[Graphics:Images/ChebyshevPolyMod_gr_8.gif] [Graphics:Images/ChebyshevPolyMod_gr_9.gif][Graphics:Images/ChebyshevPolyMod_gr_10.gif]

our task is to determine how to select the set of nodes  [Graphics:Images/ChebyshevPolyMod_gr_11.gif]  that minimizes  [Graphics:Images/ChebyshevPolyMod_gr_12.gif].  Research investigating the minimum error in polynomial interpolation is attributed to the Russian mathematician Pafnuty Lvovich Chebyshev (1821-1894).

 

Table of Chebyshev Polynomials.  
        

[Graphics:Images/ChebyshevPolyMod_gr_13.gif]

=

[Graphics:Images/ChebyshevPolyMod_gr_14.gif]

[Graphics:Images/ChebyshevPolyMod_gr_15.gif]

=

[Graphics:Images/ChebyshevPolyMod_gr_16.gif]

[Graphics:Images/ChebyshevPolyMod_gr_17.gif]

=

[Graphics:Images/ChebyshevPolyMod_gr_18.gif]

[Graphics:Images/ChebyshevPolyMod_gr_19.gif]

=

[Graphics:Images/ChebyshevPolyMod_gr_20.gif]

[Graphics:Images/ChebyshevPolyMod_gr_21.gif]

=

[Graphics:Images/ChebyshevPolyMod_gr_22.gif]

[Graphics:Images/ChebyshevPolyMod_gr_23.gif]

=

[Graphics:Images/ChebyshevPolyMod_gr_24.gif]

[Graphics:Images/ChebyshevPolyMod_gr_25.gif]

=

[Graphics:Images/ChebyshevPolyMod_gr_26.gif]

[Graphics:Images/ChebyshevPolyMod_gr_27.gif]

=

[Graphics:Images/ChebyshevPolyMod_gr_28.gif]

[Graphics:Images/ChebyshevPolyMod_gr_29.gif]

  

[Graphics:Images/ChebyshevPolyMod_gr_30.gif]

  

 

Recursive Relationship.  

     The Chebyshev polynomials can be generated recursively in the following way.  First, set

        [Graphics:Images/ChebyshevPolyMod_gr_31.gif]  

  and use the recurrence relation

        [Graphics:Images/ChebyshevPolyMod_gr_32.gif].  

Exploration 1.

 

 

Relation to trigonometric functions.

    The signal property of Chebyshev polynomials is the trigonometric representation on [-1,1].

Consider the following expansion using the Mathematica command "FunctionExpand."

[Graphics:Images/ChebyshevPolyMod_gr_51.gif]

[Graphics:Images/ChebyshevPolyMod_gr_52.gif]

[Graphics:Images/ChebyshevPolyMod_gr_53.gif]

Exploration 2.

 

 

    These celebrated Chebyshev polynomials are readily available in Mathematica and called under the reserved name "ChebyshevT[n,x]."  

[Graphics:Images/ChebyshevPolyMod_gr_82.gif]


[Graphics:Images/ChebyshevPolyMod_gr_83.gif]

[Graphics:Images/ChebyshevPolyMod_gr_84.gif]

[Graphics:Images/ChebyshevPolyMod_gr_85.gif]

[Graphics:Images/ChebyshevPolyMod_gr_86.gif]

[Graphics:Images/ChebyshevPolyMod_gr_87.gif]

[Graphics:Images/ChebyshevPolyMod_gr_88.gif]


Roots of the Chebyshev polynomials

    The roots of  [Graphics:Images/ChebyshevPolyMod_gr_89.gif]  are  [Graphics:Images/ChebyshevPolyMod_gr_90.gif].  These will be the nodes for polynomial approximation of degree n.  

Exploration 3.

 

 

The Minimax Problem

    An upper bound for the absolute value of the remainder term, [Graphics:Images/ChebyshevPolyMod_gr_104.gif],  is the product of  [Graphics:Images/ChebyshevPolyMod_gr_105.gif]  and   [Graphics:Images/ChebyshevPolyMod_gr_106.gif].  To minimize the factor  [Graphics:Images/ChebyshevPolyMod_gr_107.gif],  Chebyshev discovered that  [Graphics:Images/ChebyshevPolyMod_gr_108.gif]  must be chosen so that  [Graphics:Images/ChebyshevPolyMod_gr_109.gif], which is stated in the following result.   

 

Theorem  (Minimax Property).   Assume that  n  is fixed.  Among all possible choices for  Q(x)  and thus among all possible choices for the distinct nodes  [Graphics:Images/ChebyshevPolyMod_gr_110.gif]  in  [-1,1],  

the polynomial  
[Graphics:Images/ChebyshevPolyMod_gr_111.gif]  is the unique choice which has the property

            
[Graphics:Images/ChebyshevPolyMod_gr_112.gif]

Moreover,

            
[Graphics:Images/ChebyshevPolyMod_gr_113.gif].  

Proof  Chebyshev Polynomials  Chebyshev Polynomials  

Exploration for the theorem.  Construct Q(x) of degree n using the n+1 Chebyshev nodes and compare it to [Graphics:Images/ChebyshevPolyMod_gr_114.gif].
Exploration 4.

 

 

Rule of Thumb.

    The "best a priori choice" of interpolation nodes for the interval [-1,1] are the n+1 nodes that are zeros of the Chebyshev polynomial  [Graphics:Images/ChebyshevPolyMod_gr_146.gif].  

Here is a visual analysis of equally spaced nodes verses Chebyshev nodes on [-1,1], and their affect on the magnitude of Q(x) in the remainder term  [Graphics:Images/ChebyshevPolyMod_gr_147.gif].  
Exploration 5.

 

 

Transforming the Interval for Interpolation

    Sometimes it is necessary to take a problem stated on an interval  [a,b]  and reformulate the problem on the interval  [c,d]  where the solution is known.  If the approximation  [Graphics:Images/ChebyshevPolyMod_gr_170.gif]  to  [Graphics:Images/ChebyshevPolyMod_gr_171.gif]  is to be obtained on the interval  [a,b],  then we change the variable so that the problem is reformulated on  [-1,1]:

    [Graphics:Images/ChebyshevPolyMod_gr_172.gif]  or  [Graphics:Images/ChebyshevPolyMod_gr_173.gif],

where  [Graphics:Images/ChebyshevPolyMod_gr_174.gif].  The required Chebyshev nodes of  [Graphics:Images/ChebyshevPolyMod_gr_175.gif]  on  [-1,1]  are

    [Graphics:Images/ChebyshevPolyMod_gr_176.gif],  

and the interpolating nodes  [Graphics:Images/ChebyshevPolyMod_gr_177.gif]  on  [a,b]  are obtained using the change of variable  [Graphics:Images/ChebyshevPolyMod_gr_178.gif]  for  [Graphics:Images/ChebyshevPolyMod_gr_179.gif].  

 

Theorem (Lagrange-Chebyshev Approximation).  Assume that  [Graphics:Images/ChebyshevPolyMod_gr_180.gif]  is the Lagrange polynomial that is based on the Chebyshev interpolating nodes  [Graphics:Images/ChebyshevPolyMod_gr_181.gif]  on  [a,b]  mentioned above.  

If  
[Graphics:Images/ChebyshevPolyMod_gr_182.gif]  then

        
[Graphics:Images/ChebyshevPolyMod_gr_183.gif]  

holds for all
  [Graphics:Images/ChebyshevPolyMod_gr_184.gif].   

Proof  Chebyshev Polynomials  Chebyshev Polynomials  

 

Algorithm (Lagrange-Chebyshev Approximation).  The Chebyshev approximation polynomial  [Graphics:Images/ChebyshevPolyMod_gr_185.gif]  of  degree  [Graphics:Images/ChebyshevPolyMod_gr_186.gif]  for  f(x)  over  [-1,1]  can be written as a sum of  [Graphics:Images/ChebyshevPolyMod_gr_187.gif]:  

    [Graphics:Images/ChebyshevPolyMod_gr_188.gif].  

The coefficients  [Graphics:Images/ChebyshevPolyMod_gr_189.gif]  are computed with the formulas  

    
[Graphics:Images/ChebyshevPolyMod_gr_190.gif][Graphics:Images/ChebyshevPolyMod_gr_191.gif],  
and  

    [Graphics:Images/ChebyshevPolyMod_gr_192.gif][Graphics:Images/ChebyshevPolyMod_gr_193.gif],  

for  [Graphics:Images/ChebyshevPolyMod_gr_194.gif]  where  [Graphics:Images/ChebyshevPolyMod_gr_195.gif] for  [Graphics:Images/ChebyshevPolyMod_gr_196.gif].  

 

Animations (Chebyshev Polynomials  Chebyshev Polynomials).  Internet hyperlinks to animations.

 

Computer Programs  Chebyshev Polynomials  Chebyshev Polynomials  

 

Mathematica Subroutine (Chebyshev Polynomial Approximation).  
The first subroutine "Chebyshev" uses recursion to construct the Chebyshev Approximation Polynomial.  

     [Graphics:Images/ChebyshevPolyMod_gr_197.gif]

    The following subroutine "ChebyshevPoly" version uses Mathematica's built-in functions to construct the Chebyshev approximation polynomial.  
In the construction, vector operations are used to assist the computations, since, similar terms occur in the summation for each of the coefficients.
Both give the same results.

 

Mathematica Subroutine (Chebyshev Approximation).  
    The following subroutine "ChebyshevPoly" version uses Mathematica's built-in functions to construct the Chebyshev approximation polynomial.  
In the construction, vector operations are used to assist the computations, since, similar terms occur in the summation for each of the coefficients.
Both give the same results.

     [Graphics:Images/ChebyshevPolyMod_gr_198.gif]

First, generate some Chebyshev polynomials with Mathematica's built in function.

[Graphics:Images/ChebyshevPolyMod_gr_199.gif]

[Graphics:Images/ChebyshevPolyMod_gr_200.gif]

[Graphics:Images/ChebyshevPolyMod_gr_201.gif]

[Graphics:Images/ChebyshevPolyMod_gr_202.gif]

Example 1.   Form several Chebyshev polynomials of degree  n = 1,2, 3, 4, and 5  for the function  [Graphics:Images/ChebyshevPolyMod_gr_203.gif]  over the interval  [Graphics:Images/ChebyshevPolyMod_gr_204.gif]  using Chebyshev's nodes.
Solution 1.

 

Example 2.  Error Analysis.  Investigate the error for the Chebyshev polynomial approximations in Example 1.
Solution 2.

 

Example 3.   Form several Chebyshev polynomials of degree  n = 1,2, 3, 4, and 5  for the function  [Graphics:Images/ChebyshevPolyMod_gr_315.gif]  over the interval  [Graphics:Images/ChebyshevPolyMod_gr_316.gif]  using Chebyshev's abscissas.
Solution 3.

 

Example 4.  Error Analysis.  Investigate the error for the Chebyshev polynomial approximations in Example 3.
Solution 4.

 

Example 5.  What is the maximum over the interval  [0, 1]  for each of the quantities, where  [Graphics:Images/ChebyshevPolyMod_gr_442.gif]  is the Chebyshev polynomial.
5 (a).  Find  [Graphics:Images/ChebyshevPolyMod_gr_443.gif].  
5 (b).  Find  [Graphics:Images/ChebyshevPolyMod_gr_444.gif].  
5 (c).  Find  [Graphics:Images/ChebyshevPolyMod_gr_445.gif].  
5 (d).  Find  [Graphics:Images/ChebyshevPolyMod_gr_446.gif].  
5 (e).  Find  [Graphics:Images/ChebyshevPolyMod_gr_447.gif].  
5 (f).  Compare the result with the error bounds for the Lagrange polynomial based on equally spaced points.
Solution 5.

 

Various Scenarios and Animations for Chebyshev Polynomials.

     [Graphics:Images/ChebyshevPolyMod_gr_455.gif]

Example 6.  Find the Chebyshev polynomial approximation for  [Graphics:Images/ChebyshevPolyMod_gr_456.gif], on the interval [Graphics:Images/ChebyshevPolyMod_gr_457.gif], [Graphics:Images/ChebyshevPolyMod_gr_458.gif], and [Graphics:Images/ChebyshevPolyMod_gr_459.gif].  
Solution 6 (a).
Solution 6 (b).
Solution 6 (c).

 

Example 7.  Find the Chebyshev polynomial approximation for  [Graphics:Images/ChebyshevPolyMod_gr_499.gif], on the interval [Graphics:Images/ChebyshevPolyMod_gr_500.gif].  
Solution 7.

 

Example 8.  Find the Chebyshev polynomial approximation for  [Graphics:Images/ChebyshevPolyMod_gr_514.gif], on the interval [Graphics:Images/ChebyshevPolyMod_gr_515.gif].  
Solution 8.

 

Example 9.  Find the Chebyshev polynomial approximation for  [Graphics:Images/ChebyshevPolyMod_gr_529.gif], on the interval [Graphics:Images/ChebyshevPolyMod_gr_530.gif], and [Graphics:Images/ChebyshevPolyMod_gr_531.gif].  
Solution 9 (a).
Solution 9 (b).

 

Example 10.  Find the Chebyshev polynomial approximation for  [Graphics:Images/ChebyshevPolyMod_gr_558.gif], on the interval [Graphics:Images/ChebyshevPolyMod_gr_559.gif].  
Solution 10.

 

Example 11.  Find the Chebyshev polynomial approximation for  [Graphics:Images/ChebyshevPolyMod_gr_576.gif], on the interval [Graphics:Images/ChebyshevPolyMod_gr_577.gif].  
Solution 11.

 

Example 12.  Find the Chebyshev polynomial approximation for  [Graphics:Images/ChebyshevPolyMod_gr_591.gif], on the interval [Graphics:Images/ChebyshevPolyMod_gr_592.gif].  
Solution 12.

 

Example 13.  Find the Chebyshev polynomial approximation for  [Graphics:Images/ChebyshevPolyMod_gr_606.gif], on the interval [Graphics:Images/ChebyshevPolyMod_gr_607.gif].  
Solution 13.

 

Example 14.  Find the Chebyshev polynomial approximation for  [Graphics:Images/ChebyshevPolyMod_gr_624.gif], on the interval [Graphics:Images/ChebyshevPolyMod_gr_625.gif].  
Solution 14.

 

Example 15.  Find the Chebyshev polynomial approximation for  [Graphics:Images/ChebyshevPolyMod_gr_639.gif], on the interval [Graphics:Images/ChebyshevPolyMod_gr_640.gif].  
Solution 15.

 

Example 16.  Find the Chebyshev polynomial approximation for  [Graphics:Images/ChebyshevPolyMod_gr_654.gif], on the interval [Graphics:Images/ChebyshevPolyMod_gr_655.gif].  
Solution 16.

 

Example 17.  Find the Chebyshev polynomial approximation for  [Graphics:Images/ChebyshevPolyMod_gr_669.gif], on the interval [Graphics:Images/ChebyshevPolyMod_gr_670.gif].  
Solution 17.

 

Example 18.  Find the Chebyshev polynomial approximation for  [Graphics:Images/ChebyshevPolyMod_gr_684.gif], on the interval [Graphics:Images/ChebyshevPolyMod_gr_685.gif].  
Solution 18.

 

Animations (Chebyshev Polynomials  Chebyshev Polynomials).  Internet hyperlinks to animations.

 

Old Lab Project (Chebyshev Polynomials  Chebyshev Polynomials).  Internet hyperlinks to an old lab project.  

 

Research Experience for Undergraduates

Chebyshev Polynomials  Chebyshev Polynomials  Internet hyperlinks to web sites and a bibliography of articles.  

 

Download this Mathematica Notebook Chebyshev Polynomials

 

Return to Numerical Methods - Numerical Analysis

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

(c) John H. Mathews 2004