Assignment 4

Polynomial Interpolation using Chebyshev Polynomials

Due date: Monday, March 12, 2018 at class time

Required for submitting:

  • Grade Sheet Print this sheet and bring it to class the day the program is due.

  • Bring your UML diagram to class.

Purpose:

  • The purpose of this exercise is to give you more practice with the first few items listed below. In addition to these, we will revisit a topic you saw in your Cs 228 course (or equivalent, if you transferred credit) and a related topic that you probably, but maybe, did not see in your cs 228 class or equivalent. You will again have the experience of coding the necessary constructs using the OOP paradigm for polynomial interpolation. But this time you will include the results of some amazing mathematical results. In assignment #3, I included the following statement:

    • We will see in the succeeding assignment that some fairly ingenius mathematics can turn a disasterous interpolant into a much

    • better predictor. Thus, you shall discover in the next two assignments that the simplest, easiest way to do something just isn't

    • necessarily the best way.

  • You may have wondered what that meant. (Or, you may not have and been very content to wile away the hours watching "Leave it to Beaver" re-runs. There is merit in this mind set; look where it got W.) You saw in the last assignment that you got wild variations in the interpolating polynomial near the limits of the interval. In class I will discuss this phenomenon and the "fix" you will employ to get better results. In any case, you will learn that there is more than one way to solve a problem, and that numerical solutions can pose problems that the purist doesn't have to worry about. That is, some recipes for solutions work great in theory, but can have unforeseen consequences when put into practice on a computer. Others simply aren't the best solution to a given problem. For our problem, a modification of the technique is going to help considerably. You will have more fun with the following:

      1. templated classes

      2. templated functions

      3. overloading operators

      4. the concept of possibly implementing algorithms as classes

      5. C++ to "wrap" a data type

      6. Newton form of interpolating polynomials

      7. Nodes associated with Chebyshev polynomials

Resources:

The Concept:

  • You should have noticed in the last assignment that the polynomial you generated produced really fine results in part of the interval -- roughly [-.6, .6]. At the tail ends of the interval, the results were much less desirable. In fact, you should have seen wild swings in the interpolating polynomial near .9 and -.9. This phenomenon is attributable to the 'Runge' effect. It is caused by trying to fit a higher order polynomial to a set of data when one is not appropriate. It is probable that your interpolation would have turned out better had you used fewer data points.

    • There is an amazing result attributable to a Russian mathematician by the name Pafnuty Lvovich Chebyshev, a name no doubt that drove him to mathematics. Chebyshev proved results regarding the errors incurred by polynomial interpolation. To simplify his result, he showed that one could minimize the maximum error in polynomial interpolation by spacing the nodes for the interpolating polynomial not using uniform spacing, but using the same relative spacing of the intercepts of a certain class of polynomials. They are defined this way:

    • T0(x)=1 T1(x)=x T2(x)=2x2-1 T3(x)=4x3-3x . . . Tk(x)=2xTk-1(x)-Tk-2(x)

  • Of course, he (or some one else) named them the Chebyshev polynomials. There are many interesting features of these polynomials. One is that the x-intercepts of every Chebyshev polynomial are in the interval [-1,1]. So, the upshot of this discussion is that if you are going to produce an interpolating polynomial for a function, known or unknown, place your data in the interval of interest not using uniform spacing, but Chebyshev spacing. Since I'm not interested in giving you the additional headache of worrying about an arbitrary interval, I've placed our problem in the interval [-1,1]. This makes your job just a little easier. Thus, if you wish to fit a 10th degree polynomial to a set of 11 data points, just find the 11 Chebyshev nodes and you have your x-values for the spacing of your data points. Cool, eh!? Way cool.

    • So how do you find the intercepts of all these polynomials without solving a bunch of polynomials? We have that problem licked too. Here's a cool formula to make your life easy. It calculates (in order--I think) the roots of the N+1st Chebyshev polynomial, TN+1(x).

  • Alternatively, you can use the following formula, which is simpler, to calculate the roots of the Nth Chebyshev polynomial, TN(x). However, it does not generate them in (normal) order.

Program Specifications:

  • As with previous assignments, you will use the OO paradigm for your code for this programming assignment. This will be true for subsequent projects too. For the current assignment, you will generate the data for an interpolating polynomial for a given function based on Chebyshev node spacing. You will not read that information in from a file, as you did with hw #3. Then, you will generate the interpolating polynomial based on these data points. Then, in order to test the quality of your interpolating polynomial, you will evaluate the polynomial at given points (given below) and compare those estimates of the function with the results of your interpolating polynomial from hw #3 (based on equally spaced nodes) and the true values of the function at those points. Thus, you will need classes for at least:

      • Chebyshev node generator as a function of the number of nodes needed

      • generating data points based on the (hard coded) function:

      • create an interpolating polynomial based on a set of data

      • evaluating polynomials based on coefficients and a point passed to it

      • comparing results

  • You will also need to use the results of the program you wrote for hw #3. You are to use your code for the implementation of the Newton form of an interpolating polynomial for a set of data in R2 (i.e. the plane). Again, you will use your divided difference table that gives you the coefficients for the polynomial. You are required to use an array of arrays using your own templated array class to contain the data and the entries in the divided difference table entries. For this assignment, use your own array class to contain the aforementioned arrays. That is, template your array on your array. As before, you decide on the details of the implementation of your array class, but make it good: include adequate constructors, overloaded operators, etc. In considering the implementation of the Newton divided difference table, you will have to think about the functionality of your array class also.

    • Use command line arguments (argc and argv[]) to give the user (you and the grader) the ability to pass information to your program. Make the first argument to your executable the number of points to base your interpolation on. Make the second argument the name of the file to read data points for generating an interpolating polynomial with evenly spaced nodes (as in the last assignment). data set 3

    • Your program is to output the following:

      1. The (Chebyshev) data points used for the interpolation.

      2. The computed coefficients making up the (Chebyshev) interpolating polynomial - x0 coefficient first, xbiggest coefficient last

      3. The values of the interpolant at these x-vlaues:

        1. 0.1 0.3 0.5 0.7 0.9

      4. You'll note that these values fall in between the data points.

      5. The values of the function

      6. at the same values as above. The absolute error in your approximations at the above values

      7. The relative error in your approximations at the above values

      8. A comparison of the interpolants from equally spaced data and the Chebyshev node spaced data.

        1. One more thing: you need to provide stream operators for any array/vector class that you have written.

Deliverables:

    1. Code: I will test that the code you submit does indeed compile and run. You are to submit all your source code along with a makefile.

    2. makefile: Supply the makefile which compiles and builds your program as detailed above.

    3. Your gradesheet and UML (during class).