| course |
course_year |
question_number |
tags |
title |
year |
Numerical Analysis |
II |
108 |
II |
2020 |
Numerical Analysis |
|
Paper 1, Section II, E |
2020 |
Let $A \in \mathbb{R}^{n \times n}$ be a real symmetric matrix with distinct eigenvalues $\lambda_{1}<\lambda_{2}<\cdots<$ $\lambda_{n}$ and a corresponding orthonormal basis of real eigenvectors $\left{\boldsymbol{w}{i}\right}{i=1}^{n}$. Given a unit norm vector $\boldsymbol{x}^{(0)} \in \mathbb{R}^{n}$, and a set of parameters $s_{k} \in \mathbb{R}$, consider the inverse iteration algorithm
$$\left(A-s_{k} I\right) \boldsymbol{y}=\boldsymbol{x}^{(k)}, \quad \boldsymbol{x}^{(k+1)}=\boldsymbol{y} /|\boldsymbol{y}|, \quad k \geqslant 0 .$$
(a) Let $s_{k}=s=$ const for all $k$. Assuming that $\boldsymbol{x}^{(0)}=\sum_{i=1}^{n} c_{i} \boldsymbol{w}{i}$ with all $c{i} \neq 0$, prove that
$$s<\lambda_{1} \Rightarrow \boldsymbol{x}^{(k)} \rightarrow \boldsymbol{w}{1} \quad \text { or } \quad \boldsymbol{x}^{(k)} \rightarrow-\boldsymbol{w}{1} \quad(k \rightarrow \infty) .$$
Explain briefly what happens to $\boldsymbol{x}^{(k)}$ when $\lambda_{m}<s<\lambda_{m+1}$ for some $m \in{1,2, \ldots, n-1}$, and when $\lambda_{n}<s$.
(b) Let $s_{k}=\left(A \boldsymbol{x}^{(k)}, \boldsymbol{x}^{(k)}\right)$ for $k \geqslant 0$. Assuming that, for some $k$, some $a_{i} \in \mathbb{R}$ and for a small $\epsilon$,
$$\boldsymbol{x}^{(k)}=c^{-1}\left(\boldsymbol{w}{1}+\epsilon \sum{i \geqslant 2} a_{i} \boldsymbol{w}_{i}\right)$$
where $c$ is the appropriate normalising constant. Show that $s_{k}=\lambda_{1}-K \epsilon^{2}+\mathcal{O}\left(\epsilon^{4}\right)$ and determine the value of $K$. Hence show that
$$\boldsymbol{x}^{(k+1)}=c_{1}^{-1}\left(\boldsymbol{w}{1}+\epsilon^{3} \sum{i \geqslant 2} b_{i} \boldsymbol{w}_{i}+\mathcal{O}\left(\epsilon^{5}\right)\right)$$
where $c_{1}$ is the appropriate normalising constant, and find expressions for $b_{i}$.