Generate Random Matrices with Specified Eigenvalues — (a) (5 pts) Generate a random symmetric matrix, with eigenvalues {1, 2,…,N}. Use the similarity relation A = QQú where Q is a random unitary (N ◊ N) matrix, and a diagonal matrix with the eigenvalues on the diagonal. VERIFY, using a library call (Matlab / Python / R / ???) that your matrices indeed have the desired eigenvalues. SUBMIT: Code, and verification (output) for N = 20. (b) (5 pts) Generate a random non-symmetric matrix, with eigenvalues {1, 2,…,N}. Use the similarity relation A = QT Qú where Q is a random unitary (N ◊N) matrix, and T a triangular matrix with the eigenvalues on the diagonal, and non-zeros in the upper triangular part. VERIFY, using a library call (Matlab / Python / R / ???) that your matrices indeed have the desired eigenvalues. SUBMIT: Code, and verification (output) for N = 20.
Transform the Matrix into a more Convenient Form for Iterations (a) (5 pts) Transform A into upper Hessenberg form; you may use a library call, or code from previous homework. VERIFY the form by plotting the elements that are greater in magnitude than tolerance; use e.g. the Matlab spy, or the python matplotlib.pyplot.spy commands1. SUBMIT: Code, and verification (output) for N = 20. 1R does not(?) have a spy command, but you can use the image command to achieve the same thing 2
Find ALL the Eigenvalues Using the QR-Algorithm with Wilkinson Shifts • Stage#1 — Implement the QR-Algorithm (for the QR-factorization: you may use a library call, or code from previous homework) with Wilkinson Shifts so that it finds one eigenvalue. Stop when the change in the eigenvalue estimate is less than tolerance in magnitude between iterations. • Stage#2 — No fancy deflation needed (this is a proof-of-concept, not an optimized code). Once an eigenvalue is identified; remove the last row and column from the matrix. • Stage#3 — Repeat the process until the remaining matrix is of size (1 ◊ 1). (a) (40 pts) Generate, and SUBMIT Code, and the following output: for each use of Stage#1 — the final eigenvalue estimate; the number of QR-algorithm iterations needed to find the estimate; and the cumulative number of QR-algorithm iterations. A total of (N-1) lines of output; and the final eigenvalue estimate — the (1 ◊ 1) leftover matrix.
Summarize the Eigenvalue Estimates, with Relative Errors (a) (5 pts) Sort the eigenvalue estimates in ascending order (from small to large), SUBMIT: Code, and a table containing (line-by-line): (1) each eigenvalue estimate; and (2) the relative error of the estimate. SHOW all available digits (usually 15–16).
Use Inverse Iteration to Find Eigenvectors • For the 5 eigenvalue estimates with LARGEST (in magnitude) relative errors: Perform ONE step of Inverse Iteration (with a randomly generated vector as starting point) to get an eigenvector estimate. You may use a library call to solve the linear system in the inverse iteration. • Compute the Rayleigh Quotient for the eigenvector estimate. (a) (40 pts) SUBMIT: Code, and a table where each row contains (1) The selected eigenvalue estimate; (2) the Rayleigh Quotient; and (3) the relative dierence of the two. For FULL CREDIT you must perform all the actions on a (20 ◊ 20) symmetric, and a (20 ◊ 20) non-symmetric matrix. If you cannot get problem 3 to work, you can still get credit on Problem 5 — Select 5 eigenvalues, and perturb them individually by 10≠6*randn(1); use these perturbed eigenvalues as starting estimates.