\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{\C}{\mathbb{C}}
\newcommand{\Rnn}{\R^{n\times n}}
\newcommand{\Rmn}{\R^{m\times n}}
\newcommand{\Cnn}{\C^{n\times n}}
\newcommand{\Cmn}{\C^{m\times n}}
\newcommand{\cO}{\mathcal{O}}
\DeclareMathOperator{\Tr}{Tr}
\DeclareMathOperator{\trace}{trace}
\DeclareMathOperator{\diag}{diag}
\DeclareMathOperator{\dist}{dist}
\sectionfont{\Large\sc}
\subsectionfont{\sc}
\usepackage[margin=1 in]{geometry}
\begin{document}
\noindent
\textsc{\Large CS 6210: Homework 5}\\
Instructor: Anil Damle\\
Due: November 19, 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 supporting plots and requested output from your code
must be typeset and submitted via the CMS as a single 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.\\
\hrule
\vspace{1cm}
\noindent

\subsection*{Question 1:}
Here we will prove one nice property of the Rayleigh Quotient and use that to prove the convergence rate of Rayleigh iteration. Assume that $v$ is an eigenvector of $A$ with simple eigenvalue $\lambda$ and $z$ is some vector of unit length such that $\dist(v,z) = \cO(\epsilon).$ 
\begin{enumerate}
\item Prove that if $A$ is real and symmetric then $\lvert \lambda - r_A(z)\rvert \leq \cO(\epsilon^2).$
\item Assume that $A$ is a $n\times n$ real and symmetric matrix with distinct eigenvalues $\lambda_1,\lambda_2,\ldots,\lambda_n.$ Under the assumption that Rayleigh iteration converges (technically it does for almost all starting vectors, \emph{i.e.} all but a set of measure zero) prove that the convergence is asymptotically cubic to some eigenvalue of $A.$
\item Assuming that $A$ is not symmetric (or hermitian) argue that in general we may only expect the Rayleigh quotient $r_A$ to provide an eigenvalue estimate satisfying $\lvert \lambda - r_A(z)\rvert \leq \cO(\epsilon)$ when $\dist(v,z) = \cO(\epsilon).$ 
\end{enumerate}
(Hint: it may be useful as an intermediary to prove that for two one dimensional subspaces represented by unit length vectors $v$ and $z$ $\dist(v,z) = \sqrt{1-(v^Tz)^2}.$)

\subsection*{Question 2:}
Assume we want to solve an $n \times n$ linear system with $A=M-N$ via a Krylov method (CG, MINRES, or GMRES, whichever is appropriate). Furthermore, assume that $M$ is non-singular and $N$ is rank $k.$ If we can use $M$ as a preconditioner for our Krylov method, at most how many iterations will it take to converge in exact arithmetic? (You may assume any matrix you like is diagonalizable in your proof.)

\subsection*{Question 3:}
Assume you are given an $n\times n$ matrix $A$ with eigenvalues such that $\lvert \lambda_1 \rvert = \lvert \lambda_2 \rvert > \lvert \lambda_3 \rvert > \cdots > \lvert\lambda_n\rvert.$ Is there any sense in which the iterates generated by the power method converge? If you think they do, is there any way to get an estimate of any of the eigenvalues of $A$ given the iterates?
\newpage
\subsection*{Question 4:}
Implement orthogonal iteration (also sometimes known as simultaneous iteration), you may use a built in eigenvalues solver to find the $r$ eigenvalues of the projection of $A$ into the subspace of current iterates.

For the remainder of this problem let $A$ be an $n\times n$ real matrix with the real block Schur factorization (see HW1 for details)
\[
A = \begin{bmatrix}Q_1 & Q_2\end{bmatrix}\begin{bmatrix}T_{11} & T_{12} \\ & T_{22}\end{bmatrix}\begin{bmatrix}Q_1 & Q_2\end{bmatrix}^T
\]
where $Q_1$ is the first $r$ columns of $Q,$ $T_{11}$ is $r\times r$ and the remaining dimensions are as inferred. Furthermore, let $A$ have eigenvalues satisfying $\lvert \lambda_1 \rvert \geq \cdots \geq \lvert \lambda_r \rvert > \lvert \lambda_{r+1} \rvert \geq \lvert \lambda_{r+2} \rvert \geq \cdots \geq \lvert \lambda_n \rvert$ and assume that the $T_{11}$ has eigenvalues $\lambda_1,\ldots,\lambda_r.$
\begin{itemize}
\item For real symmetric $A$ of size $100 \times 100$ generate instances of this problem where $\lambda_{r+1}\rightarrow \lambda_r$ and show your implementation achieves the desired convergence rate (you can show this for either the convergence of the invariant subspace you are computing or the corresponding estimates of the eigenvalues) both in terms of iterations and as a function of the eigenvalue gap. Think carefully about how to illustrate this.
\item Now, assume $A$ is not normal and numerically explore how the convergence behavior of orthogonal iteration changes as a function $\|T_{12}\|_F$ (you may once again use $n=100$) What are the implications of your observations?
\end{itemize}




\end{document}