\documentclass[11pt,onecolumn]{article}
\usepackage{amssymb, amsmath, amsthm,graphicx, paralist,algpseudocode,algorithm,cancel,url,color}
\usepackage{sectsty}
\usepackage{fancyvrb}
\usepackage{mathrsfs}
\usepackage{multirow}
\usepackage{hhline}
\usepackage{booktabs}
\usepackage[table]{xcolor}
\usepackage{tikz}
% \usepackage[framed,numbered,autolinebreaks,useliterate]{mcode}
\usepackage{listings}
\usepackage{enumitem}
\newcommand{\bvec}[1]{\mathbf{#1}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\calO}{\mathcal{O}}
\DeclareMathOperator{\Tr}{Tr}
\DeclareMathOperator{\trace}{trace}
\DeclareMathOperator{\diag}{diag}
\sectionfont{\Large\sc}
\subsectionfont{\sc}
\usepackage[margin=1 in]{geometry}
\begin{document}
\noindent
\textsc{\Large CS 4220 / MATH 4260: Homework 3}\\
Instructor: Anil Damle\\
Due: March 30, 2018\\
\subsection*{Policies}
You may discuss the homework problems freely with other students, but please
refrain from looking at their code or writeups (or sharing your own).
Ultimately, you must implement your own code and write up your own solution to
be turned in. Your solution, including plots and requested output from your code
should be typeset and submitted via the CMS as a pdf file. Additionally, please
submit any code written for the assignment via the CMS as well. This can be done
by either including it in your solution as an appendix, or uploading it as a zip
file via the CMS.\\
\hrule
\subsection*{Question 1:}
Assume that we are given $A\in\mathbb{R}^{n\times n},$ $A=A^T,$ and $A$ has eigenvalue and vector pairs $\left\{(v_i,\lambda_i)\right\}_{i=1}^n.$ Furthermore, assume that $\lvert\lambda_1\rvert = \lvert\lambda_2\rvert > \lvert \lambda_3\rvert \geq \lvert\lambda_4\rvert \geq \cdots.$
\begin{enumerate}[label=(\alph*)]
\item Prove that for any initial guess $v^{(0)}$ such that $v^{(0)}$ is not simultaneously orthogonal to both $v_1$ and $v_2$ the power method yields iterates $v^{(k)}$ that converge to lie in the span of $v_1$ and $v_2.$
\item What is the rate of convergence of $1-\left\|\left(v^{(k)}\right)^T\begin{bmatrix}v_1 & v_2\end{bmatrix}\right\|_2.$
\item Does the associated eigenvalue estimate via the Rayleigh quotient necessarily converge in this setting? what about if $\lambda_1 = \lambda_2?$
\end{enumerate}
\subsection*{Question 2:}
What does the $QR$ algorithm without shifts applied to the matrix
\[
\begin{bmatrix}0 & 1 \\ 1 & 0 \end{bmatrix}
\]
converge to? Does using a shift of $A^{(k)}_{n,n}$ change this behavior? (Algorithm~\ref{alg:qr} gives the shifted QR algorithm.)
\subsection*{Question 3:}
For the QR algorithm with an arbitrary shift and initial tri-diagonalization of a symmetric matrix $A$ (see Algorithm~\ref{alg:qr}) prove that $A^{(k)}$ is similar to $A.$
\begin{algorithm}
\caption{QR algorithm with tri-diagonalization and shifts}
\label{alg:qr}
\begin{algorithmic}[1]
\State {\bf input:} $A\in\mathbb{R}^{n\times n}$ symmetric
\State Compute $Q^{(0)}$ such that $A^{(0)} = \left(Q^{(0)}\right)^TAQ^{(0)}$ is tri-diagonal
\For{$k=1,2,3,\ldots$}
\State Pick a shift $\mu^{(k)}$
\State Compute the QR factorization $A^{(k-1)} - \mu^{(k)}I = Q^{(k)}R^{(k)}$
\State $A^{(k)} = R^{(k)}Q^{(k)} + \mu^{(k)}I$
\EndFor
\end{algorithmic}
\end{algorithm}
\subsection*{question 4:}
Implement Rayleigh iteration, shifted inverse iteration, and the QR algorithm without shifts (you may omit the tri-diagonalization and use the QR built into your language of choice). In doing so you will have to think about and use a reasonable convergence criteria given the remainder of this problem. Describe the criteria you chose to implement.
Now, generate a dense symmetric matrix $A \in \mathbb{R}^{500 \times 500}$ whose eigenvalues are uniformly distributed in the interval $[0,1]$ and whose eigenvectors are an orthogonalized set of normalized Gaussian random vectors of length 500. (This can be computed via the Q factor from a QR factorization of a $500 \times 500$ Gaussian random matrix.)
\begin{enumerate}[label=(\alph*)]
\item Using your implementation of the QR algorithm, compute all of the eigenvalues of $A$ and plot a histogram of their values.
\item Now, for 500 random vectors ($\mathcal{N}(0,1)$ entries) that have been normalized, run Rayleigh iteration and plot a histogram of the eigenvalues you converge to. What do you observe? Can you reason about why you might be observing what you do?
\item Now, repeat the same experiment as in the previous part, but generate the initial guess for Rayleigh iteration by running one step of shifted inverse iteration with a shift of $\mu = 1$ on a random vector. Plot a histogram of your 500 computed eigenvalues, what do you observe? Can you reason about why you might be observing what you do?
\end{enumerate}
\subsection*{Question 5:}
Suppose we are using a splitting method with $A=M-N$ to solve $Ax=b$ via the iteration $Mx^{k+1} = Nx^{k}+b$ with some arbitrary initial guess $x^0.$ Prove that the iteration does not necessarily converge if $\rho(R) \geq 1.$ You may assume that the iteration matrix $R=M^{-1}N$ is diagonalizable.
\subsection*{Question 6 (A more challenging, ungraded problem):}
Let $A$ be a $n\times n$ matrix that is not diagonalizable, and whose eigenvalue of largest magnitude, denoted $\lambda_1,$ is associated with a Jordan block of size two. You may assume the rest of the eigenvalues ($\lambda_2,\ldots,\lambda_{n-1}$) are simple. This means that there exists a matrix $X$ such that
\[
X^{-1}AX = \begin{bmatrix}\lambda_1 & 1 & \\ & \lambda_1 & \\ & & \Lambda \end{bmatrix}
\]
where $\Lambda$ is a diagonal matrix and $\|\Lambda\|_2<\lvert \lambda_1\rvert.$ Given essentially any initial guess, what, if anything, does the power method applied to $A$ converge to? If it does converge, at what rate does it do so?
\end{document}