Power Iteration (computing eigen values and vectors)¶
Definition¶
A simple method for computing the largest eigenvalue and eigenvector for an \(n \times n\) matrix \(\mathbf{A}\).
Multiply an arbitrary nonzero vector repeatedly by \(\mathbf{A}\) to get its dominant eigenvalue and eigenvector.
Power Iteration¶
Drawbacks to Power Iteration:
- The starting vector \(\mathbf{x}_{0}\) may have no component in the dominant eigenvector \(\mathbf{v}_{1}\). However, this possbility is incredibly unlikely if \(\mathbf{x}_{0}\) is chosen randomly. And realistically isn't a problem because rounding error introduces such a component.
- There may be more than one eigenvalue sharing the same largest absolute value, in which case the iteration may converge to a vector that is a linear combination of the corresponding eigenvectors. This possibility can happen realistically, so it must be accounted for.
- For a real matrix and real starting vector, the iteration cannot converge to a complex vector.
- Geometric growth of the components in \(\mathbf{x}_{i}\) can be of risk to numerical overflow. (To solve this we use normalized power iteration)
Normalized Power Iteration¶
