Let $A$ be a real symmetric $n \times n$ matrix with $n$ distinct real eigenvalues $\lambda_{1}<\lambda_{2}<$ $\cdots<\lambda_{n}$ and a corresponding orthogonal basis of normalized real eigenvectors $\left\{\mathbf{w}_{i}\right\}_{i=1}^{n}$.

(i) Let $s \in \mathbb{R}$ satisfy $s<\lambda_{1}$. Given a unit vector $\mathbf{x}^{(0)} \in \mathbb{R}^{n}$, the iteration scheme

$$\begin{gathered} (A-s I) \mathbf{y}=\mathbf{x}^{(k)} \\ \mathbf{x}^{(k+1)}=\mathbf{y} /\|\mathbf{y}\| \end{gathered}$$

generates a sequence of vectors $\mathbf{x}^{(k+1)}$ for $k=0,1,2, \ldots$. Assuming that $\mathbf{x}^{(0)}=\sum c_{i} \mathbf{w}_{i}$ with $c_{1} \neq 0$, prove that $\mathbf{x}^{(k)}$ tends to $\pm \mathbf{w}_{1}$ as $k \rightarrow \infty$. What happens to $\mathbf{x}^{(k)}$ if $s>\lambda_{1}$ ? [Consider all cases.]

(ii) Describe how to implement an inverse-iteration algorithm to compute the eigenvalues and eigenvectors of $A$, given some initial estimates for the eigenvalues.

(iii) Let $n=2$. For iterates $\mathbf{x}^{(k)}$ of an inverse-iteration algorithm with a fixed value of $s \neq \lambda_{1}, \lambda_{2}$, show that if

$$\mathbf{x}^{(k)}=\left(\mathbf{w}_{1}+\epsilon_{k} \mathbf{w}_{2}\right) /\left(1+\epsilon_{k}^{2}\right)^{1 / 2}$$

where $\left|\epsilon_{k}\right|$ is small, then $\left|\epsilon_{k+1}\right|$ is of the same order of magnitude as $\left|\epsilon_{k}\right|$.

(iv) Let $n=2$ still. Consider the iteration scheme

$$s_{k}=\left(\mathbf{x}^{(k)}, A \mathbf{x}^{(k)}\right), \quad\left(A-s_{k} I\right) \mathbf{y}=\mathbf{x}^{(k)}, \quad \mathbf{x}^{(k+1)}=\mathbf{y} /\|\mathbf{y}\|$$

for $k=0,1,2, \ldots$, where $(,$, denotes the inner product. Show that with this scheme $\left|\epsilon_{k+1}\right|=\left|\epsilon_{k}\right|^{3} .$