MATH6800/CSCI6800 Computational Linear Algebra

Homework 5.

Due: Monday, December 4, 2000.

1.

Demmel, Question 5.13. Hint: Use the arguments on page 161. Relate the sequence of Q matrices to the sequence of x vectors; for example, relate the last column of Q₀ to x₁. Use Lemma 4.4 on page 161 and also the relationship immediately after the lemma. Note that a_nn refers to the (n,n) position of A_i. Note that QR Iteration initializes with A₀=A.

2.

Demmel, Question 5.16.

3.

(a)

Let $A \in I \! \! R^{m \times m}$ be a tridiagonal symmetric matrix, with all its sub- and superdiagonal elements nonzero. Show that the eigenvalues of A are distinct. (Hint: Show that for any $\lambda$, $A-\lambda I$ has rank at least m-1.)

(b)

Let A be upper-Hessenberg, with all its subdiagonal entries nonzero. Give an example that shows that the eigenvalues of A are not necessarily distinct.

4.

Use bisection to find the number of eigenvalues of the following matrix A in the interval [1,2), using recurrence (5.17):

$$A := \left[ \begin{array}{cccc} 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 \\ 0 & 1 & 2 & 1 \\ 0 & 0 & 1 & 3 \end{array} \right]$$

5.

(Programming.) Construct a random real symmetric tridiagonal matrix T of dimension 100 and compute its eigendecomposition T=QDQ^T. (You can use the MATLAB command eig(T) to find the eigendecomposition.) What proportion of the 10,000 entries of Q are greater than 10^-10 in magnitude? What is the answer if you take T to be the discrete Laplacian with diagonal entries -2 and sub- and superdiagonal entries 1? (This is an example of the phenomenon of localization. You may find it of interest to plot some of the columns of Q on a semilogy scale.)

I will pass out the final exam on Thursday, December 7. It will be due on Thursday, December 14.

	John Mitchell
	Amos Eaton 325
	x6915.
	mitchj@rpi.edu
	Office hours:
	Monday: 12.30pm - 1.30pm. Thursday: 4pm - 6pm.