Homework 3: assigned Tue Feb 14, due Tue Feb 21 at 5 p.m.

Since Monday Feb 20th is a holiday, I will hold office hours Tue Feb 21 from 11-12. I will not be available after 12 on the 21st. Change in policy: please submit all homework on paper -- give it to me in person or leave it under my door (WWH 429), not in my mailbox. If you cannot submit the hard copy by the deadline, you can submit an email copy to s70421g2@cs.nyu.edu (note this is a different grader email than the one used for hw1 and hw2) by the deadline and follow it up by submitting hard copy the next day that you are on campus. The email copy and the hard copy must match.

Ground rules for homework: if necessary, you can get help from any source (friends, classmates, books, the web) but you must acknowledge the source in your submission. Penalty for not reporting your sources : grade of zero for the homework. Penalty for late homework: 20%. Homework will not be accepted more than one week late.

If you have any questions about homework, please email me, not the grader. Also, you may send questions to the class mailing list, and suggestions for trouble-shooting (but not homework solutions!) may be posted there too.

Review questions from Ascher and Greif (A&G), p.89-90 (but skip (d),(e),(f),(j)): do not submit these.

Homework to be submitted:

• Exercises from A&G, p.90-91: 1, 5, 6 (see p.76-77), 8, 9, 10.
  
  
• Prove matrix norm properties 1, 2 and 3 on p. 76 of A&G directly from the definition of the matrix norm at the top of the page.
  
  
• Generalize the code on p.84 as follows: write (in Matlab) function [A,x,p] = polyInterpOrApprox(t,b,deg,nPlot) that takes as input the data vector t whose entries are ordered and distinct, data vector b with any real entries, the integer deg and the integer nPlot, and gives as output the Vandermonde matrix for interpolating/approximating the data by a polynomial of degree deg and the corresponding coefficient vector x, as well as the vector p representing the corresponding polynomial values evaluated on an equally spaced grid of nPlot points (called "v" in A&G, but that could be confusing as it does not stand for Vandermonde but represents polynomial values). If t and b do not have the same length (type "help length"), the function should throw an error (type "help error"). Let's call that length m. If m is less than deg+1, the function should throw an error as there is not enough data to determine a polynomial of degree deg. Otherwise, the function should set A to the Vandermonde matrix. This will be square, as on the bottom of p.83, if m equals deg+1; otherwise it will be rectangular, with more rows than columns. Then the function should generate x by the backslash command x=A\b, which solves a system of linear equations if m equals deg+1 and solves a linear least squares problem (see p.85) otherwise. Then the function should compute p, the interpolating or approximating polynomial values evaluated on tt, a grid of nPlot ordered points equally spaced between t(1) and t(m) (type "help linspace"). Finally, the function should plot the points (tt(i),p(i)) with a solid blue curve (the default symbols for plot) as well as the original data points (t(i),b(i)) as red circles, as in Fig 4.6. Note the need to invoke hold on between the two plot commands. If nplot is zero the program should not fail; it should set p to the empty vector [ ] and should plot only the red circles.
  
  
• Debug the program by making sure it reproduces Fig 4.6 on the data given there (except that it does not plot points to the left of the first data point or to the right of the last one) and that it also works for higher degree interpolating polynomials (say up to degree 8) when m=deg+1, and that it produces some "reasonable" approximating polynomials when m>deg+1, even if it is much greater. In particular run it on this data and this data.
  
  
• Assuming m=deg+1, what happens if:
  • You make the degree much bigger than 8, say 20 or 50?
  • You use small degree, such as 5, but evaluate and plot the p vector on a grid tt of points that runs from substantially less than t(1) to substantially greater than t(m)? This is called "extrapolation".
  • The t points are not all distinct, for example, t=[1 1 2 3]?
    
    
• Include comments in your program that explain what it does. You will not receive full credit if the function does not have reasonable comments.
  
  
• Turn in a listing of the function, plots for the two given data sets, and plots that address the various questions above.

Some Useful Tips in Matlab

• Write vector and matrix operations, avoiding loops, whenever possible
• Type "dbstop if error" at the keyboard so that errors will take you into the debugger when they occur. To get out of the debugger, type "dbquit".
• Type "shg" to bring the active graphics window to the front
• Type "clf" to clear the current active graphics window