2016-102.md

course	course_year	question_number	tags	title	year
Numerical Analysis	II	102	II 2016 Numerical Analysis	Paper 4, Section II, B	2016

(a) Describe an implementation of the power method for determining the eigenvalue of largest modulus and its associated eigenvector for a matrix that has a unique eigenvalue of largest modulus.

Now let $A$ be a real $n \times n$ matrix with distinct eigenvalues satisfying $\left|\lambda_{n}\right|=\left|\lambda_{n-1}\right|$ and $\left|\lambda_{n}\right|>\left|\lambda_{i}\right|, i=1, \ldots, n-2$. The power method is applied to $A$, with an initial condition $\mathbf{x}^{(0)}=\sum_{i=1}^{n} c_{i} \mathbf{w}{i}$ such that $c{n-1} c_{n} \neq 0$, where $\mathbf{w}{i}$ is the eigenvector associated with $\lambda{i}$. Show that the power method does not converge. Explain why $\mathbf{x}^{(k)}, \mathbf{x}^{(k+1)}$ and $\mathbf{x}^{(k+2)}$ become linearly dependent as $k \rightarrow \infty$.

(b) Consider the following variant of the power method, called the two-stage power method, applied to the matrix $A$ of part (a):

1. Pick $\mathbf{x}^{(0)} \in \mathbb{R}^{n}$ satisfying $\left|\mathbf{x}^{(0)}\right|=1$. Let $0<\varepsilon \ll 1$. Set $k=0$ and $\mathbf{x}^{(1)}=A \mathbf{x}^{(0)}$.

2. Calculate $\mathbf{x}^{(k+2)}=A \mathbf{x}^{(k+1)}$ and calculate $\alpha, \beta$ that minimise

$$f(\alpha, \beta)=\left|\mathbf{x}^{(k+2)}+\alpha \mathbf{x}^{(k+1)}+\beta \mathbf{x}^{(k)}\right| .$$

2. If $f(\alpha, \beta) \leqslant \varepsilon$, solve $\lambda^{2}+\alpha \lambda+\beta=0$ and let the roots be $\lambda_{1}$ and $\lambda_{2}$. They are accepted as eigenvalues of $A$, and the corresponding eigenvectors are estimated as $\mathbf{x}^{(k+1)}-\lambda_{2} \mathbf{x}^{(k)}$ and $\mathbf{x}^{(k+1)}-\lambda_{1} \mathbf{x}^{(k)}$.

3. Otherwise, divide $\mathbf{x}^{(k+2)}$ and $\mathbf{x}^{(k+1)}$ by the current value of $\left|\mathbf{x}^{(k+1)}\right|$, increase $k$ by 1 and return to Step $\mathbf{1}$.

Explain the justification behind Step 2 of the algorithm.

(c) Let $n=3$, and suppose that, for a large value of $k$, the two-stage power method yields the vectors

$$\mathbf{y}{k}=\mathbf{x}^{(k)}=\left(\begin{array}{l} 1 \ 1 \ 1 \end{array}\right), \quad \mathbf{y}{k+1}=A \mathbf{x}^{(k)}=\left(\begin{array}{c} 2 \ 3 \ 4 \end{array}\right), \quad \mathbf{y}_{k+2}=A^{2} \mathbf{x}^{(k)}=\left(\begin{array}{c} 2 \ 4 \ 6 \end{array}\right)$$

Find two eigenvalues of $A$ and the corresponding eigenvectors.