MA 3457 / CS 4033 HW #3

MA 3457 / CS 4033
HW #3
1. (10 points) Cubic Splines
Here, we will assume cubic splines for a set of n ordered data points (x1, y1), . . . ,(xn, yn) are of the
form:
S(x) =



s1(x) x1 ≤ x ≤ x2
.
.
.
.
.
.
sn−1(x) xn−1 ≤ x ≤ xn
where the i = 1, . . . , n − 1 splines are defined as:
si(x) = ai(x − xi)
3 + bi(x − xi)
2 + ci(x − xi) + di
It turns out we can use properties of an interpolating function and assumptions of continuity of splines
to determine equations for the coefficients in terms of bi = Mi/2 where:
Mi−1 + 4Mi + Mi+1 =
6
h
2
(yi−1 − 2yi + yi+1), i = 2, . . . , n − 2
with h = xi − xi−1 for i = 2, . . . , n. With Boundary Conditions specified for conditions on M1 and
Mn−1, we can write this system of equations as a linear system AM~ = R~ where we need to solve for
M~ . Once we have M~ , we then have bi = Mi/2 and di = yi for i = 1, . . . , n − 1. Then ci and ai can be
determined based on bi for i = 1, . . . , n − 1. Refer to slides 16-17 of power point from Tuesday Nov 1st
class.
(a) (5 points) It turns out that the matrix A is diagonally dominant. Explain what this property is,
why you can see it is true for rows 2, . . . , n − 2, and how it leads to knowing we can solve for
coefficients uniquely.
(b) (5 points) We would call A a sparse matrix since it has many entries that are 0’s. As we know from
earlier discussions about error, each 0 entry will be represented by its floating point representation
in the computer where 0 = fl(0) + . From an error and computational storage standpoint, why
does it make sense to use a sparse matrix representation where you only store non-zero entries in
the matrix? (Note that Matlab and most programming languages have sparse matrix utilities)
2. (15 points) Discrete Least Squares
(a) (7 points) Write a code that takes an input of D for the degree of the least squares polynomial
that you want to fit to the data. The data points are x =[1, 1.1, 1.3, 1.5, 1.9, 2.1], y =[1.84, 1.96,
2.21, 2.45, 2.94, 3.18].
1
(b) (5 points) Determine the discrete least squares polynomials of degrees 1, 2, and 3 for the data.
Create a plot for each polynomial fit. Plot both the data points (using a symbol for data in Matlab
such as ‘og’ or ‘xg’) and also plot the polynomial at additional points xeval=linspace(0,3,100)
with the data.
(c) (3 points) Compute the error in each polynomial approximation of degree D, ED =
Pm
k=1(yi −
pn(xi))2
for m data points.
2