CS227:Assignment 5 - Interpolation

Assigned Tuesday, October 11
Due Tuesday, October 18

If you want to read something apart from the posted notes, check out Chapter 3 of Moler.  We will not use Moler's textbook implementations of  the various interpolation methods, nor will we bother with the lengthy derivations of the algorithms for cubic splines and piecewise cubic Hermite interpolation.  We will instead use polyfit(x,y,n), where n is one less than the dimensions of the vectors x and y, to compute polynomial interpolants, and interp1(x,y,z,method) where method is one of the strings 'linear', 'splines' or 'pchip' to compute the others.  Play around with the interpgui program to get a feel for the different interpolation methods.

In Exercise 1  you are asked to interpolate a sequence of points in the plane that do not necessarily lie on the graph of a function.  So you will need to 'decouple' the points:  If you start out with (x0,y0),...,(xn,yn) you will interpolate through the points (0,x0), (1,x1),...,(n,xn) with a function x(t), and separately through (0,y0),..,(n,yn) with y(t), and then plot the parametrized curve (x(t),y(t)).

1. Create a Stylish Illegible Signature.  If you apply the above procedure to a dozen or so randomly generated points (xi,yi) using spline interpolation, the effect is amusing:  It often looks like one of those fancy illegible signatures that bear absolutely no resemblance to the signer's name.  It will also give you some sense of why spline interpolation is used in computer graphics.

Write a script that performs the following sequence of steps:

(a) Selects a number n between 8 and 16 at random.
(b) Generates n random points in the plane, and plots them. (If you have vectors x and y of the x- and y-coordinates of the points, you can plot them with plot(x,y,'o'), so that only the points are shown and not  the line segments connecting them).
(c) Then include the statements hold on; pause;  This pauses execution until you type the enter key, but will allow the next plot to be superimposed on this one.
(d) Finally, draws the curved interpolation path, as described above, using spline interpolation.

If you enclose these statements inside an infinite loop while(1)...end  you can generate a lot of 'signatures', and save the best-looking ones. (You will want to turn hold  off and pause again between signatures.)

You should experiment with variants. Try this out with pchip interpolation and polynomial interpolation as well.  Include some samples of each, and comment on the differences.  (For polynomial interpolation, don't use more than 10 points.) You might also see what is different if instead of using equally spaced values 0,1,...,n for the independent variable in the interpolating functions, you made the spacing proportional to the distance between the points.


2. Table Lookup. Write a function

u = table_lookup(x,y,z)

Here is the meaning of the arguments:  The input arguments x and y are row vectors of the same size, where x is sorted in ascending order.  The input argument z is a row vector, which in general will have a different size (and that may well be a scalar).  The output argument is a row vector of the same size as z.

The entries of x and y are assumed to be the tabulated values of some unknown function f.  The entries of z are supposed to be values at which you would like to evaluate the function f.  Generally speaking, these will not match the entries of x where the values of f have been tabulated, so you will have to interpolate.  The output argument u should be the computed values of f at the entries of z.

To perform the interpolation, for each entry z(j) of z your function should locate the entries x(i) and x(i+1) such that x(i) <= z(j) <= x(i+1) and then use polynomial interpolation with the third degree polynomial that passes through the points

(x(i-1),y(i-1)), (x(i),y(i)) , (x(i+1), y(i+1)) (x(i+2),y(i+2))

If z(j) falls between the first two points of x, or the last two points of x, you need to adapt this procedure and instead use quadratic interpolation with the first three or last three values of x and y.

How do you search for the appropriate interval that contains a value??  You can try a statement like

i=1;
while(x(i)<=val)
    i=i+1;
end

but you may have to modify this somewhat to prevent the array index from becoming too large.  If the value you are searching for is less than the first element of x, or greater than the last element of x, an error message should be printed.

Test your function by tabulating values of sin(x) at 20 different points between 0 and pi/2, and interpolating at 200 equally spaced points in this interval.  Plot the result and find the maximum error at your interpolated points. It is actually more informative to plot the difference between your interpolated values and the correct values of the sin function.


What to hand in.  For Problem 1, your M-file, your favorite plots, and a bit of narrative evaluating the effects of different methods.  For Problem 2, the code for your function, the commands you typed to test it, and the resulting plots and error results.