Numerical Linear Algebra, Math 4267, Homework # 6 Due April 14, 1999

(1) Let A = .

(a) Compute the first SHIFT.

(b) Find the shifted matrix. Call it .

(c) Find P2 in the equation = P2 so that the (2,1) entry of is 0.

(d) Find P3 in the equation R1 = P3.

(e) Compute Q1 = (P3P2)t.

(f) Let A(2) = R1Q1. Then find the approximation of eigenvalues of A.





(2)

Find the exact eigenvalues of the matrix A =

Go to the web and download the following Matlab files from ftp://www.etsu.edu/kerleyl/nla.

Matrix1

Matrix6

Hessenbe.m

Househol.m

QR_facto.m

QR_eig.m

Run Matrix6. Enter command who. You will see the variables are the matrices M1-M6.

(3) Use paper and pencil to complete this part.

As in the problem in the first example from handout 4-5-99 on page 2, find the Householder transformation matrix (Call it H1) so that H1*M1 has zeros in the first column below the subdiagonal.

Compute by hand H1*M1.

Then proceed as in the second example on page 2 of handout to find H2 so that H2*H1*M1 has zeros in the second column below the subdiagonal.

Compute by hand H2*H1*M1. Call the product R.

Compute by hand H1*H2. Call the product Q.

Note that the inverse of H2*H1 is H1*H2 since H1 and H2 are Householder matrices.

Compute by hand R*Q.

Compute by hand Q*R.

Now M1 is similar to R*Q. Also note that M1=Q*R. That is, we have factored M1 as a product of an orthogonal matrix Q and an upper triangular matrix R. Of course, Q*R does not equal R*Q.


(4) We now repeat (3) but solely use Matlab. Compute with the commands:

% Use following commands

[Q,R]=QR_factor(M1);

Q

R

Q*R

R*Q

% Done with commands

(5) Rather than using only one iteration as used in (3) or (4), we will perform 18 iterations. This is achieved using the command:

B=QR_eig(M1,18);

Find the eigenvalues of B (which is a Heissenberg matrix) by solving 0=det(A-lambda*I) for all lambdas by hand.

Now use Matlab command eig(M1). Contrast last two results.

(6) By applying the QR algorithm to a matrix A, we generate a sequence of matrices Am that are

orthogonally similar to A. The sequence Am converges to a matrix for which the eigenvalues can be found easily.

(a.) If the eigenvalues are all different (even if original matrix is not similar), the iterates converge to a triangular matrix with eigenvalues on the diagonal.

(b.) If the original matrix in similar, the iterates will converge to a block diagonal matrix in which all blocks have order 1 or 2.

(c.) In fact, any symmetric matrix with real entries will converge to a diagonal matrix.


Run Martix6

Type command who. The name of matrices will appear. They are M1-M6. You will only need M1-M4.

Provide a written discussion of matrices M1-M4 (with supporting hardcopy from Matlab). In your discussion, indicate whether the matrix is symmetric. Apply QR_eig(M1, max) for max = 10 and max = 20. Discuss in light of a and b above. Repeat for M2, M3, and M4 except use 10 and 13 for M4 .

In addition, for M4, for B= QR_eig(M4,13) , decompose B into a block of size 1 and a block of size 2. Proceed as discussed on p 582 where b3 =0.030396964 determined the 2 blocks which were used. Use the criterion that a certain element be less than 0.03 in determining the appropriate split of B. Then find via paper and pencil from the 2 blocks all 3 eigenvalues. Two eigenvalues are determined by the quadratic formula using a 2x2 submatrix of B and the third one is determined by inspection.