Power method converging towards non-dominant eigenvector

Question

I need to calculate the dominant eigenvalue of the square matrix $\begin{pmatrix} 15 & -4 & -3\\ -10 & 12 & -6\\ -20 & 4 & -2 \end{pmatrix}$ and also the corresponding eigen vector.

The most obvious choice of the method is the power method. For this, I chose the initial guess of dominant vector as $ \begin{pmatrix} 0\\0 \\1 \end{pmatrix} $. While choosing this guess of dominant eigen vector, the solution converges towards the eigenvalue $ 10 $, with corresponding eigenvector $ \begin{pmatrix} -0.5\\-1 \\0.5 \end{pmatrix}$.

After a short check in Wolfram, I found out the dominant eigenvalue is $ 20 $. In fact if I choose the initial guess as $\begin{pmatrix} 1\\0 \\0 \end{pmatrix}$, then the method converges to the true dominant eigenvalue.

Does this suggest that the outcome of Power method is dependent on the choice of initial guess? If yes, then what is the rule of thumb that we can follow to get only the dominant eigenvalue/eigenvector?

Also, while performing power method, it is required that numerically largest value be taken out as common to produce $ X^{(n)} $ for next iteration. For instance, if I have $ AX^{(n)} = \begin{pmatrix} 15\\-20 \\10 \end{pmatrix}$, then which one of the following is the correct way of finding $ X^{(n+1)} $?

1. $\begin{pmatrix} 15\\-20 \\10 \end{pmatrix} = 20 \begin{pmatrix} 0.75\\-1 \\0.5 \end{pmatrix} = \lambda ^{(n+1)}X^{(n+1)}$
2. $\begin{pmatrix} 15\\-20 \\10 \end{pmatrix} = -20 \begin{pmatrix} -0.75\\1 \\-0.5 \end{pmatrix} = \lambda ^{(n+1)}X^{(n+1)}$
3. $\begin{pmatrix} 15\\-20 \\10 \end{pmatrix} = 15 \begin{pmatrix} 1\\-1.333 \\0.667 \end{pmatrix} = \lambda ^{(n+1)}X^{(n+1)}$

Answer 1

The eigenvectors to the eigenvalues $20, -5, 10$ are the columns of $$ V=\pmatrix{ -2 & 1 & 1 \\ 1 & 2 & 2 \\ 2 & 4 & -1 } $$ and can see that $x^{[0]}=\pmatrix{0\\0\\1}$ is one-fifth of the difference of the last two columns $x^{[0]}=0.2(v_2-v_3)$. As it has no part from the first eigenspace, the power iteration will be constrained to the space spanned by the last two eigenvectors and converge towards the largest eigenvalues in that space.

If you want to almost guarantee convergence towards the eigenspaces of the largest eigenvalue, take a random vector as initial vector.

---

In the eigenbasis, the first coordinate is zero. You get $$ A^kx^{[0]}=0⋅v_1+0.2⋅(−5)^kv_2−0.2⋅10^kv_3 $$ which does not contain $v_1$ and thus the eigenvalue $20$ at any point. Now if you add numerical noise, that zero coefficient becomes a non-zero $\varepsilon\approx 2^{-50}$ and gets magnified with coefficient $(20/10)^k=2^k$ in the normalized iterated vectors $$ 10^{-k}⋅A^kx^{[0]}=2^k ε⋅v_1+0.2⋅(−0.5)^kv_2−0.2⋅v_3 $$ so that it builds up for about $50$ iterations (mantissa length $53$) to be equal in magnitude to the other coefficients and eventually dominates and drives out all other coefficients after about $50$ further iterations, as for $k>50$ $$ 2^{50}⋅20^{-k}⋅A^kx^{[0]}=2^{50} ε⋅v_1+0.2⋅0.5^{50}⋅(−0.25)^{k-50}⋅v_2−0.2⋅0.5^{k-50}⋅v_3. $$

Answer 2

I can only reproduce the behaviour if I do not iterate enough. Notice that the inner product of the eigenvectors with eigenvalue 10 and 20 is 0.3, so they are not very orthogonal. The less orthogonal these two eigenvectors are, the harder it is to find them by power iteration.

If I iterate only 10 times, I get the eigenvalue/eigenvector you mention. After 25 iterations it starts to move away from this pair and towards the correct pair. If I use 100 iterations I am very close to the desired eigenvalue/eigenvector pair.

Power iteration is very slow. You should do significantly more than 10 iterations. It's probably also best to start with a random initial vector to decrease the chances of having an initial guess orthogonal to the desired eigenvector (in particular, a unit vector might be a very bad guess).

None of the three things you mentioned is the correct way of defining your next iteration. You should be normalizing the current iteration to have norm 1 before applying A.