# BEST代写-线上编程学术专家

Best代写-最专业靠谱代写IT | CS | 留学生作业 | 编程代写Java | Python |C/C++ | PHP | Matlab | Assignment Project Homework代写

# Matlab数学代写 | CS 475/675 Spring 2021: Assignment 3

### Matlab数学代写 | CS 475/675 Spring 2021: Assignment 3

1. (6 marks) Let v be a given non-zero column vector.

(a) (2 marks) Show algebraically that the orthogonal projection matrix P = I vvT
vT v is idempo- tent, i.e. PP = P. (This property ensures that applying such a projection matrix repeatedly
has no additional e ect after the rst application.)

(b) (4 marks) One characterization of an orthogonal matrix Q is that its transpose equals its
inverse, i.e., QT = Q 1. Derive (separately) the transpose and the inverse of the Householder
matrix F = I 2vvT
vT v
; and thereby show that F is an orthogonal matrix. (Hint: Use the fact
that F is an identity matrix to which a rank-one update has been applied.)

2. (10 marks) Adapt the ideas of Householder QR-factorization to derive a method to instead
compute a factorization A = QL, where L is lower triangular and Q is orthogonal. Assume that
A is square and full-rank. Give a text description of how your algorithm works, supported by
illustrations and pseudocode. (Hint: Derive a modi cation of the Householder approach such
that (I 2vvT =vT v)x is zero everywhere but its last component, rather than its rst.)

3. (7 marks) Use Householder transformations to perform a QR factorization of the following matrix
by hand.

Show your work, and give the resulting factors.

4. (15 marks) Let A be a symmetric tridiagonal matrix.

(a) (4 marks) In the QR factorization of A = QR, which entries of R are in general nonzero?

(b) (5 marks) Show that the tridiagonal structure is recovered when the product RQ is formed.
(Hint: Show that (i) RQ is upper Hessenberg, and (ii) RQ is symmetric.)

(c) (6 marks) Explain how the 2  2 Householder transformation can be used in an ecient
algorithm to compute the QR factorization of a tridiagonal matrix. (Similar to the more
general algorithm we saw in Lecture 19, your method here does not need to explicitly form

Q.) Determine whether the op count complexity of your proposed algorithm will be linear, 