MS-C1650 - Numerical Analysis
Week 17: Lecture 3: A Gentle Introduction to Interpolation

Harri Hakula, 2021

Interpolation

Let us assume that we have a set of data points and we want to fit a polynomial which is exact at the data points. Consider a sine function.

x=Subdivide[0,2Pi,10];
y=Sin[x];
Show[Plot[Sin[x],{x,0,2Pi}],ListPlot[Transpose[{x,y}],PlotStyle->Red,PlotMarkers->Automatic],ImageSize->Large]

poly=InterpolatingPolynomial[N@Transpose[{x,y}],t];

Show[Plot[Sin[x],{x,0,2Pi}],ListPlot[Transpose[{x,y}],PlotStyle->Red,PlotMarkers->Automatic],Plot[poly,{t,0,2Pi},PlotStyle->Black],ImageSize->Large]

err=Expand@N[poly-Normal@Series[Sin[t],{t,Pi,9}]]

Show[Plot[err,{t,0,2Pi},PlotRange->All,ImageSize->Large],ListPlot[Thread[List[x,0]],PlotStyle->Red,PlotMarkers->Automatic]]

Runge Phenomenon

The example above is misleading. Let us consider another example. (Notice that it is misleading in its own way!) The idea is to examine what happens when we increase the number of equidistant points.

np=20;
x=Subdivide[-1,1,np];
y=1/(1+25x^2);
poly=InterpolatingPolynomial[N@Transpose[{x,y}],t];
Show[Plot[1/(1+25x^2),{x,-1,1}],ListPlot[Transpose[{x,y}],PlotStyle->Red,PlotMarkers->Automatic],Plot[poly,{t,-1,1},PlotStyle->Black],ImageSize->Large,PlotRange->All]

Runge Phenomenon (Solution)

Now repeat the process above. By choosing the interpolation points appropriately, one can control the oscillations (and thus the error).

np=25;
xp=Table[Pi(2k-1)/(2np),{k,1,np}];
x=Cos[xp];
y=1/(1+25x^2);
poly=InterpolatingPolynomial[N@Transpose[{x,y}],t];
Show[Plot[1/(1+25x^2),{x,-1,1}],ListPlot[Transpose[{x,y}],PlotStyle->Red,PlotMarkers->Automatic],Plot[poly,{t,-1,1},PlotStyle->Black],ImageSize->Large]