AMath 352 { Winter 2018
Homework 6
Due Tuesday Mar. 13th, 11:59pm, on Scorelator
Problem 1 | Constrained least squares
Recall that any matrix A2Rm n of rank n has a reduced QR decomposition A = QR, with Q2Rm n
orthogonal (QTQ = In) and R2Rn n upper triangular. We have seen in class that QQT2Rm m is
a projector onto the range of A, while I QQT is a projector onto range A? , where
5. Compute the reduced QR decomposition, v = qr, where q2R3 1 and r2R.
2. Compute B = I3 qqT. Save it with save A1.dat B -ascii ;
3. Find the solution to the following least squares problem:
and save it in A2.dat
4. Suppose we now insist the solution satis es xTv = 0:
Save the solution x to this problem in A3.dat
Hint: you can take care of the requirement xTv = 0 as follows:
substitute x = I3 qqT w into the least squares problem minxkAx yk2,
solve the resulting problem in w,
with w, retrieve x.
Hint: Useful Matlab commands for this part involve qr(A,0) to QR-factorize a matrix A, x = Anb to
solve a linear system Ax = b for x. For ill-conditioned linear systems, use x = pinv(A) * b instead.
Problem 2 | Continuing on data tting
Let consider a set of data stored in a le uploaded on Canvas in the Files/Homeworks/Homework 6
section.
You can load these data in Matlab by using:
H = load("data.m") ;
H is a two-column matrix of n rows which contains the x coordinate of the points as the rst column
and the corresponding values y as the second column.
Note: you must submit this le to Scorelator in addition to your Matlab code.
We are interested in deriving a t for these data.
1. From H, extract the vector x of x components and the value vector y.
2. We want to determine the best t g?(x) to the data fx;yg in the following sense:
g?2arg min
g2G
ky(x) g(x)k:
The class G is chosen as P15, the set of polynomials of degree no larger than 15: g(x) =
c1 x15 + c2 x14 + ::: + c15 x + c16.
Since the data are only known at nitely many points, the problem reformulates in a discrete
setting as follows: letting gi g(xi), 8i = 1;:::;n, one nally solves for
g?2arg min
g
ky gk2 :
Write the optimal coe cients associated with the monomials (of decreasing order) as a column
vector c in A4.dat.
3. If you plot the t, you would note that it is rather wiggly compared to the true curve. Let us
consider the following weighted norm on Rn:
kzk2w = nz21 + (n 1)z22 + ::: + 2z2n 1 + z2n; 8z2Rn:
Observe you can write
kzk2w =kDzk22 ;
where D is a 16 16 diagonal matrix.
Suppose you consider a generic least squares problem with this regularization:
minz kAz bk22 + 0:1 kDzk22 :
Reformulate the tting problem considered above in question 2 into a linear system to solve for
polynomial tting problem with the additional regularization.
Write the optimal coe cients associated with the monomials (of decreasing order) as a column
vector in A5.dat.
Hint: Useful Matlab commands for this part involve diag(d) which allows to create a diagonal
matrix D from a vector d.