Background for the Chebyshev approximation polynomial.  

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

        ,  

where the remainder term    has the form

        .  

and    is the polynomial of degree    given by    

        

Using the relationship

            

our task is to determine how to select the set of nodes    that minimizes  .  Research investigating the minimum error in polynomial interpolation is attributed to the Russian mathematician Pafnuty Lvovich Chebyshev (1821-1894).

Table of Chebyshev Polynomials.  
        

	=
	=
	=
	=
	=
	=
	=
	=

  

Recursive Relationship.  

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

          

  and use the recurrence relation

        .  

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."

Exploration 2.

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

Roots of the Chebyshev polynomials

    The roots of    are  .  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, ,  is the product of    and   .  To minimize the factor  ,  Chebyshev discovered that    must be chosen so that  , 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    in  [-1,1],  

the polynomial    is the unique choice which has the property

            

Moreover,

            .  

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 .
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  .  

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  .  
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    to    is to be obtained on the interval  [a,b],  then we change the variable so that the problem is reformulated on  [-1,1]:

      or  ,

where  .  The required Chebyshev nodes of    on  [-1,1]  are

    ,  

and the interpolating nodes    on  [a,b]  are obtained using the change of variable    for  .  

Theorem (Lagrange-Chebyshev Approximation).  Assume that    is the Lagrange polynomial that is based on the Chebyshev interpolating nodes    on  [a,b]  mentioned above.  

If    then

          

holds for all  .   

Proof  Chebyshev Polynomials  Chebyshev Polynomials  

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

    .  

The coefficients    are computed with the formulas  

    ,  
and  

    ,  

for    where   for  .  

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.  

    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.

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

Example 1.   Form several Chebyshev polynomials of degree  n = 1,2, 3, 4, and 5  for the function    over the interval    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    over the interval    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    is the Chebyshev polynomial.
5 (a).  Find  .  
5 (b).  Find  .  
5 (c).  Find  .  
5 (d).  Find  .  
5 (e).  Find  .  
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.

Example 6.  Find the Chebyshev polynomial approximation for  , on the interval , , and .  
Solution 6 (a).
Solution 6 (b).
Solution 6 (c).

Example 7.  Find the Chebyshev polynomial approximation for  , on the interval .  
Solution 7.

Example 8.  Find the Chebyshev polynomial approximation for  , on the interval .  
Solution 8.

Example 9.  Find the Chebyshev polynomial approximation for  , on the interval , and .  
Solution 9 (a).
Solution 9 (b).

Example 10.  Find the Chebyshev polynomial approximation for  , on the interval .  
Solution 10.

Example 11.  Find the Chebyshev polynomial approximation for  , on the interval .  
Solution 11.

Example 12.  Find the Chebyshev polynomial approximation for  , on the interval .  
Solution 12.

Example 13.  Find the Chebyshev polynomial approximation for  , on the interval .  
Solution 13.

Example 14.  Find the Chebyshev polynomial approximation for  , on the interval .  
Solution 14.

Example 15.  Find the Chebyshev polynomial approximation for  , on the interval .  
Solution 15.

Example 16.  Find the Chebyshev polynomial approximation for  , on the interval .  
Solution 16.

Example 17.  Find the Chebyshev polynomial approximation for  , on the interval .  
Solution 17.

Example 18.  Find the Chebyshev polynomial approximation for  , on the interval .  
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