The power method

Directly to the input form: predefined case

Directly to the input form: user defined case

• The power method, invented by von Mises, and its modification "inverse iteration" by Wielandt is a very simple method for the determination of the absolutely largest or absolutely smallest eigenvalue of an in principle "general" matrix A.
• The direct iteration following v.Mises gives the absolutely largest eigenvalue and the inverse iteration following Wielandt the absolutely smallest (via its reciprocal), if the so called shift parameter is chosen as zero, otherwise the eigenvalue which is nearest to the shift chosen. Both methods determine a corresponding eigenvector and the eigenvalue is found afterwards for example using the Rayleigh quotient.
• Both methods have the same structure. The power method builds a sequence of vectors
  with x₀ properly chosen, normalized with first component nonnegative (this is done here automatically)
  using
  for k=0,1,...
  w = A x_k (an intermediate vector)
  λ = x_k^Tw (the Rayleigh quotient)
  x_k+1 = w/norm(w) with first component nonnegative
  check convergence via norm(x_k+1-x_k)
  The inverse Iteration is in principle the application of the power method to the inverse matrix, but replacing matrix inversion by iterated linear system solves
  A w = x_k
  
• Both methods allow the introduction of a shift μ of the spectrum, i.e. A is replaced by A - μ *I
• for convergence, there must be no two different dominant eigenvalues and the initial vector x₀ must have a component in the direction of the true eigenvector.
• If the matrix is diagonalizable then speed of convergence is linear and given by the quotient of the first subdominant and the dominant eigenvalue. In the case of a dominant eigenvalue with incomplete eigensystem convergence is sublinear only. Hence the importance of this method comes from its basic theory which underlies many more advanced methods. However, with properly chosen variable shifts it is the basis of the powerful methods QR (resp. QL)-iteration.
• We have two input forms for reasons of better readibility: 4 prepared cases and Input of a user defined matrix

Input forms: Predefined and User defined

Inputs: Predefined cases

• Choose between direct power method and inverse iteration.
• There are four predefined matrices with exactly known eigensystem, which is given there.
• Either you type your own initial vector x₀ or decide for an automatic generation using a random number generator.
• You must set the shift μ.
• The parameter eps, which is used in the termination criterion: The computation terminates if the relative change in the computed eigenvector is less than eps. Important: 1.E-11 <= eps <= 1.E-2 !
• The maximum number of steps to be performed: iter. Important: iter <= 10000 !
• You might want to see a printout of A.
• You might want to see a printout of the computed eigenvector.

The results:

• the matrix A, if requested.
• the number of iterations performed.
• the computed eigenvalue, if no error occured.
• the computed eigenvector, if requested and no error occured.
• A plot with logarithm to base 10 of the relative error of the computed eigenvalue (i.e. essentially the number of correct digits) and of the norm of the difference of the iterated vectors.

Questions: Predefined case ?!

• How depends speed of convergence on the shift ?
• What takes place in the case of an eigenvalue cluster and what if there is a true multiple eigenvalue?
• What takes place in case of a dominant conjugate complex eigenvalue?
• What takes place with a wrong initial guess, combined with a low or a high precision requirement?

Input form: Predefined case

The inputs: user defined case

• Choice of the method: direct= power method or invers = Wielandt-Iteration , i.e. absolutely largest or absolutely smallest eigenvalue of A-μ*I is to be found.
• The dimension n of A. Important: 2 <= n <= 30 !
• You have the choice:
  1. input of n eigenvalues, from which A is generated using an internally fixed complete eigensystem or
  2. direct input of a n x n matrix.
• The initial vector can be given explicitly or you might choose internal generation via a random number generator.
• The shift μ .
• The parameter eps which determines termination. The computation terminates if the relative change in the iterated vector is less than eps. Important: 1.E-11 <= eps <= 1.E-2 !
• The maximum number of steps: iter. Important: iter <= 10000 !
• You might want to see a printout of A.
• You might want to see a printout of the eigenvector.

The output : user defined case

• The matrix A, if requested.
• The number of iterations performed.
• The approximate eigenvalue, if no premature termination occured.
• The approximate eigenvector, if requested and if no premature termination occured.
• A plot with the log10 of the norm of the difference of successive iterates.

Questions: user defined case ?!

• How depends speed of convergence on the shift μ?
• How depends convergence on the eigenvalue distribution of the matrix?
• What takes place if complex eigenvalues become dominant ?
• What takes place if there is a cluster of nearby dominant eigenvalues?
• What takes place if you combine a faulty input vector with a low or a very high precision requirement?

The input form: user defined case