\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 6}\\
Instructor: Anil Damle\\
Due: December 3, 2018 (only one slip day is allowed due to the end of courses)\\

\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:}
We will now explore two small details of the practical QR algorithm\textemdash the computational complexity of each QR factorization step and convergence.

\begin{enumerate}
\item Assume that we are given an $n\times n$ tridiagonal real symmetric matrix $T.$ Using Givens rotations devise an $\cO(n)$ algorithm to compute the QR factorization (you need not explicitly compute $Q,$ it can be in product form)
\[
T = QR.
\]
\item Using your previous algorithm show that you can also compute
\[
\widehat{T} = RQ
\]
in $\cO(n)$ time and $\widehat{T}$ is tridiagonal.
\item Assuming we instead have an $n \times n$ upper Hessenberg matrix $H$ is it easy to adapt your preceding algorithm to get a $QR$ factorization in $\cO(n^2)$ time?
\item Finally, assume we are given an $n\times n$ upper Hessenberg matrix $H$ and are running the QR algorithm with the Rayleigh shift $\mu^{(k)} = H^{(k)}_{n,n}$. Now, say that at step $k$ we are computing the QR factorization of $H^{(k)} - \mu^{(k)}I$ using Givens rotations and prior to applying the final necessary rotation we observe the structure
\[
G^{(n-2)}\cdots G^{(1)}\left(H^{(k)} - \mu^{(k)}I\right) = \begin{bmatrix}R^{(k)}_{11} & R^{(k)}_{12} & R^{(k)}_{13} \\ 0 & a & b \\ 0 & \epsilon & 0 \end{bmatrix}
\]
where $R_{11}^{(k)}$ is $n-2 \times n-2$ and $a,b,$ and $\epsilon$ are scalars. Derive an expression for $H^{(k+1)}_{n,n-1}$ where $H^{(k+1)} = R^{(k)}Q^{(k)} + \mu^{(k)}I$ and given some conditions under which we would expect that entry to be $\cO(\epsilon^2).$ Notably, this argues that we may sometimes expect quadratic convergence of each eigenvalue in the non-symmetric case.
\end{enumerate}
\newpage
\subsection*{Question 2:}
The following question will not be graded and you do not have to submit a solution. Nevertheless, it is certainly plausible that a question on the Lanczos or Arnoldi method for finding eigenvalues/vectors could appear on the final exam. Therefore, we wanted to provide a homework problem on the topic for your perusal.\\

Assume we are using the Lanczos process to compute some eigenvalues of a real symmetric matrix $A$ and build the Krylov space starting with vector $z_0.$ Let $A$ have eigenvalues $\lambda_1,\ldots,\lambda_n$ satisfying $\lambda_1 \geq \cdots \geq \lambda_n$ and associated eigenvectors $v_1,\ldots,v_n.$ 
\begin{enumerate}
\item After $k$ steps of the Lanczos process let $T_k$ be the tridiagonal matrix generated by the process, prove that $\theta_1 = \lambda_1(T_k)$ (the largest magnitude eigenvalue of $T_k$) satisfies
\[
\lambda_1 \geq \theta_1 \geq \lambda_1 - (\lambda_1-\lambda_n)\left(\frac{\tan \phi_1}{c_{k-1}(1+2\rho_1)}\right)^2
\]
where $\cos(\phi_1) = \lvert z_0^Tv_1\rvert,$ $\rho_1=\frac{\lambda_1-\lambda_2}{\lambda_2-\lambda_n},$ and $c_{k-1}(x)$ is the Chebyshev polynomial of degree $k-1.$ 
\item Compare and contrast this convergence result with that for the power method (assuming the eigenvalues are such that the power method would converge to $\lambda_1$).
\end{enumerate}






\end{document}