\documentclass[]{article}
\textwidth 6.4in
\textheight 9.0in
\oddsidemargin -0.3in
\evensidemargin -0.3in
\usepackage{latexsym}
\usepackage{multicol}
%\usepackage{epsfig}
\usepackage{latexsym}
 \usepackage{epsfrag}
\usepackage{multicol}
\usepackage{fancybox}

  \topmargin -.5in

\input{/afs/eos.ncsu.edu/users/z/zhilin/TEX/mystyle}
\def\be{\begin{enumerate}}
\def\ee{\end{enumerate}}
%\newcommand{\vthin}{\vskip 5pt}


\pagestyle{empty}
\begin{document}
\bc
\hfill\vbox{\hbox{MA/CSC 580, Homework \#5 }\hbox{
\bf Due Tuesday,  November  16, 2018}}
\ec

\vskip .2in
\baselineskip 14pt

\be

\item Let $A\in R^{n,n}$ be a square matrix. 
\be
\item Let  $(\lambda, {\bf x})$ be an
eigenpair of $A$. Show that $(\lambda^k,{\bf x})$ is an eigenpair of $A^k$
for any integer $k$. Can $k$ be negative or zero?

\item If  $A=A^H$ (the conjugate transpose of $A$ and so on) be a symmetric matrix, use the conclusion above to show the following
\eqmno
\|A\|_2 = \max_{1\le i \le n} |\lambda_i(A)|, \qquad \dsp
\|A^{-1} \|_2 = \fr{1}{\min_{1\le i \le n} |\lambda_i(A)|}, \qquad \dsp
cond_2(A) = \fr{ \max_{1\le i \le n} |\lambda_i(A)|} {\min_{1\le i\le n}
|\lambda_i(A)|}.
\enmno
\item  Also show that all eigenvalues of $A$ are real and eigenvectors corresponding to different eigenvalues are orthogonal. {\bf Hint:} Consider $ A x = \lambda_i x$, and
$y^H A^H = \bar{\lambda}_i y$, $y^h A x$ and $x^h A y$. 
\item If $A$ is a lower/upper triangular matrix, show that
$\lambda_i(A)=a_{ii}$, that is, the eigenvalues of $A$ are the diagonal
entries. Is such a matrix always diagonalizable?
\ee

\item Let $A\in R^{n,n}$ be the following matrix
\eqmno
  A = \left(%
 \begin{array}{ccccc}
  \lambda_{1} & 1  &   &  &  \\
   & \lambda_{2} & 1 &  &  \\
   &   & \ddots  & \ddots &  \\
   &   &   & \ddots & 1 \\
   &   &   &  & \lambda_{n} \\
\end{array}%
\right),
\enmno
Assume that $\lambda_i \neq \lambda_j$ if $i\neq j$. Find a similarity transform so that the  Gershgorin circles of the transformed matrix are separated.  {\bf Hint:} See the proof of the convergence of stationery iterative methods. 

\vthin
\item (a): Derive the Power method using $\|{\bf x}\|_1$ or $\|{\bf x}\|_{\infty}$  scaling and show its convergence under appropriate conditions. (b): Compare with different method for general  and symmetric matrices. You can write a Matlab code to test different methods; and then carry out some analysis. 


\ignore{
\item Assume that $\|R\|< 1$, show that the iterative method
$\mathbf{x}^{k+1} = R \mathbf{x}^{k} + \mathbf{c}$ has the error
estimate
\eqmno
\|\mathbf{x}^{k} - \mathbf{x}^{*}\| \le \fr{ \|R\|^k}{ 1 - \|R\|} \,
\| \mathbf{x}^{1} - \mathbf{x}^{0}\|,
\enmno
where $\mathbf{x}^{*} $ is the solution to $\mathbf{x} =
R \mathbf{x} + \mathbf{c}$.
Note that in this estimate, the true solution is not involved in the right
hand side. {\bf Hint:} First show that $\mathbf{x}^{k+1} -
\mathbf{x}^{k}
= R(\mathbf{x}^{k} - \mathbf{x}^{k-1} )=R^k (\mathbf{x}^{1} -
\mathbf{x}^{0} )$, and then $R \lp \mathbf{x}^{k} -
\mathbf{x}^{*} \rp
 -\lp  \mathbf{x}^{k} - \mathbf{x}^{*} \rp =R^k (\mathbf{x}^{1} -
\mathbf{x}^{0} )$. }


\vthin
\vthin
\item $\null$ \be
\item Use the Gershgorin's theorem to locate the intervals that contain the
eigenvalues of $A$
\eqmno
A = \left [\begin {array}{ccc}
0&1&1\\\noalign{\medskip}1&-6&0\\\noalign{\medskip}0&1&9\end {array}\right ].
\enmno
\item Can $A$ have complex eigenvalues? Why?
\item Is $A$  diagonalizable? Why?
\item Apply one step Power method using the 2-norm, and the $x_p$ notation.
\item Assume that eigenvalues $A$ satisfy
$|\lambda_1|>|\lambda_2|>|\lambda_3|$, apply one step {\bf \em shifted inverse
Power method} to approximate the
eigenvalue $\lambda_2$ and its eigenvector with initial guess
$\left [\begin {array}{ccc} 0&1&0\end {array}\right ]^T$.
\ee
 {\bf Hint:} You can use Matlb command  [l u p ]= lu(A)  to find $PA = LU$ decomposition.


\vthin


\item  $\null$
Let $\; x= \left [\begin {array}{cccc} 3&0&-1&2\end {array}\right ]^T,\;
$ and $\;y=\left [\begin {array}{cccc} -1&0&0&0\end {array}\right ] ^T$.
\be
\vthin
\item Is there a Householder matrix $P$ such that $\,Px=y?\;$ Explain.
\vthin
\item Let $\tilde{y}=\alf y,\;$ find the scalar $\alf$ and a Householder
matrix
$P$ such that $\,Px=\tilde{y}$.
\item Find the QR decomposition of the following matrix. 
\eqmno \dsp
A = \left [\begin {array}{ccc} 2&2&1\\\noalign{\medskip}0&5&3
\\\noalign{\medskip}0&0&0\\\noalign{\medskip}0&0&-1
\\\noalign{\medskip}0&0& 2 \end {array}\right ].
\enmno
\ee

\vthin
\item Write a computer program to find the least dominant eigenvalue
of the matrix $A$ and corresponding the unit eigenvector. Test your code for
the following  matrices:
\eqmno
 A = \left [\begin {array}{ccccccc}
2 & -1 & 0   & 0 & \cdots &\cdots & 0 \
-1 & 2 & -1 & 0 & \cdots & \cdots& 0 \\
0 & -1 & 2 & -1 & \cdots &\cdots&0 \\
\cdots  &\cdots     & \cdots&\cdots&\cdots &\cdots & \cdots  \\
\cdots  &\cdots     & \cdots&\cdots&\cdots &\cdots & \cdots  \\
 0 &\cdots     & \cdots& 0 & -1 & 2 & -1 \\
0 &\cdots     & \cdots& \cdots& 0 &-1 & 2  \\
\end {array}\right ], \qquad  B=
\left [\begin {array}{ccccccc}
2 & -1 & 0   & 0 & \cdots &\cdots & 0 \\
1 & 2 & -1 & 0 & \cdots & \cdots& 0 \\
0 & 1 & 2 & -1 & \cdots &\cdots&0 \\
\cdots  &\cdots     & \cdots&\cdots&\cdots &\cdots & \cdots  \\
\cdots  &\cdots     & \cdots&\cdots&\cdots &\cdots & \cdots  \\
 0 &\cdots     & \cdots& 0 & 1 & 2 & -1 \\
0 &\cdots     & \cdots& \cdots& 0 &1 & 2  \\
\end {array}\right ]; 
\enmno
$C$ is a $n$ by $n$ random matrix generated by (i), generate a diagonal matrix, 
$n=10; D=diag( rand(n,1)*100);  S=rand(n,n);  C=inv(S)*D*S$. In this way, we can generate a matrix with known eigenvalues. 

Tabulate the number of iterations, the relative error of the eigenvalue,
and the residue vector $\|A x - \lambda x\|_2$ for $n=10,20,40,80,160$.
For the second matrix, also try $n=11,21,41,81,161$. Explain your results.
{\bf Hint:} Use the Lemma learned in class to find the exact
eigenvalues of $A$ for the first matrix; and the Matlab function $eig(A)$
for the second matrix.

\ee

\end{document}


