Mathematics 372 – Numerical Linear Algebra Final Problem Set April 30, 2007, due: 5:00pm on May 9, 2007

General Information and Ground Rules

This is an open-book, open notes, open Swords 335 assignment. You must work independently on these problems, and you may not consult with other faculty members or students. You may consult other books, sources in the library, or information from the Internet, but if you find something relevant, you should footnote it for proper acknowledgment of sources. When you have finished your solutions, please write out a short statement that you have abided by these ground rules, sign it, and hand it in with your work.

I. Some additional properties of matrix norms. Recall that from Theorem 4.2.1 in Watkins, using the SVD, we know ∥A∥_{2} = σ_{1}, the largest singular value of A. This gives additional properties and estimates for the matrix 2-norm.

A) (10) On the midterm problem set, recall that we showed

∥A∥_{F} ≤ \sqrt{n} · ∥A∥_{2}

for all n × n matrices. Show the following more general and sharper form of this inequality: For all A ∈ M_{n×m}(R),

∥A∥_{F} ≤ \sqrt{rank(A)} · ∥A∥_{2}.

B) (10) Show that for all matrices A ∈ M_{n×m}(R),

∥A∥_{2} ≤ \sqrt{∥A∥_{1}∥A∥_{∞}}

(this is sometimes useful for estimating ∥A∥_{2} without computing it exactly). (Hints: How are singular values of A related to eigenvalues of A^{t}A? What happens if you apply the 1-norm to an equation A^{t}Az = λz?)

C) (10) Show using MATLAB that the inequalities in parts A and B are satisfied for the matrix B − I_{60}, where B is the 60 × 60 bucky matrix.

II. More on condition numbers. Let n > m. Recall that if A ∈ M_{n×m}(R), the condition number κ_{2}(A) = σ_{1}/σ_{m} measures the susceptibility of the least-squares solution of Ax = b to round-off errors.

A) (10) Show that if an additional column y ∈ R^{n} is appended to A, to yield

\overline{A} = ( A y) ∈ M_{n×(m+1)}(R),

then

σ_{1} (\overline{A}) ≥ σ_{1} (A) and σ_{m+1} (\overline{A}) ≤ σ_{m} (A) .

What does this say about κ_{2}(\overline{A}) vs. κ_{2}(A)?

B) (10) Show that if an additional row, w^{t} for w ∈ R^{m}, is appended to A to yield

\overline{A} = ( \begin{matrix}A \\ w^{t} \end{matrix} ) ∈ M_{(n+1)×m}(R),

then

σ_{1} (\overline{A}) ≤ \sqrt{σ_{1}(A)^{2} + ∥w∥_{2}^{2}} and σ_{m} (\overline{A}) ≥ σ_{m} (A) .

What does this say about κ_{2}(\overline{A}) vs. κ_{2}(A)?

III. An image-processing application of the SVD. A large, detailed, image stored as a matrix of gray-scale pixel values can take a large amount of storage space. If the information contained in such an image can be compressed without losing too much image quality, that is a good thing for transmission and storage. One possible method for image compression is based on the the theoretical result on SVD’s in part A below. The later parts will show you how this works in practice.

A) (10) Recall from Theorem 4.1.12 (Exercise 4.1.13) in Watkins that if A = UΣV^{t} is an SVD of A, then if A has rank r,

(∗)  A = ∑_{j=1}^{r} σ_{j}u_{j}v_{j}^{t},

where u_{j} and v_{j} are the columns of the U and V matrices respectively, and σ_{1} ≥ σ_{2} ≥ ⋯ ≥ σ_{r} > 0 as usual. If we keep only the largest k singular values for some k < r, then the resulting matrix

(∗∗)  A_{k} = ∑_{j=1}^{k} σ_{j}u_{j}v_{j}^{t},

can be thought of as a rank k approximation to A (this makes especially good sense if the omitted singular values σ_{k+1}, …, σ_{r} are “small” compared to the others). Prove that:

(1) ∥A − A_{k}∥_{2} = σ_{k+1}, and

(2) if A′ is any other matrix of rank ≤ k, then

∥A − A′∥_{2} ≥ ∥A − A_{k}∥_{2}.

In words, A_{k} is the closest matrix to A among all matrices of rank k or less. Hint: For part (2), show that

N (A′) ∩ Span{v_{1}, …, v_{k+1}} ≠ {0}

and see what A − A′ does to a unit vector in the intersection.

B) (5) One measure of the size of an image A is the total number of real numbers needed to write the vectors u_{j}, v_{j} and the σ_{j} in (*) or (**). If A is 200 × 320 and has rank 200, what is the

compression ratio = \frac{size using (∗∗)}{size using (∗)}

achieved if we replace the original expression (*) for A with (**), using k = 5, 10, 20, 25?

C) (10) Using MATLAB, test out this compression scheme using the image file clown.mat:

load clown.mat;
colormap('gray');

This will store the image file as a 200 × 320 full matrix called X. You can display the full image using

image(X)

Now, compute the SVD of X calling the factors U, S, V. To compute the “compressed” matrices A_{k} for various k, you can use commands like this:

U(:,1:k)*S(1:k,1:k)*V(:,1:k)'

(you supply the values of k). Note: the MATLAB syntax A(:, a : b) means: form the submatrix of A taking all rows and columns a through b.) For k = 5, 10, 20, 25, compute A_{k}, display the resulting images, and comment on how well they represent the full image (k = 200). As a more precise measure of image quality, also compute ∥A − A_{k}∥_{2} for each of these k values.

IV. More on iterative methods. Recall that the Jacobi and Gauss-Seidel iterative methods for square systems Ax = b can be derived by splitting the coefficient matrix A as a sum. The general idea would be to write A = M + N for some square matrices M, N with M invertible.

A) (5) Show that however this is done, the resulting iteration can be written as a correction based on the residual r^{(k)} = b − Ax^{(k)}:

x^{(k+1)} = x^{(k)} + M^{−1}r^{(k)}.

B) (5) For the remainder of this problem, assume that all eigenvalues of A are real and non-negative. The method obtained with M = \frac{1}{ω} I for some ω > 0 and N = A − M is called Richardson’s method. Richardson’s method iteration in the fixed point form is

x^{(k+1)} = (I − ωA)x^{(k)} + ωb.

Show that Richardson iteration converges only for ω < \frac{2}{λ_{max}}, where λ_{max} is the largest eigenvalue of A.

C) (10) Show that the omega that minimizes the spectral radius of the “Richardson

G-matrix” I − ωA is

ω_{opt} = \frac{2}{λ_{max} + λ_{min}} ,

where “opt” stands for “optimal – explain why this would be the best value of ω to use.

D) (5) Refer to the system from Example 7.2.3 in the text. Using MATLAB, determine ω_{opt} for Richardson on this system, and determine the number of Richardson iterations needed to yield a solution that is accurate to 8 decimal places using ω = .17, ω_{opt}, and ω = .1.

Have an enjoyable and productive summer, and congratulations to our graduating seniors!