Module for the Chebyshev Approximation Polynomial

Check out the new Numerical Analysis Projects page.

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.  The proof is found in advanced numerical analysis books.  

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  .  

The Affect of Nodes  

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  .  

Observation.  The magnitude of Q(x) is less when the Chebyshev nodes are used and larger when equally spaced notes are used.  This becomes more pronounced when the degree is larger.

Are you convinced that using the Chebyshev nodes on [-1,1], will decrease the magnitude of the term Q(x) in the remainder term  ?  

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  .   

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.

Mathematica Subroutine (Chebyshev 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. Construct three interpolating polynomials of degree  n=1  for the function    over  .  
Use the following sets of interpolation nodes.
(a).  Use the nodes  .  
(b).  Use the nodes  .  
(c).  Use the Chebyshev nodes  .
Solution.

Example 1.  Investigate a Chebyshev polynomial for  .
Solution 1.

Example 2.   Form several Chebyshev polynomials of degree  n = 1,2, 3, 4, and 5  for the function    over the interval    using Chebyshev's abscissas.
Solution 2.

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

Example 4.  What is the maximum over the interval  [0, 1]  for each of the quantities, where    is the Chebyshev polynomial.
4 (a).  Find  .  
4 (b).  Find  .  
4 (c).  Find  .  
4 (d).  Find  .  
4 (e).  Find  .  
4 (f).  Compare the result with the error bounds for the Lagrange polynomial based on equally spaced points.
Solution 4.

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

Research Experience for Undergraduates

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

Downloads (Chebyshev Approximation Polynomial Chebyshev Approximation Polynomial).  
Download this Mathematica notebook.  

(c) John H. Mathews 2003