MATH 449: FINAL EXAM
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
MATH 449: FINAL EXAM
F.1 (10 pts) Find all the eigenvalues and eigenvectors of the rotation matrix
R(pq)(ϕ). Can each rotation matrix be expressed in the form of a Householder matrix H = I . 2vvT \(vT v) with non-zero v e Rn×1? If yes, show that this can be done for any rotation matrix. If not, show that this cannot be done.
F.2 (25 pts) Consider the QR algorithm for A e Rn ×n ,
where we choose µk := [A(k)1(n-1)n .
(a) [I] Implement the algorithm and apply it to the symmetric matrix
|
． ．
． ． ． ． ． ' |
1 4 1 |
1 4 . . . |
1 . . . 1 |
. . . 4 1 |
1 4 1 |
for sizes n = 32, 64, 128.
┐
．
．
．
．
(b) Plot the eigenvalues for each n above and find an explicit expression for the eigenvalues. [Hint: try different trigonometric expressions]
(c) (Extra Credit ) Show that if A(k) is tri-diagonal, then there is a QR decomposition for which A(k＋1) in (1) is also tri-diagonal. [Hint: the proof we gave in the lectures had an error - find the correct proof]
F.3 (20 pts) The function H(x) is defined by
╱．1
．
H(x) = ．0
．
．
if x > 0,
if x = 0,
if x < 0.
(a) Construct the best polynomial approximation pn of degrees n = 0, 1, 2 in the induced norm | · |w := ( · , ·>w of H the interval [.1, 11 with weight function w(x) = 1.
(b) If you let n 二 o will pn converge to H in the induced norm? Either show that it converges or it does not.
F.4 (25 pts) Suppose we are given any matrix A e Rn ×n .
(a) Construct two orthogonal matrices U and V in the form
U = H(n-2)H(n-3) · · · H(1) ,
V = K(n-1)K(n-2) · · · K(1) ,
where H(k) , K(k) are Householder matrices that make B = UAVT bi- diagonal (tri-diagonal and lower-triangular).
(b) [I] Implement the construction above. For the matrix
_ 1 .1 .1 .1 .1 .1 ┐
．.1 1 1 1 1 .1．
． ．
．.1 1 .1 .1 .1 1．
A = ． ．
． ．
． 1 .1 1 .1 .1 .1．
' 1 1 .1 .1 1 .1'
compute the corresponding bi-diagonal matrix B = UAVT (as discussed in part (a)) and display the matrix B.
(c) [I] Implement the Jacobi’s method and approximately diagonalize the symmetric matrix BT B (b). Use the tolerance e =1e-3 for the off- diagonal entries. How many iterations are needed to satisfy this toler- ance? List the resulting diagonal entries of the final iteration.
(d) [I] Using only the outputs from the implementations above in (b-c), compute the induced 2-norm of A, as accurately as possible, and display the result.
2022-12-16