Write a C++ program that implements the Newton Interpolation.

1. Write a separate function for each of the following. You may define and call additional functions.

Computation of divided differences

Evaluation of the interpolating polynomial Must use a nested form .

2. Your program must store divided differences in a single dimensional array.

3. All floating point arithmetic will be double precision.

4. Program input: Sequence of x values of data points, x = -8,-6, -4, -2, 0, 2, 4, 6, 8

Sequence of x values to evaluate P(x), x = -8,-7,-6, -5, -4, -3,-2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8

5. Program output (See below for an example.)

Divided differences at each iteration

Table containing f(x), P(x), |f(x) P(x)| for the 17 data points.

EXAMPLE OUTPUT:

How many data points?

7

Enter X values separated by spaces: -6 -4 -2 0 2 4 6

Divided Differences

Iteration: 0 -------------

0.0270270270

0.0588235294

0.2000000000

1.0000000000

0.2000000000

0.0588235294

0.0270270270

Iteration: 1 -------------

0.0270270270

0.0158982512

0.0705882353

0.4000000000

-0.4000000000

-0.0705882353

-0.0158982512

Iteration: 2 -------------

0.0270270270

0.0158982512

0.0136724960

0.0823529412

-0.2000000000

0.0823529412

0.0136724960

Iteration: 3 -------------

0.0270270270

0.0158982512

0.0136724960

0.0114467409

-0.0470588235

0.0470588235

-0.0114467409

Iteration: 4 -------------

0.0270270270

0.0158982512

0.0136724960

0.0114467409

-0.0073131955

0.0117647059

-0.0073131955

Iteration: 5 -------------

0.0270270270

0.0158982512

0.0136724960

0.0114467409

-0.0073131955

0.0019077901

-0.0019077901

Iteration: 6 -------------

0.0270270270

0.0158982512

0.0136724960

0.0114467409

-0.0073131955

0.0019077901

-0.0003179650

How many test values? 13

How many test values? 13

Enter all X values separated by spaces: -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6

i | Xi | f(Xi) | P(Xi) | |f(Xi)-P(Xi)|

---------------------------------------------------------

0 -6 0.027027027 0.027027027 0.000000000

1 -5 0.038461538 0.674085851 0.635624312

2 -4 0.058823529 0.058823529 0.000000000

3 -3 0.100000000 -0.170429253 0.270429253

4 -2 0.200000000 0.200000000 0.000000000

5 -1 0.500000000 0.750397456 0.250397456

6 0 1.000000000 1.000000000 0.000000000

7 1 0.500000000 0.750397456 0.250397456

8 2 0.200000000 0.200000000 0.000000000

9 3 0.100000000 -0.170429253 0.270429253

10 4 0.058823529 0.058823529 0.000000000

11 5 0.038461538 0.674085851 0.635624312

12 6 0.027027027 0.027027027 0.000000000