4
$\begingroup$

To compute the eigenvector corresponding to a dominant eigenvalue of a matrix $A\in\mathbb{R}^{n\times n}$, one could apply the Power Iteration: $$v_1=\frac{Av_1}{\|Av_1\|}.$$

1) in case $A$ is symmetric, eigenvectors are orthonormal. However, suppose that there are, e.g, two occurrences of the dominant eigenvalue $\lambda_1$ corresponding to different eigenvectors. Does that mean that the method would yield inconsistent results on different invocation? The "inconsistency" means that the method could (assuming random initialization on each invocation) change direction of convergence (since the eigenvalues are the same)

In case one needs the following dominant eigenvector, one usually performs Gram Schmidt orthonormalization, ie, removes component of the first eigenvector from the initialization to the second. Would this second vector converge to the eigenvector corresponding to "the other" occurence of dominanant eigenvalue $\lambda_1$?

2) in case of a general $A$, eigenvectors are not orthonormal. So, what would be the way to extract subsequent eigenvectors. In other words, would GS orthonormalization now make sense? It removes component from the first eigenvector, but, since the eigenvectors are not orthogonal, I'm not sure it the following matrix-vector multiplication adds the component back.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ 1) No, Yes. 2) Yes. $\endgroup$
    – Arnold Neumaier
    Commented Oct 11, 2012 at 10:41
  • $\begingroup$ @ArnoldNeumaier in 1), "the inconsistency" means that the method could (assuming random initialization on each invocation) change direction of convergence (since the eigenvalues are the same). Does this change your answer 1a) and 1b)? ...for 2) How can it be shown that the component of $v_1$ is not added back by matrix-vector mult? Note that, in case of subsequent application of GS, the resulting vectors would be orthogonal; the eigenvectors of a general $A$ might not be. $\endgroup$
    – usero
    Commented Oct 11, 2012 at 10:53

1 Answer 1

Reset to default
5
$\begingroup$

1) In case of a multiple dominant eigenvalue (and no other of the same absolute value), the power itieration converges to the vector obtained by projecting the starting vector to the dominant eigenspace (if this vector is nonzero). These projections are orthogonal if the matrix is symmetric. Of course, if you start with different starting vectors you'll typically get different such projections.

2) If the matrix is nondefective, the starting vector can be written in a unique way as a linear combination of eigenvectors to distinct eigenvalues. In this decomposition, it is easy to see what happens when you iterate. If the matrix is nondefective, the result is the same but the proof needs an additional limiting step.

[Edit1] Note that in the nonsymmetric, nondefective case, the left and right eigenvectors form a biorthogonal system, and one must orthogonalize with a left eigenvector to get a particular right eigenvector.

[Edit2]
3) If the matrix has precisely two dominant eigenvalues, each of algebraic multiplicity 1, one has convergence if and only the starting vector is orthogonal to exactly one of the corresponding left eigenvectors, and then converges to the other. I leave it as an exercise to figure out what happens in the other degenerate cases possible.

But why are you so concerned about the power iteration? it is generally a poor method, and it fails to converge if there are two different eigenvalues with (equal) maximal absolute value. Lanczos (in the symmetric case) or Arnoldi (in the nonsymmetric case) are far better.

Improve this answer
$\endgroup$
5
  • $\begingroup$ An additional concern on 2): the initial GS would remove the component of $u_1$ in the initialization for $u_2$, but in inexact arithmetic the component might be added back. However, subsequent GS would yield an orthogonal vector, and $v_2$ need not be necessarily orthogonal to $v_1$. So, is the additional application of GS to remove component of $u_1$ meaningful? In your last paragraph: method still converges, but with inconsistent results (your 1)) .My interest in the method stems from its large utilization for eigenvectors of a Laplacian (abundant literature considers it). $\endgroup$
    – usero
    Commented Oct 11, 2012 at 14:16
  • $\begingroup$ Maybe my edit helps for 2). - Even for Laplacians, you'll usually get quite a speedup with Lanczsos/Arnoldi. - if there are dominant eigenvalues 1 and -1, say, the power iteration oscillates and does not converge for generic starting points: try $A=Diag(1,-1)$ and start with the all-one vector. $\endgroup$
    – Arnold Neumaier
    Commented Oct 11, 2012 at 14:25
  • $\begingroup$ To avoid potential misinterpretation: in case of a symmetric input matrix with two dominant eigenvalues $$|\lambda_1|=|\lambda_2| ~~~~~~~~~~~~ i),$$ the power method converges, but not to the eigenvector (according from your 1)). The ambiguity is caused by the above comment: can it happen that the power method converges to (one of) the dominant eigenvectors in case of i) (e.g, random starting point), or does it always fail to converge? Argumentation from en.wikipedia.org/wiki/Power_iteration is tailored for strictly dominant eigenvalue. $\endgroup$
    – usero
    Commented Oct 31, 2012 at 18:02
  • $\begingroup$ On en.wikipedia.org/wiki/Lanczos_algorithm I found that the vector that PowerMethod (PM) converges to in case of two identical dominant eigenvalues is the one spanned by these two corresponding eigenvectors (so, not a dominant eigenvector). However, if the dominant eigValue is large, does the PM tend to increase the contribution of the "nearest" eigenvector? $\endgroup$
    – usero
    Commented Nov 1, 2012 at 15:12
  • $\begingroup$ See the second edit. But had you followed up my suggestion in 2), you would have found this out by yourself. $\endgroup$
    – Arnold Neumaier
    Commented Nov 1, 2012 at 16:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.