You may collaborate in groups of at most three, but you must turn in your own writeup. Please list the names of the people you collaborated with and any external resources you used. Please submit an electronic version via Moodle that includes code and plots. Submissions will shut o at 3:00pm on Wednesday, October 11, and no late submissions will be accepted.
Write a function called vandermonde that takes two arguments, n and d, where n is the number of points and d is degree of polynomial, and returns the Vandermonde matrix of size n (d + 1).
The values x1; : : : ; xn that you use should be evenly spaced in the interval [
1; 1], with x1 = 1
and xn = 1. As a check,
2
1
1
3
1
1
1
1=3
1
6
1=3
7
vandermonde(3,2) returns
1
1
1
; vandermonde(4,1) returns
:
1
0
0
5
21
3
4
61
1
7
4
5
Let An be the n n Vandermonde matrix computed with your function vandermonde(n,n-1). For n = 2k + 1 with k = 1; : : : ; 8, plot the condition number of An versus n. Note that the Matlab function cond computes the condition number of a matrix. Use a logarithmic scale on the vertical axis of your plot. (Hint: look up the function semilogy for the plot.) What’s going on?! What does this tell you about interpolation on evenly spaced points?
Consider the function
f(x) = 2 + x + x sin(2 x); x 2 [ 1; 1]:
(1)
Using your vandermonde function, compute the coe cients of a least-squares- t degree-3 poly-nomial from n = 33 evenly spaced samples of the function. In other words, your data is
xi =
1 + 2
i
1
;
yi = f(xi); i = 1; : : : ; n;
(2)
n
1
where n = 33. Make a plot of both f(x) and the cubic polynomial approximation on 100 evenly spaced points.
For d from 1 to 31, compute the least-squares coe cients of a polynomial of degree d using the function f(x) from Equation (1) sampled at 33 evenly spaced points in [ 1; 1]. In other words, your data is the same as in Problem 3. For each d compute the largest error in the polynomial approximation over 100 evenly spaced points. In other words, if pd(x) is your polynomial of degree d, the error ed is
ed =
max
jf(xj ) pd(xj )j
;
(3)
where
1 j 100
jf(xj )j
j
1
xj =
1 + 2
;
j = 1; : : : ; 100:
99
Plot the error ed versus d on a log scale (that is, use semilogy). Interpret the error behavior as a function of the polynomial degree.
For d from 1 to 31, compute the condition number of the matrix you used to compute the least-squares polynomial coe cients in the previous part. Plot the condition number versus d on a log scale. How does this compare to the plot you made in the Problem 2?
1
