Final exam | CSE/MATH 6643 | Spring 2022
Instructions
This exam has six questions, one for each section of the book. Each question is weighted equally, and only
the highest four scores count.
In general you should show your work to have the chance to get partial credit, but you may use results from
the book without proof, as long as it is clear which results you are using at each step.
You will submit your answers as a single pdf on canvas. You can type your answers or work out your solutions
by hand and submit a document containing scans or high quality photos of your answers.
You must turn in your submission by 10:50 a.m., Thursday, May 5.
This is a closed book, closed note exam. You should only look at the questions starting on the following
page once you have finished studying. Once you start working, you may not consult the book, your notes,
piazza, other students, or any other outside resources. Doing so will be considered an honor code violation.
Clarification questions may be asked privately of instructors on piazza.
Once you start working there is no time limit (other than the final submission deadline, see above). The exam
was written so that it should be reasonable to complete it in three hours, but you do not have to complete it
in one sitting.
Best of luck to you!
1
(Turn the page to start the exam)
2
Q1
Define f : Cm×n → R by
f(A) = sup
B 6=0∈Cm×n
|tr(B∗A)|
‖B‖2 ,
where ‖ · ‖2 is the induced matrix 2-norm.
Q1.a (40%)
Prove that f defines a norm on Cm×n.
Q1.b (40%)
Prove that f is unitarily invariant: that f(A) = f(QA) for every unitary Q and f(A) = f(AΦ) for every
unitary Φ. (A fact that you may use without proof is that the trace of a product of matrices is invariant
under cyclic permutations: tr(AB) = tr(BA), tr(ABC) = tr(BCA), etc.)
Q1.c (20%)
Use part (b) to show that f is an explicit function of the singular values of A and show what that function is.
3
Q2
Write an algorithm for computing the QR factorization of an upper Hessenberg matrix H ∈ Cm×m. Your
algorithm can represent Q in any form, and should construct R from H in place.
Your algorithm should:
• be correct; (20%)
• be backward stable; (30%)
• have optimal complexity (up to a factor of a leading coefficient). (30%)
You should correctly compute the leading term in the work required by your algorithm. (20%)
4
Q3
We can modify the least squares problem by introducing a nonstandard inner product. Let M ∈ Cm×m be a
hermitian positive definite matrix, let A ∈ Cm×n, (m ≥ n) be a rank n matrix, and let b ∈ Cm be given. We
want to compute x ∈ Cn that minimizes the quantity
‖b−Ax‖M ,
where ‖v‖M =
√
v∗Mv.
Q3.a (40%)
For the ordinary least squares problem, the residual r = b−Ax is orthogonal to range(A). State and prove a
similar orthogonality condition for this modified least squares problem.
Q3.b (40%)
The image of the solution in Cm is y = Ax. Give a formula for a matrix P such that y = Pb.
Q3.c (20%)
As with other norms, we can induce a matrix norm from the vector norm ‖ · ‖M . Show that ‖P‖M = 1.
5
Q4
Let A be a real symmetric positive definite matrix with the following properties:
• (a) aij ≤ 0 for every (i, j) such that i 6= j;
• (b) aii >
∑
j 6=i |aji| for every i.
Let LL∗ be the Cholesky factorization of A. Prove that Lij ≤ 0 for every (i, j) such i 6= j.
Hint: if a real symmetric positive definite matrix has property (a), then another way to state property (b) is
that the vector A1 is positive, where 1 is the vector of ones.
6
Q5
Suppose A is a normal n× n matrix with eigenvalues at the n roots of unity, λk = e2pi kn i for k = 1, . . . , n.
Q5.a (25%)
Does the power iteration with a random initial vector v converge to an eigenvector? If yes, what is the
convergence rate? If no, why not?
Q5.b (75%)
Now consider the matrix A + I. Does the power iteration with a random initial vector converge to an
eigenvector? If yes, what is the convergence rate? If no, why not?
7
Q6
GMRES is used to solve Ax = b using only matrix-vector products with A. It is usually assumed that the
matrix A is nonsingular. But in this question we try to use GMRES on singular matrices. (In this question,
we mean GMRES with an initial guess of x0 = 0.)
Q6.a (40%)
Suppose A is diagonalizable: prove that if b ∈ range(A), then GMRES converges to an x such that Ax = b.
Q6.b (20%)
Give an example of a 2× 2 singular matrix A and b ∈ range(A) such that GMRES does not converge to an x
such that Ax = b.
Q6.c (40%)
Suppose A is a normal matrix and b is not in range(A). Does GMRES converge? If so, what x does GMRES
converge to?
8

欢迎咨询51作业君