Mathematics 372 – Numerical Linear Algebra Midterm Problem Set March 16, 2007, due: March 23, 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. (More on Gaussian elimination and LU factorizations).

A) (10) Show that an n × n matrix A has an LU factorization (equivalently, Gaussian elimination is possible with no row interchanges) if and only if for each 1 ≤ k ≤ n, the upper left corner k × k submatrix

A_{k} = ( \begin{matrix}a_{11} & ⋯ & a_{1k} \\ ⋮ & & ⋮ \\ a_{k1} & ⋯ & a_{kk} \end{matrix} )

is nonsingular.

B) (10) Suppose that A is a matrix that satisfies the condition in part A, and for any k, 1 ≤ k ≤ n, partition A as

A = ( \begin{matrix}A_{k} & B \\ C & D \end{matrix} ) ,

where B is k × (n − k), C is (n − k) × k, and D is (n − k) × (n − k). Show that there is a unique (n − k) × k matrix M such that

( \begin{matrix}I_{k} & 0 \\ −M & I_{n−k} \end{matrix} ) ( \begin{matrix}A_{k} & B \\ C & D \end{matrix} ) = ( \begin{matrix}A_{k} & B̂ \\ 0 & D̂ \end{matrix} )

for some matrices B̂ and D̂. Also show that D̂ = D − CA_{k}^{−1}B.

C) (5) Deduce that A has the block LU decomposition

A = ( \begin{matrix}I_{k} & 0 \\ M & I_{n−k} \end{matrix} ) ( \begin{matrix}A_{k} & B̂ \\ 0 & D̂ \end{matrix} ) .

D) (5) By definition, the matrix A_{k} satisfies the condition in part A. It can be shown that D̂ does as well. Hence each of these matrices also has an LU-decomposition:

A_{k} = L_{1}U_{1}, and D̂ = L_{2}U_{2}. Express the LU-decomposition of A in terms of L_{1}, L_{2}, M, U_{1}, U_{2}, and B.

II. (The matrix 2-norm, revisited.) By the general theory of the matrix operator norms associated to vector norms on R^{n}, the matrix 2-norm of A ∈ M_{n×n}(R) is given by

(1)  ∥A∥_{2} = max_{∥u∥_{2}=1} ∥Au∥_{2}.

Your goal in this problem is to prove the formula

(2)  ∥A∥_{2} = \sqrt{max\{|λ| : λ is an eigenvalue of A^{t}A\}}

that we mentioned in class. The equation (1) shows that we need to solve a constrained optimization problem to determine ∥A∥_{2}.

A) (5) What standard method from multivariable calculus applies to solve constrained optimization problems of the following form:

maximize : f(x_{1}, …, x_{n})
subject to : g(x_{1}, …, x_{n}) = 0?

Describe how the method works in general.

B) (15) For our purposes in (1), it will be most convenient to square both the function ∥Au∥_{2} we seek to maximize and the constraint equation ∥u∥_{2} = 1. Writing u = (u_{1}, …, u_{n})^{t}, apply the method with f(u_{1}, …, u_{n}) = ∥Au∥_{2}^{2} and g(u_{1}, …, u_{n}) = u_{1}^{2} + ⋯ + u_{n}^{2} − 1. Show that the equations for the constrained maximum imply that the vector u where f achieves its maximum must be an eigenvector of A^{t}A, and that the multiplier λ in the method must be the corresponding eigenvalue.

C) (5) Deduce that (2) holds, giving the formula for ∥A∥_{2}.

D) (10) Recall the 60 × 60 adjacency matrix B of the “bucky ball” from Lab/Problem Set 3. Use (2) above and MATLAB to compute ∥B∥_{2}. Some technical notes: (a) The MATLAB command eig returns a list of all the eigenvalues of a square matrix; (b) the built-in matrix bucky is a sparse matrix. If you want to check your answer using the norm command, you will need to convert bucky to “full” form.

E) (10) If A = (a_{ij}), the matrix Frobenius norm is defined by

∥A∥_{F} = \sqrt{∑_{i=1}^{n} ∑_{j=1}^{n} |a_{ij}|^{2}}

(note: the absolute values here are unnecessary for real matrices, but necessary if some of the entries in A are complex numbers with nonzero imaginary parts). Show that for all matrices A

(3)  ∥A∥_{2} ≤ ∥A∥_{F} ≤ \sqrt{n}∥A∥_{2}

F) (5) Compute the Frobenius norm of the bucky ball matrix B using MATLAB and verify that (3) holds in this case.

III. (Roundoff considerations and least squares.) In many situations, the way a problem is set up can have a significant effect on the susceptibility to roundoff errors when we apply standard methods. But fortunately, there are often ways to minimize those effects. For instance, suppose that we want to compute the best-fit line for the following data points

\begin{matrix}x_{i} & 1.001 & 1.002 & 1.003 & 1.004 & 1.005 & 1.006 & 1.007 \\ y_{i} & 3.664 & 3.789 & 3.891 & 4.022 & 4.233 & 5.200 & 5.329 \end{matrix}

by solving the normal equations X^{t}X ( \begin{matrix}m \\ b \end{matrix} ) = X^{t}Y for the least squares problem.

A) (5) Using MATLAB, find the ∞-norm condition number of the coefficient matrix X^{t}X in the system of normal equations. What does your answer indicate about this system of equations?

B) (10) Our standard way of setting up the normal equations corresponds to using the basis {x, 1} for the vector space of linear polynomials. But we could use any other basis we like too. Suppose we use {300(x − 1.004), 1} instead (that is, translate and rescale the x_{i} values). What is the ∞-norm condition number of the coefficient matrix in the normal equations now? Show that the best-fit line can still be computed if we set the problem up this way.

C) (5) Explain your results in A and B geometrically.