Advanced Linear Algebra for Computing Exam 1
Please acknowledge the following (initial each)
I will not and have not used notes, books, or other outside re- sources while taking this exam.
I will not and have not consulted any individuals (other than course staff) during this exam.
The answers to this exam that I upload are wholly my own.
I will not share this exam or any information about this exam with any other person in the class or not in the class other than the teaching staff. This includes sharing the exam with anyone (other than course staff) at anytime, even after the class has completed, for all of eternity, and beyond, unless explicit permission has been granted by or Robert van de Geijn
You are free to use scratch paper (that starts being blank).
Signed: Date:
1. (a)LetA= 0 1 −2 .Evaluate
i. ∥A∥1 = ii. ∥A∥∞ = iii. ∥A∥F =
(b) Let A ∈ Cm×m. Prove that ∥A∥∞ ≤ m∥A∥1. For what vector is equality attained? Justify all steps.
100 2. (a) GivetheSVDof 0 −2 0
(b) Let D = 0 δ
. Prove that ∥D∥2 = max(|δ0|, |δ1|). Justify all steps.
(c) (10 points) Let A ∈ Rm×m have the special structure α0
where α ∈ R is a scalar. Prove that ∥A∥2 = max(|α|, ∥B∥2). Justify all steps.
3. Let A ∈ Rm×m be a nonsingular matrix and x, δx, y, δy ∈ Rm. Consider solving Ax =y
A(x+δx) = y+δy (a) Prove that ∥δx∥2 ≤ ∥A∥ ∥A−1∥ ∥δy∥2 . Justify all steps.
∥x∥2 2 2 ∥y∥2
(b) Verbally interpret what the result from Part (a) says.
4. Show that if A ∈ Rm×m the QR factorization via Householder transformations requires, ap- proximately, 43 m3 flops. (If this were a real exam, Figure 3.3.4.2 from the notes would appear here). Be sure to clearly describe where what contribution to the cost comes from.
zT 2 2 2 Partition x = z . Prove that ∥z∥2 = ∥zT ∥2 + ∥zB∥2.
(b) Let Q ∈ Rm×m be a unitary matrix. Prove that ∥Qx∥2 = ∥x∥2.
(c) Let A ∈ Rm×n have linearly independent columns and let A = QLRT be its QR factor- ization with QL ∈ Rm×n. Prove that the linear least square problem
∥b−Ax∥2 = min∥b−Ax∥2 x∈Rn
issolvedbyxwhereRTx=QTLb. Justifyallsteps.