Choice of Nodes and Interpolation.

This demonstration shows the interpolating polynomial and the function for some explicit examples.

f[x_] := 1/(1 + (10*x)^2);

a = -1;
b =    1;
n  =   40;

EqualNodes := Table[{a + (b-a)i/n,f[a+(b-a)i/n]},{i,0,n}]
ChebyNodes := Table[{(1/2)*(a + b) + (1/2)(b-a)Cos[(2i+1)Pi/(2n+2)],
f[(1/2)*(a + b) + (1/2)(b-a)Cos[(2i+1)Pi/(2n+2)] ]},{i,0,n}]

EqP := InterpolatingPolynomial[EqualNodes,x];
ChebyP := InterpolatingPolynomial[ChebyNodes,x];

We now show plots of the interpolating polynomials constructed on each set of nodes, together with the original function. Here's the equally-spaced nodes interpolating polynomial:

Show[Plot[{f[x],EqP},{x,a,b}],ListPlot[EqualNodes,PlotStyle->{PointSize[Large]}]]

Now we're going to see the interpolating polynomial constructed on the Chebyshev nodes:

Show[Plot[{f[x],ChebyP},{x,a,b},PlotRange->1.5],ListPlot[ChebyNodes,PlotStyle->{PointSize[Large]}]]

This is so striking that we plot it again just to see some error!

Show[Plot[{f[x],ChebyP},{x,a,b}],ListPlot[ChebyNodes,PlotStyle->{PointSize[Large]}]]

Now last class we put in a substantial amount of work developing an explicit error bound for the approximation error on N nodes for polynomial interpolation. It's worth evaluating that error bound explicitly for this function for various values of n to see what happens. Recall that our general error bound looks like:

| f(x) - p(x) | <= (1/(4n +1 )) M (h^(n+1))

for evenly spaced nodes with spacing h, when M is a bound on the (n+1)-derivative of f, and in general, we have

| f(x) - p(x) | <= (1/((n +1)! ))M (∏_( i=1)^( n))(x - (Subscript[x, i]))

We will now evaluate the simple bound for n between 1 and 20 for our function f(x). The hard part will be getting a bound on the (n+1)st derivative of f, of course. We cheat by just sampling the (n+1)st derivative at a lot of (equally spaced) node points and taking the maximum value we find there.

M [n_] := Max[Table[D[f[x],{x,n+1}] /. x->(a + i(b-a)/(1000)),{i,0,1000}]];

EqualBound[n_] := (1/(4n+1)) * M[n] * ((b-a)/n)^(n+1);
Mtab = Table[N[M[i]],{i,1,20}]
EqualBoundTab = Table[N[Log[10,EqualBound[i]]],{i,1,20}]

Show[ListLinePlot[EqualBoundTab,AxesLabel->{x,Log[bound]},Filling->Axis],ListPlot[EqualBoundTab,PlotStyle->{PointSize[Large]}]]

As we can see, for this function, we have the error bound (and the actual error, below it) diverging to infinity rather rapidly! For 20 evenly spaced nodes, we already have a bound on the interpolation error of something like 10^17.

We can compute the actual interpolation error as well (again, by sampling at a large number of points in the interval). It's big, but a heck of a lot smaller than the bound.

ActualError[n_] := Module[{Nodes,P},

	Nodes := Table[{a + (b-a)i/n,f[a+(b-a)i/n]},{i,0,n}];
  P[x_] := InterpolatingPolynomial[Nodes,x];
	Max[Table[Abs[f[N[a + i(b-a)/(1333)]] - P[N[(a + i(b-a)/(1333))]]],{i,0,1333}]]

]
ActualError[2]
ActualErrorTab = Table[ActualError[i],{i,2,20}]

Show[ListLinePlot[ActualErrorTab,Filling->Axis,PlotRange->Full],ListPlot[ActualErrorTab,PlotStyle->{PointSize[Large]}]]

The Chebyshev error bound is still increasing, though somewhat
 slower.

ChebyBound[n_] := (1/(2^n*((n+1)!))) * M[n];

ChebyBoundTab = Table[N[Log[10,ChebyBound[i]]],{i,2,20}]

Show[ListLinePlot[{EqualBoundTab,ChebyBoundTab},AxesLabel->{x,Log[bound]},Filling->Axis],ListPlot[{EqualBoundTab,ChebyBoundTab},PlotStyle->{PointSize[Large]}]]

ActualChebyError[n_] := Module[{Nodes,P},
Nodes := Table[{(1/2)*(a + b) + (1/2)(b-a)Cos[(2i+1)Pi/(2n+2)],
f[(1/2)*(a + b) + (1/2)(b-a)Cos[(2i+1)Pi/(2n+2)] ]},{i,0,n}];	
  P[x_] := InterpolatingPolynomial[Nodes,x];
	Max[Table[Abs[f[N[a + i(b-a)/(1000)]] - P[N[(a + i(b-a)/(1000))]]],{i,0,1000}]]

]
ActualChebyError[2] 
ActualChebyErrorTab = Table[ActualChebyError[i],{i,2,20}]

The actual Chebyshev error is actually going down in this case (unlike the Chebyshev error bound).

Show[ListLinePlot[{ActualChebyErrorTab},Filling->Axis,PlotRange->{Full},AxesOrigin->{0,0}],ListPlot[{ActualChebyErrorTab},PlotStyle->{PointSize[Large]}]]