0

Suppose $A$ is $m\times m$ and has a complete set of orthonormal eigenvectors, $q_1, \ldots , q_m$, and with corresponding eigenvalues $\lambda_1,\ldots , \lambda_m$. Assume that the ordering is such that $\left|\lambda_j\right| \geq \left|\lambda_{j+1}\right|$. Furthermore, assume that $\left|\lambda_1\right| > \left|\lambda_2\right| > \left|\lambda_3\right|$. Consider the artificial version of the power method $v^{(k)} = Av^{(k-1)}/\lambda_1$, with $v^{(0)}=\alpha_1q_1+\ldots +\alpha_mq_m$ where $\alpha_1$ and $\alpha_2$ are both nonzero. (This is artificial since the normalizing factor $\lambda_1$ in the iteration would not be known ahead of time. However, this version is easier to analyze.) Show that the sequence $\{v^{(k)}\}^\infty_{k=0}$ converges linearly to $\alpha_1q_1$ with asymptotic constant $C = \left|\lambda_2/\lambda_1\right|$.

So far I see that I can use the $QR$ factorization of $A$ to do something with it and apply a more general power method argument but I don't see how it is done here

Razor7654
  • 163
  • 1
  • 7
  • What does the iteration look like in the basis $q_1,...,q_m$? I presume you mean convergence rate $|{\lambda_2 \over \lambda_1}|$? – copper.hat Apr 12 '16 at 06:17

1 Answers1

1

Take any vector, which can be expressed in the base of the eigenvectors:

$$v=v_1e_1+v_2e_2+\cdots v_me_m.$$

Then

$$\frac1{\lambda_1}{Av}=v_1e_1+\frac{\lambda_2}{\lambda_1}v_2e_2+\cdots \frac{\lambda_m}{\lambda_1}v_me_m.$$

Iterating,

$$\frac1{\lambda_1}A\left(\frac1{\lambda_1}{Av}\right)=v_1e_1+\left(\frac{\lambda_2}{\lambda_1}\right)^2v_2e_2+\cdots\left(\frac{\lambda_m}{\lambda_1}\right)^2v_me_m.$$

You should get the idea.