MS-C1650 - Numerical Analysis
Week 17: Lecture 4: Interpolation - Different Bases

Harri Hakula, 2021

Reference

Let us define a reference set of points for our interpolation examples.

data={{0,0},{1,3},{2,4},{3,1},{4,-1}};
ip=Expand@InterpolatingPolynomial[data,x]
Show[Plot[ip,{x,0,4}],ListPlot[data,PlotStyle->Red,PlotMarkers->Automatic]]

Lagrange

Clear@LagrangeShapes

LagrangeShapes[data_]:=Block[{x,len,ind,local},
len=Length[data];
ind=Range[len];
Table[
Product[(x-data[[j,1]])/(data[[i,1]]-data[[j,1]]),{j,Complement[ind,{i}]}]
,{i,len}]
]

Plot[LagrangeShapes[data],{x,0,4},Epilog->{Red,PointSize[0.02],Point@Thread[List[Range[0,4],1]]}]

Plot[data[[All,2]].LagrangeShapes[data],{x,0,4}]

Show[Plot[data[[All,2]].LagrangeShapes[data],{x,0,4}],ListPlot[data,PlotStyle->Red,PlotMarkers->Automatic]]

lp=Expand[data[[All,2]].LagrangeShapes[data]]

lp-ip

Newton

NewtonCoefficients[data_]:=Block[{L,b,n,x,a},
n=Length[data];
x=data[[All,1]];
b=data[[All,2]];
L=ConstantArray[0,{n,n}];
L[[All,1]]=1;
Do[
L[[j;;,j]]=Product[x[[j;;]]-x[[k]],{k,1,j-1}]
,{j,2,n}];
a=LinearSolve[L,b];
a
]

NewtonBasis[data_]:=Block[{n,x,shapes},
n=Length[data];
shapes=Table[Product[x-data[[j,1]],{j,1,k}],{k,1,n-1}];
Prepend[shapes,1]
]

a=NewtonCoefficients[data]

shapes=NewtonBasis[data]

Plot[NewtonBasis[data],{x,0,4},Epilog->{Red,PointSize[0.02],Point@Thread[List[Range[0,4],0]]},PlotRange->All]

np=Expand[a.shapes]

np-ip

Divided Differences

Divided differences are important both in theoretical and low-level practical applications. Here we define them using recursion.

Clear@DividedDifference

DividedDifference[{{x_?NumericQ,y_?NumericQ}}]:=y

DividedDifference[data:{{_?NumericQ,_?NumericQ}..}]/;Length[data]>1:=(DividedDifference[Rest[data]]-DividedDifference[Most[data]])/(data[[-1,1]]-data[[1,1]])

data

Table[DividedDifference[data[[1;;k]]],{k,Length[data]}]

NewtonCoefficients[data]