MATH6800/CSCI6800 Computational Linear Algebra

Final Exam, Fall 2000

Take Home Due: 5pm, Thursday, December 14, 2000.

This is to be all your own work. You may use any result from class, homeworks, the textbook, the course website and files linked directly to it, the books on reserve in the library, and the textbook website. You can look at the MATLAB and conjugate gradient information linked from the course webpage. Do not consult anybody or anything else. I can dispense hints to help you if you are stuck. My email address is mitchj@rpi.edu and my phone number is 276-6915. I'll have my regular office hours today from 4pm to 6pm; I'll also have office hours next Monday and Wednesday, between 2pm and 4pm.

In order that I can display grades, please write a 4 digit number on the front of your solution set.

Here is a brief discussion of four digit codes.

1.

(15 points) Let P be an n x n symmetric matrix satisfying PP=P. Examples include the identity matrix and the matrix

$$A := \left[ \begin{array}{cc} 1 & 0 \\ 0 & 0 \end{array} \right].$$

(a)

(5 points) Show that P is positive semidefinite. (Recall that a matrix is positive semidefinite if $x^TPx \geq 0$ for all n-vectors x.)

(b)

(10 points) What are the singular values of P?

2.

(15 points) Let S and T be n x n upper triangular matrices. Let $\lambda$ be a given scalar. Assume $ST-\lambda I$ is nonsingular. Show that the system of equations $(ST-\lambda I)x=b$ can be solved in O(n²) floating point operations.

(Note that it costs O(n^3) to form the product ST explicitly. Therefore, you need to give a method that doesn't require forming this product. You can assume that all computations can be performed in exact arithmetic for this question. )

3.

(15+10 points) Let the n x n symmetric matrices A and H commute, so AH=HA.

(a)

(15 points) Assume the eigenvalues of A are distinct. Show that there exists an orthogonal matrix Q such that Q^TAQ and Q^THQ are both diagonal. (Thus, the columns of Q are the eigenvectors of both A and H.)

(b)

(Extra credit: 10 points) Show that even if the eigenvalues of A are not distinct, there still exists an orthogonal matrix Q such that Q^TAQ and Q^THQ are both diagonal.

4.

(15 points) Consider the least squares problem $\min \vert\vert Ax-b\vert\vert _2$, where A is m x n, b is an m-vector, m>n, and A has rank n. In this question, we are going to start constructing a Lanczos scheme for solving this problem. We want to find an m x m orthogonal matrix U and an n x n orthogonal matrix V so that the product U^TAV has the bidiagonal form B:

$$U^TAV = B := \left[ \begin{array}{ccccc} \alpha_1 & 0 & \ldo... ...& \beta_n \\ \hline \multicolumn{5}{c}{0} \end{array} \right]$$

Let u_k denote the kth column of U and v_k denote the kth column of V.

(a)

(5 points) Show that the columns of U and V satisfy the following identities for $k=1,\ldots,n$, where $\beta_0:=0$ and v₀:=0:

$$\begin{eqnarray*} A^Tu_k &=& \beta_{k-1}v_{k-1} + \alpha_k v_k \\ Av_k &=& \alpha_k u_k + \beta_k u_{k+1}. \end{eqnarray*}$$

(b)

(10 points) Develop a Lanczos-type recursion from these equations to find U and V.

5.

(40 points) Let A be a positive definite symmetric n x n matrix and let b be an n-vector. An alternative iterative approach to find the solution to the system Ax=b is the steepest descent method. This can be described as follows:

Initialize:

x₀=0, r₁=b, k=0.

Main loop:

    
Repeat:

(a)

$\alpha_k=\frac{r_k^TAr_k}{r_k^TAAr_k}$

(b)

$x_{k+1}=x_k+\alpha_kr_k$

(c)

r_k+1=b-Ax_k+1

(d)

k=k+1

until ||r_k||₂ small enough

(For all the requested plots, you can use a standard plot and/or a semilog plot, as appropriate.)

(a)

(5 points) Given a point x_k and a residual b-Ax_k, show that the choice of $\alpha$ given in the algorithm is the one that minimizes the norm of the residual over all points of the form $x_k+\alpha r_k$.

(b)

Let A be the 100 x 100 tridiagonal matrix with the ith diagonal entry being i and the sub- and superdiagonal entries all equal to one. Let b be the vector of all ones.

i.

(15 points) Implement the steepest descent method. Run it for 100 iterations to try to find the solution to Ax=b. Plot the norms of the residuals produced by the algorithm.

ii.

(15 points) Implement the conjugate gradient algorithm. Run it for 100 iterations to try to find the solution to Ax=b. Plot the norms of the residuals b-Ax_k produced by the algorithm and the norms of the residuals r_k produced by the algorithm. (Recall that the algorithm does not calculate r_k exactly but updates it using r_k-1 and z.) Is the residual decreasing monotonically? Is there a related quantity that is decreasing monotonically?

iii.

(5 points) What do you conclude?