\magnification=\magstep1
\centerline{Mathematics 372 -- Numerical Linear Algebra}
\centerline{Midterm Problem Set}
\centerline{March 16, 2007, {\it due}: March 23, 2007}
\bigskip
\noindent
{\it General Information and Ground Rules}
\bigskip
This is an open-book, open notes, open Swords 335 assignment.
You must work {\it 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 
{\it 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.
\bigskip
\noindent
I.  (More on Gaussian elimination and $LU$ factorizations).
\bigskip
\item{A)}  (10) Show that an $n\times n$ matrix $A$ has an $LU$ 
factorization (equivalently, Gaussian elimination is possible
with no row interchanges) if and only if for each $1\le k \le n$,
the upper left corner $k\times k$ submatrix 
$$A_k = \pmatrix{a_{11} & \cdots & a_{1k}\cr
                \vdots & & \vdots\cr
                 a_{k1} & \cdots & a_{kk}\cr}$$
is nonsingular.  
\bigskip
\item{B)}  (10) Suppose that $A$ is a matrix that satisfies the 
condition in part A, and for any $k$, $1 \le k \le n$, partition $A$ as 
$$A = \pmatrix{A_k & B\cr
                C  & D\cr},$$
where $B$ is $k \times (n-k)$, $C$ is $(n-k) \times k$, and $D$
is $(n-k) \times (n - k)$.
Show that there is a unique $(n-k) \times k$ matrix $M$
such that 
$$\pmatrix{I_k & 0\cr
           -M  & I_{n-k}\cr} \pmatrix{A_k & B\cr
                                       C  & D\cr} = \pmatrix{A_k & \hat{B}\cr
                                                              0  & \hat{D}\cr}$$
for some matrices $\hat{B}$ and $\hat{D}$.
Also show that $\hat{D} = D - C A_k^{-1} B$.  
\bigskip
\item{C)} (5) Deduce that $A$ has the {\it block LU decomposition}
$$A = \pmatrix{I_k & 0\cr
                M  & I_{n-k}\cr} \pmatrix{A_k & \hat{B}\cr
                                           0  & \hat{D}\cr}.$$
\item{D)} (5) By definition, the matrix $A_k$ satisfies the condition in part A.
It can be shown that $\hat{D}$ does as well.  Hence each of these
matrices also has an $LU$-decomposition:
$A_k = L_1U_1$, and $\hat{D} = L_2U_2$.
Express the $LU$-decomposition of $A$ in terms of $L_1,L_2,M,U_1,U_2,$ and
$B$.    
\bigskip
\noindent
II.  (The matrix $2$-norm, revisited.) By the general theory of the matrix 
operator norms associated to vector norms on ${\bf R}^n$, 
the matrix $2$-norm of $A \in M_{n\times n}({\bf R})$ is
given by 
$$\|A\|_2 = \max_{\|u\|_2 = 1} \|Au\|_2.\leqno(1)$$
Your goal in this problem is to prove the formula
$$\|A\|_2 = \sqrt{\max \{|\lambda| : 
\lambda {\rm\ is\ an\ eigenvalue\ of\ } A^tA\}}\leqno(2)$$
that we mentioned in class.  The equation (1) shows that we need
to solve a {\it constrained optimization problem} to determine
$\|A\|_2$.
\bigskip
\item{A)} (5) What standard method from multivariable calculus
applies to solve constrained optimization problems of the
following form:
$$\eqalign{
{\rm maximize:}\ &f(x_1,\ldots,x_n)\cr
{\rm subject\ to:}\ &g(x_1, \ldots, x_n) = 0?\cr
}$$
Describe how the method works in general.  
\bigskip
\item{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,\ldots,u_n)^t$,
apply the method with $f(u_1,\ldots,u_n) = \|Au\|_2^2$
and $g(u_1,\ldots,u_n) = u_1^2 + \cdots + 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^tA$, 
and that the multiplier $\lambda$ in the method
must be the corresponding eigenvalue.  
\bigskip
\item{C)} (5) Deduce that (2) holds, giving the formula
for $\|A\|_2$.
\bigskip
\item{D)}  (10) Recall the $60 \times 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 {\tt eig} returns a list of all
the eigenvalues of a square matrix; (b) the built-in matrix
{\tt bucky} is a sparse matrix.  If you want to check your
answer using the {\tt norm} command, you will need to convert {\tt bucky}
to ``full'' form. 
\bigskip
\item{E)} (10) If $A = (a_{ij})$, the matrix Frobenius norm is
defined by 
$$\|A\|_F = \sqrt{\sum_{i=1}^n \sum_{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$
$$\|A\|_2 \le \|A\|_F \le \sqrt{n} \|A\|_2\leqno(3)$$
\bigskip
\item{F)} (5) Compute the Frobenius norm of the bucky ball matrix $B$ using
MATLAB and verify that (3) holds in this case.
\bigskip
\noindent
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
\bigskip
$$\matrix{x_i & 1.001 & 1.002 & 1.003 & 1.004 & 1.005 & 1.006 & 1.007 \cr
          y_i & 3.664 & 3.789 & 3.891 & 4.022 & 4.233 & 5.200 & 5.329 \cr}$$
by solving the normal equations $X^tX \pmatrix{m \cr b\cr} = X^tY$
for the least squares problem.
\bigskip
\item{A)} (5) Using MATLAB, find the $\infty$-norm condition number of the 
coefficient matrix $X^tX$ in the system of normal equations.  What does your 
answer indicate about this system of equations?
\bigskip
\item{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 $\infty$-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.  
\bigskip
\item{C)} (5) Explain your results in A and B geometrically.
\bye
