Lab 5: Polynomial Interpolation
```To see visually how good and bad various interpolation methods
can be, we'll use Matlab's interpolation functions and plotting,
on data generated from Runge's function:
f(x) = 1/(1+x2)
In Matlab (diary on), do the following:

1. Generate N+1=11 equi-spaced nodes Xi in the interval [-5,5]:
X = [-5:1:5];    (to see values, omit the ;)
and evaluate f(x) at these nodes:
Y = 1./(1+X.^2);
The N+1 points (Xi, Yi) are the data points to be interpolated
by various methods. Plot them to see where they are:
plot(X,Y,'o')
title('N+1 = 11 equi-spaced data points')
pause

Also generate lots of points xi at which to evaluate f(x) and the
interpolants for plotting:
x = [-5:0.1:5];      (this is a lower case x, not X)
Evaluate f(x) at these xi's and plot y=f(x) and the data points:
plot(x,y,'-', X,Y,'o')
title('Runge f(x) and data pts')
pause

Now, we use the data points (Xi, Yi) to construct various interpolants.
A good interpolant should "reproduce" the function f(x) as close as
possible. Let's try a few.

2. Nth degree interpolating polynomial:
Use Matlab's polyinterp to construct (the coefficients of) the
Nth degree interpolating polynomial (here N=10):
pN = polyfit( X,Y, N);
Now this can be evaluated anywhere in the interval [-5,5] with polyval,
e.g. at the xi's:
v = polyval( pN, x);
Find the Inf-norm error ∥y-v∥∞:
err = norm(y-v, inf)
and plot both f(x) and pN(x) on the same plot:
plot(x,y,'-', x,v,'x-')
title('f(x) and pN(x) at plotting pts')
pause

Is this a good interpolant ?  Why ?

3. Interpolation at Chebychev nodes:
Generate N+1=11 Chebychev points (Xchebi, Ychebi) in [a,b]:
fprintf('------ chebychev nodes ------\n')
K = N+1;
a=-5;  b=5;
for i=1:K
Xcheb(i)=(a+b)/2 + (b−a)/2 *cos( (i−0.5)*pi/K );
end
Ycheb = 1./(1+Xcheb.^2);

Follow the steps in 2. to produce the Nth degree interpolating
polynomial pNcheb based on the Chebychev nodes, its values
vcheb at the xi's, the error ∥y − vcheb∥∞,
and plot both f(x) and pNcheb(x) on the same plot.

Compare the error and plot with those from 2.
Which one is better ?  why ?

4. Piecewise linear interpolation:
Use Matlab's interp1 to construct the linear interpolant:
lin = interp1(X,Y, x, 'linear');
Repeat the steps of 2.

Compare errors and plots.

5. Piecewise cubic interpolation:
Use Matlab's interp1 to construct the cubic interpolant:
cub = interp1(X,Y, x, 'cubic');
Repeat the steps of 2.

Compare errors and plots.

6. Cubic spline interpolation:
Use Matlab's interp1 to construct the spline interpolant:
spl = interp1(X,Y, x, 'spline');
Repeat the steps of 2.

Compare errors and plots.

7. To see that the error gets worse for bigger N for equi-spaced
nodes but not for Chebychev nodes (for this f(x) at least),
repeat 2. and 3. with N = 20.

diary off

Clean up your "diary" to create a matlab script, "lab5.m", that
does all the above.  Then insert comments (lines starting with %),
describing what each step does. Make sure your script works.