| course |
course_year |
question_number |
tags |
title |
year |
Numerical Analysis |
II |
104 |
II |
2014 |
Numerical Analysis |
|
Paper 4, Section II, D |
2014 |
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} .$