Skip to main content
added partial characterization of (non)convergence
Source Link
Arnold Neumaier
  • 11.4k
  • 21
  • 49
  1. In case of a multiple dominant eigenvalue (and no therother of the same absouteabsolute 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 ieasyeasy 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.

[Edit][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. LanczsosLanczos (in the symmetric case) or Arnoldi (in the nonsymmetric case) are far better.

  1. In case of a multiple dominant eigenvalue (and no ther of the same absoute value), the power itieration converges to the vector obtained by projecting the starting vector to the dominant eigenspace. 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 ieasy 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.

[Edit] 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.

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. Lanczsos (in the symmetric case) or Arnoldi (in the nonsymmetric case) are far better.

  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.

added remrk on left orthogonalization
Source Link
Arnold Neumaier
  • 11.4k
  • 21
  • 49
  1. In case of a multiple dominant eigenvalue (and no ther of the same absoute value), the power itieration converges to the vector obtained by projecting the starting vector to the dominant eigenspace. 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 ieasy 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.

[Edit] 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.

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. Lanczsos (in the symmetric case) or Arnoldi (in the nonsymmetric case) are far better.

  1. In case of a multiple dominant eigenvalue (and no ther of the same absoute value), the power itieration converges to the vector obtained by projecting the starting vector to the dominant eigenspace. 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 ieasy 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.

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. Lanczsos (in the symmetric case) or Arnoldi (in the nonsymmetric case) are far better.

  1. In case of a multiple dominant eigenvalue (and no ther of the same absoute value), the power itieration converges to the vector obtained by projecting the starting vector to the dominant eigenspace. 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 ieasy 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.

[Edit] 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.

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. Lanczsos (in the symmetric case) or Arnoldi (in the nonsymmetric case) are far better.

Source Link
Arnold Neumaier
  • 11.4k
  • 21
  • 49

  1. In case of a multiple dominant eigenvalue (and no ther of the same absoute value), the power itieration converges to the vector obtained by projecting the starting vector to the dominant eigenspace. 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 ieasy 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.

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. Lanczsos (in the symmetric case) or Arnoldi (in the nonsymmetric case) are far better.