\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}
\newcommand{\bvec}[1]{\mathbf{#1}}
\newcommand{\R}{\mathbb{R}}
\DeclareMathOperator{\Tr}{Tr}
\sectionfont{\Large\sc}
\subsectionfont{\sc}
\usepackage[margin=1 in]{geometry}
\begin{document}
\noindent
\textsc{\Large CS 3220: Homework 3}\\
Instructor: Anil Damle\\
Due: October 7, 2020\\
\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 typset and submitted via the CMS as a pdf file. Additionally, please submit any code written for the assignment via the CMS as well.\\
\hrule
\vspace{5mm}
\subsection*{Question 1:}
In class we made the observation that when we run the power method, the $k^{th}$ iterate can be written as
\[
v^{(k)} = c_k A^k v^{(0)}
\]
for some constant $c_k,$ where our chosen starting vector is $v^{(0)}$ (you should assume $v_1^Tv^{(0)}\neq 0$). Let $V$ be the matrix whose columns are the eigenvectors (\emph{i.e.,} the columns of $V$ denoted $v_i$ are the eigenvectors) of a symmetric matrix $A.$ (Assume they are ordered with respect to the eigenvalues $\lambda_1,\lambda_2,\ldots$ and assuming $\lvert\lambda_1\rvert > \lvert\lambda_2 \rvert \geq \lvert\lambda_3 \rvert \geq \dots \lvert\lambda_n \rvert \geq 0$). We showed that
\[
v^{(k)} = c_k \lambda_1^k \left(\alpha_1 v_1 + \sum_{i=2}^n \alpha_i \left(\frac{\lambda_i}{\lambda_1}\right)^kv_i\right)
\]
where $\alpha_i = v_i^T v^{(0)}.$
\begin{enumerate}[(a)]
\item Argue that $\lvert c_k \alpha_1 \lambda_1^k \rvert \rightarrow 1$ as $k\rightarrow \infty.$ Are the absolute value signs necessary? Hint: consider how to write $\|A^kv^{(0)}\|_2$ in terms of $\alpha_i$'s and $\lambda_i$'s.
\end{enumerate}
\subsection*{Question 2:}
Here, we will geometrically explore the behavior of the power method. First, implement the power method in your language of choice. Now, consider the following sequence of steps.
\begin{enumerate}[(a)]
\item For $n=2$ construct a ``random'' orthogonal matrix. This may be accomplished by generating a $2\times 2$ random matrix (say with $\mathcal{N}(0,1)$ entries) using built in functions in your language of choice, call it $B,$ computing the SVD of B and using either of the resulting orthogonal matrices returned\textemdash call this orthogonal matrix $V.$ Outline the procedure you used.
\item Now, let $A = V\Lambda V^T$ where
\[
\Lambda = \begin{bmatrix} 2 & 0 \\ 0 & 1\end{bmatrix}.
\]
Using a built in routine in your language of choice, compute the eigenvalues of $A$ and verify that they are correct.
\item Now, pick a random vector $v^{(0)}$ and normalize it. Plot a picture of the unit sphere along with points representing the vectors $v^{(0)} / \|v^{(0)}\|_2,$ $v_1,$ and $v_2.$
\item Finally, for $k = 1,2,\ldots$ plot the point on the sphere representing the iterate $v^{(k)},$ what do you observe? You need not provide plots for all $k,$ choose some to make your point and you can also stop when it is no longer possible to visually distinguish $v^{(k)}$ and $v_1.$
\end{enumerate}
Now, just to be sure your implementation of the power method is working do the following:
\begin{enumerate}[(a)]
\setcounter{enumi}{4}
\item Generate a random $100 \times 100$ symmetric matrix $A.$ (To do this, generate a random $100\times 100$ matrix $B$ using built in functions\textemdash the specific distribution is not so important\textemdash and form $A = (B+B^T)/2.$) Using a built in function compute the eigenvalues of $A,$ then run your version of the power method and plot $\log \lvert \lambda^{(k)} - \lambda_1 \rvert$ vs $k,$ you may stop when this quantity is less than $10^{-8}.$ Does the slope of the line agree with our assessment in class that $\lvert \lambda^{(k)} - \lambda_1 \rvert = \mathcal{O}(\lvert \lambda_2 / \lambda_1 \rvert^{2k})$? Think about how to argue this based on the slope of the line and recall that you have computed $\lambda_2$ as well via the built in routine.
\end{enumerate}
\subsection*{Question 3:}
Let $D\in\R^{n\times n}$ be a diagonal matrix with $D_{ii} = (1/10)^{(i-1)}.$
\begin{enumerate}[(a)]
\item What is $\kappa_2(D)$ as a function of $n?$
\item If $Dx = b$ for a given $b$ and I want to maximize the change in the solution when I solve $D(x + \hat{x}) = b + \hat{b}$ (recall we are just writing the new solution with respect to the point $x$) how do I do this? More specifically, if I fix the norm of $\|\hat{b}\|_2$ which vector(s) maximize $\|\hat{x}\|_2?$
\end{enumerate}
Now, we will use that to understand what changes to $b$ result in worst case changes in $x.$
\begin{enumerate}[(a)]
\setcounter{enumi}{2}
\item Let $A\in\R^{n\times n}$ be full rank. If $Ax=b$ and I want to maximize the change in the solution by perturbing $b$ in what direction should $\hat{b}$ lie? Again, specifically, this means that you get to pick $\hat{b}$ and would like $\hat{x}$ to be as big as possible when $A(x+\hat{x}) = b+\hat{b}.$ Note that while nominally we can think of this as having a ``budget'' for the perturbation size $\|\hat{b}\|_2$ the answer does not depend on this\textemdash irrespective of the size of the perturbation the direction it should lie in remains unchanged.
\item Consider the same setup as the previous part, except now you would like to know which perturbations $\hat{b}$ result in the smallest $\hat{x}.$ To have the smallest change in $\hat{x},$ in what direction should $\hat{b}$ lie?
\end{enumerate}
\end{document}