
\documentclass[11pt]{report}

\usepackage{../../StyleFiles/ksmac}
\usepackage{fancyhdr}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{../../StyleFiles/cprog}
\usepackage{../../StyleFiles/fullpage-old}
\usepackage{epsfig}
\usepackage{graphics}

\newcommand{\real}{\mathbb{R}}


\def\lectnumb{3}
%---------------------------------------------------------------------------

\shortrep

\lhead[{\bfseries 15-859N\quad HW \lectnumb}]{{\bfseries 15-859N\quad HW \lectnumb}}
\chead[]{}
\rhead[{\bfseries\thepage}]{{\bfseries\thepage}}
\lfoot[]{}
\cfoot[]{}
\rfoot[]{}

\pagestyle{fancy}

\parskip 1ex
\parindent 0mm

\renewcommand{\arraystretch}{1.5}
\def\titledquestion#1#2{\section{Problem: {#1} ({#2} pts.)}}

%----------------------------------------------------------------------


%-----------Danny's Macros-------------

\newcommand{\problem}[1]{\section{#1}\vspace{-1em}}
\newcounter{partnumber}
\newenvironment{parts}{\begin{list}{
%     \arabic{problemnumber}\alph{partnumber}:}{
     (\alph{partnumber})}{
     \usecounter{partnumber} \setlength{\rightmargin}{\leftmargin}}
     \setlength{\itemsep}{.0 in}}{
     \end{list} \vspace*{.0 in}}

\newenvironment{mylist}[1]{
\setbox1=\hbox{#1}
\begin{list}{}{
\setlength{\labelwidth}{\wd1}
\setlength{\leftmargin}{\wd1}
  \addtolength{\leftmargin}{1em}
  \addtolength{\leftmargin}{\labelsep}
\setlength{\rightmargin}{1em}}}{\end{list}}

\newcommand{\litem}[1]{\item[#1\hfill]}
\newcommand{\ritem}[1]{\item[#1]}

\newcommand{\comment}[1]{}
%---------------------------------------

\begin{document}


\framebox{
\begin{minipage}[t]{\textwidth}
\vspace{1ex}

\begin{center}
{\LARGE\bf  15-859N --- Spectral Graph Theory \\ and Scientific Computing  ---  Fall 2005}\newline
{\large\bf Miller

\vspace{2ex}

Assignment 3 \vspace{1ex}
Due date: December 8 2005.\\
}
\end{center}

\end{minipage}
}%% end framebox

\begin{problem}{Lanczos algorithm}

\begin{enumerate}
\item Show that running Lanczos algorithm on $A$ with starting vector $q$, produces identical
tridiagonal matrix as running the algorithm on $Q^TAQ$, with starting vector $Q^Tq$, where $Q$ is
a unitary matrix.

\item Let ${\cal K}_n = span(b,Ab,\ldots,A^{n-1}b)$. Show that the approximation $\xi_n(A)$ of the
maximum eigenvalue of $A$ returned after $n$ steps of Lanczos' algorithm, satisfies
$$\xi_n(A) = \max_{x \in {\cal K}_n} \frac{x^T A x}{x^Tx}$$
\end{enumerate}

Assume that the algorithm uses exact arithmetic and ${\cal K}_n$ is of
rank $n$. There are many different interpretations of Lanczos'
algorithm. For the second part of this problem assume that Lanczos
returns  $\xi_n(A)$ the largest Ritz value.



\end{problem}

\begin{problem}{Singular value decomposition (SVD)}
The singular value decomposition theorem states that every matrix $A$, can be written as $A = U
\Sigma V$, where $U,V$ are unitary matrices, and $\Sigma$ is a diagonal matrix. The singular values
of $A$, are the entries of $\Sigma$. The columns of $V,U$ are called the right and left singular
vectors respectively. Let $\sigma_1\leq \ldots\leq  \sigma_n$ denote the singular values.
\begin{enumerate}
 \item Show that the singular values are non-negative.
 \item Show that $\max_x {||Ax||/||x||} = \sigma_n$. In other words, the maximum singular value
 measures the maximum amount by which $A$ 'stretches' any vector.
 \item Show that $\min_x{||Ax ||/||x||}  = \sigma_1$. Conclude that $\sigma_1=0$ if and only if $A$
 has rank smaller than $n$.  Generalize this, by proving that the
 rank of $A$ is equal to the number of strictly positive singular values of $A$.
 As an interesting fact, you
 should know that
 $$
    \sigma_{1}(A) = \min_{E} \{ \sigma_1(E) , ~~s.t. ~~ \sigma_1(A+E)=0 \}
 $$
 \item Assume you have an algorithm for computing the eigenvalues and eigenvectors of symmetric matrices.
 Show how to use it to compute the singular value decomposition.
\end{enumerate}

\end{problem}

\begin{problem} {Preconditioning}
  We have seen in class that the running time of iterative algorithms for solving  the system $A x=
  b$ depends on the condition number $\kappa(A) = \lambda_{\max}(A) / \lambda_{\min} (A)$.
  Let $B$, the {\em  preconditioner},
  be any matrix whose null space is contained in the null space of  $A$.
  The preconditioned system $B^{-1} A x = B^{-1} b$, has the same solution with the
  original system. Observe that  the convergence rate of the new system is characterized by
    $\kappa(A,B)= \lambda_{\max}(B^{-1}A) / \lambda_{\min} (B^{-1}A)$. Thus, the choice of a good preconditioner can
    potentially speed up the solution of the system.
  \begin{enumerate}
    \item  To exploit the existence of a good preconditioner $B$, show that even if $B^{-1}$ is not
    directly available,
    it is enough to have a way of solving the system $B y  = z$  relatively fast.
    \item Let $A$ be the Laplacian of an $n$-vertex graph whose Cheeger number is a constant. Find
    an easily invertible, asymptotically optimal preconditioner for $A$.
    Show an example where your preconditioner gives a condition
    number $\kappa(A,B)$ linearly smaller than  $\kappa(A)$.
  \end{enumerate}



\end{problem}




\end{document}
