Homework 6. Assigned: Thu Apr 5. Due: Fri Apr 13 at 4 p.m.

1. Splines: write a Matlab function myspline(x,f,n,k) to plot a cubic spline passing through n+1 data points (x_i,f_i), i=1,...n+1, plotted at k additional points in each interval (x_i, x_i+1). Follow the algorithm described in Section 11.2 of the text, where the notation is actually for data points (x_i,f_i), i=0,...n: unfortunately Matlab doesn't allow zero-subscripting. Use the free boundary (natural spline) conditions. Although the derivation is complicated, the algorithm is not:
   • solve the tridiagonal system at the bottom of p.243 for the c_i. The notation f[x_i, x_i+1] used on the top of p.244 (and also in equation (11.3b)) is from Section 10.3; it refers to the divided difference (f(x_i) - f(x_i+1))/(x_i - x_i+1), that is (f_i - f_i+1)/(x_i - x_i+1), since there is no explicit function f provided here, just data values f_i
   • plug the c_i into equation (11.4a) and (11.4b) to get the d_i and b_i
   • for each i, plot the polynomial s_i(x) (see equations (11.2a) and (11.3a)) on k equally spaced points in each interval (x_i, x_i+1, using 'r.', 'g.', 'b.', etc., for the 3rd argument to plot so that it doesn't do any additional interpolation and so that adjacent cubics are plotted in different colors
   • also plot the original data points using '*' for the 3rd argument to plot
   • solve the tridiagonal system with the backslash \ at first to make sure it is solved correctly, and compare your spline with the one obtained and plotted with the built-in spline. The results will be slightly different since the latter uses different boundary conditions.
   • write your own tridiagonal solver tridiag.m, which solves a general tridiagonal system without pivoting and using only O(n) storage: the input should be the 3 diagonals of the matrix stored as vectors. Call this from myspline.m and make sure you get the same the results as you do using the backslash \. How many multiplications and additions are required? Answer this in the comments.
2. Parametric Piecewise Cubic Hermite Polynomials (Bezier Polynomials): show that the formula for X(&tau) and Y(&tau) given 2/3 of the way down the page on p.253 indeed satisfies the conditions 1/3 of the way down the page, with the derivatives scaled by 3 as explained in the middle of the page. To do this you need to
   • evaluate X(0),X(1),Y(0),Y(1)
   • write down formulas for the derivatives X'(&tau) and Y'(&tau)
   • evaluate X'(0),X'(1),Y'(0),Y'(1)
3. Exercise 8, p. 256 of the text, following the pattern shown in Example 11.7, p. 253-254. Use only Bezier polynomials. You should use ginput and plot but you may not use any built-in interpolation routines such as spline, etc. Email myspline.m and tridiag.m to the grader, zz299@nyu.edu, with a cc to me. He will test them on his own input. Questions 2 and 3 can be turned in either on paper or by submitting a single pdf file by email. Don't forget to include the plot that shows the guidepoints as well as the interpolation points, as well as your source code.

Reading: Chapter 11, except Section 11.3