Description
ECS130 Homework Assignment 3
Due: 11:59pm, February 6, 2022
1. The Householder transformation is defined by
Hv = I – 2
vv T
vT v
for 0 6= v ? Rn .
(a) Show that Hv is symmetric.
(b) Show that Hv is independent of the scaling of v, i.e., Hav = Hv , where a is a scalar.
(c) Show that Hv is involutary, meaning Hv2 = I.
(d) What is the inverse of Hv ?
2. Use the Householder transformation to compute the QR factorization of the matrix A in
Example 5.2, i.e.,
?
?
1 1 1
A = ?0 1 1? .
0 1 0
Do you obtain the same QR factorization as the Gram-Schmidt method?
3. Suppose we consider the nonzero vector a ? Rn as an n ? 1 matrix. Write out the reduced
and full QR factorizations of a explicitly.
T
4. Let x, y ? Rn with x 6= y and kxk2 = kyk2 , find a Householder transformation Hv = I – 2 vv
vT v
such that Hv x = y. (Hint: extend the derivation on pages 100-101 for finding the vector v of
the Householder transformation Hv such that Hv x = y.)
5. (a) Take A ? Rm?n and suppose we apply the Cholesky factorization to obtain AT A = LLT .
Define Q = A(LT )-1 . Show that the columns of Q are orthonormal.
(b) Based on (a), suggest a relationship between the Cholesky factorization of AT A and the
QR factorization of A.
6. Square root fitting problem. Write a short program that computes the parameter a and ?
that minimizes
f(a, ?) =
m h
X
(a + ?ti ) –
v i2
ti
i=1
for m = 4. Plot the function y =
v
with ti =
1 3 i-1
+
4 4m-1
t and the computed fitting line `(t) = a + ?t.
7. Ranking sport teams. Suppose we have four college teams, call T1, T2, T3 and T4. These
four teams play each other with the following outcomes:
? T1 beats T2 by 4 points: 21 to 17.
? T3 beats T1 by 9 points: 27 to 18.
? T1 beats T4 by 6 points: 16 to 10.
? T3 beats T4 by 3 points: 10 to 7.
? T2 beats T4 by 7 points: 17 to 10.
1
To determine ranking points r1 , r2 , r3 , r4 for each team, we do a least squares fit to the
overdetermined system:
r1 – r2 = 4,
r3 – r1 = 9,
r1 – r4 = 6,
r3 – r4 = 3,
r2 – r4 = 7.
In addition, we fix the total number of ranking points, i.e., r1 + r2 + r3 + r4 = 100. Find
the values of r1 , r2 , r3 , r4 that most closely satisfy these equations, and based on your results
rank the four teams.1
1
This method of ranking sport teams is a simplification of one introduced by Ke Massey in 1997. It has evolved
into a part of the famous BCS (Bowl Championship Series) model for ranking college football teams and is one factor
in determining which teams play in bowl games.
2
Purchase answer to see full
attachment
