CSE 477 / G. Farin
Interpolation

This explores the Vandermonde approach. A set of knots (Subscript[t, i ])is prescribed and then a set of data points is defined with the same number as elements. The interpolation problem is solved once we find a Bezier polygon bez such that the corresponding curve passes through the data points.

	x(t) = (Subscript[b, 0])(Subscript[B, 0]^3)(t) + (Subscript[b, 1])(Subscript[B, 1]^3)(t) + (Subscript[b, 2])(Subscript[B, 2]^3)(t) + (Subscript[b, 3])(Subscript[B, 3]^3)(t)   general cubic
	
	x((Subscript[t, 0])) = (Subscript[b, 0])(Subscript[B, 0]^3)((Subscript[t, 0])) + (Subscript[b, 1])(Subscript[B, 1]^3)((Subscript[t, 0])) + (Subscript[b, 2])(Subscript[B, 2]^3)((Subscript[t, 0])) + (Subscript[b, 3])(Subscript[B, 3]^3)((Subscript[t, 0])) 
	        =
	        =
	x((Subscript[t, 3])) = (Subscript[b, 0])(Subscript[B, 0]^3)((Subscript[t, 3])) + (Subscript[b, 1])(Subscript[B, 1]^3)((Subscript[t, 3])) + (Subscript[b, 2])(Subscript[B, 2]^3)((Subscript[t, 3])) + (Subscript[b, 3])(Subscript[B, 3]^3)((Subscript[t, 3])) 
	
Short:
	X = V · B
	
Find unknowns in B:

	B = (V^(-1)) · X
	
Add more data points:

           x((Subscript[t, 0])) = (Subscript[b, 0])(Subscript[B, 0]^3)((Subscript[t, 0])) + (Subscript[b, 1])(Subscript[B, 1]^3)((Subscript[t, 0])) + (Subscript[b, 2])(Subscript[B, 2]^3)((Subscript[t, 0])) + (Subscript[b, 3])(Subscript[B, 3]^3)((Subscript[t, 0])) 
	        =
	        =
	        =
	x((Subscript[t, K])) = (Subscript[b, 0])(Subscript[B, 0]^3)((Subscript[t, K])) + (Subscript[b, 1])(Subscript[B, 1]^3)((Subscript[t, K])) + (Subscript[b, 2])(Subscript[B, 2]^3)((Subscript[t, K])) + (Subscript[b, 3])(Subscript[B, 3]^3)((Subscript[t, K])) 
	
Short:
	X = V · B
	
Try: finding unknowns in B:

	B = (V^(-1)) · X	doesn’t work since V is not invertible.
	
We can get a linear system for B:

	(V^T)X = (V^T)V · B	(V^T)V  is invertible!

interpol[knot_,data_]:=
(n=Length[knot]-1;

center=Sum[data[[i]],{i,1,n+1}]/(n+1);
dists=Table[Norm[data[[i]]-center],{i,1n+1}];
radius=Max[dists];
 
vandermonde=Table[BernsteinBasis[n,i-1,knot[[j]]],{j,1,n+1},{i,1,n+1}];
bez=LinearSolve[vandermonde,data];

dplot=Graphics[{Green,PointSize[0.015],Point[data]}];

points=Graphics[{PointSize[0.015],Point[bez]}];

bplot=ListLinePlot[bez];

curve[t_] :=Sum[BernsteinBasis[n,i,t]*bez[[i+1]],{i,0,n}];
cplot=ParametricPlot[curve[t],{t,0,1},PlotStyle->{Thick,Red}];

Show[{cplot, dplot,points,bplot},PlotRange->3radius]
);

n=3;

data1=Table[{0.3t^1.5,3Sqrt[t]},{t,0.0,10.0,10/n}];
data2=Table[{(1+t)Cos[t], (1+t)Sin[t]},{t,0.0,3Pi,3Pi/n}];
data2={{0,2}, {2,0}, {2,2}, {0,0}};
center=Sum[data1[[i]],{i,1,n+1}]/(n+1);
dists=Table[Norm[data1[[i]]-center],{i,1n+1}];
radius=Max[dists];
 
Do[data1[[i]]=data1[[i]]-center,{i,1,n+1}];
(* This moves all points such that their centroid is the origin. *)

uniknot=Table[t,{t,0.0,1.0,1/n}]; (* uniform knots *)

interpol[uniknot,data2]

The Runge Phenomenon

This was discovered in the early 1900s. If we sample a continuous function more and more, one would expect the polynomial interpolants to converge to the function. A counterexample is given by the Abs function.

Manipulate[(knot=Table[t,{t,0,1.0,1/n}];
databs=Table[{t,Abs[t]},{t,-1.0,1.0,2/n}];
interpol[knot,databs]),{n,2,20,1}]

One might expect that the failure interpolation to converge is due to the fact that the Abs function is not smooth. Not so, as the following example shows (Runge's original):

Manipulate[(knot=Table[t,{t,0,1.0,1/n}];
databell=Table[{t,1/(1+t^2)},{t,-5.0,5.0,10/n}];
interpol[knot,databell]),{n,2,20,1}]