Eigenvalue algorithm
In mathematics, power iteration (also known as the power method) is an eigenvalue algorithm: given a diagonalizable matrix formula_1, the algorithm will produce a number formula_2, which is the greatest (in absolute value) eigenvalue of formula_1, and a nonzero vector formula_4, which is a corresponding eigenvector of formula_2, that is, formula_6.
The algorithm is also known as the Von Mises iteration.
Power iteration is a very simple algorithm, but it may converge slowly. The most time-consuming operation of the algorithm is the multiplication of matrix formula_1 by a vector, so it is effective for a very large sparse matrix with appropriate implementation. The speed of convergence is like formula_8(see a later section). In words, convergence is exponential with base being the spectral gap.
The method.
The power iteration algorithm starts with a vector formula_9, which may be an approximation to the dominant eigenvector or a random vector. The method is described by the recurrence relation
formula_10
So, at every iteration, the vector formula_11 is multiplied by the matrix formula_1 and normalized. 
If we assume formula_1 has an eigenvalue that is strictly greater in magnitude than its other eigenvalues and the starting vector formula_9 has a nonzero component in the direction of an eigenvector associated with the dominant eigenvalue, then a subsequence formula_15 converges to an eigenvector associated with the dominant eigenvalue.
Without the two assumptions above, the sequence formula_15 does not necessarily converge. In this sequence,
 formula_17,
where formula_18 is an eigenvector associated with the dominant eigenvalue, and formula_19. The presence of the term formula_20 implies that formula_21 does not converge unless formula_22. Under the two assumptions listed above, the sequence formula_23 defined by
 formula_24
converges to the dominant eigenvalue (with Rayleigh quotient).
One may compute this with the following algorithm (shown in Python with NumPy):
import numpy as np
def power_iteration(A, num_iterations: int):
 # Ideally choose a random vector
 # To decrease the chance that our vector
 # Is orthogonal to the eigenvector
 b_k = np.random.rand(A.shape[1])
 for _ in range(num_iterations):
 # calculate the matrix-by-vector product Ab
 b_k1 = np.dot(A, b_k)
 # calculate the norm
 b_k1_norm = np.linalg.norm(b_k1)
 # re normalize the vector
 b_k = b_k1 / b_k1_norm
 return b_k
power_iteration(np.array(0.5, 0.5], [0.2, 0.8), 10)
The vector formula_11 converges to an associated eigenvector. Ideally, one should use the Rayleigh quotient in order to get the associated eigenvalue.
This algorithm is used to calculate the "Google PageRank".
The method can also be used to calculate the spectral radius (the eigenvalue with the largest magnitude, for a square matrix) by computing the Rayleigh quotient
formula_26
Analysis.
Let formula_1 be decomposed into its Jordan canonical form: formula_28, where the first column of formula_29 is an eigenvector of formula_1 corresponding to the dominant eigenvalue formula_31. Since generically, the dominant eigenvalue of formula_1 is unique, the first Jordan block of formula_33 is the formula_34 matrix formula_35 where formula_31 is the largest eigenvalue of "A" in magnitude. The starting vector formula_9 can be written as a linear combination of the columns of "V":
formula_38
By assumption, formula_39 has a nonzero component in the direction of the dominant eigenvalue, so formula_40.
The computationally useful recurrence relation for formula_41 can be rewritten as:
formula_42
where the expression: formula_43 is more amenable to the following analysis.
formula_44
The expression above simplifies as formula_45
formula_46
The limit follows from the fact that the eigenvalue of formula_47 is less than 1 in magnitude, so
formula_48
It follows that:
formula_49
Using this fact, formula_50 can be written in a form that emphasizes its relationship with formula_51 when "k" is large:
formula_52
where formula_53 and formula_54 as formula_45
The sequence formula_56 is bounded, so it contains a convergent subsequence. Note that the eigenvector corresponding to the dominant eigenvalue is only unique up to a scalar, so although the sequence formula_57 may not converge,
formula_50 is nearly an eigenvector of "A" for large "k".
Alternatively, if "A" is diagonalizable, then the following proof yields the same result
Let λ1, λ2, ..., λ"m" be the m eigenvalues (counted with multiplicity) of A and let "v"1, "v"2, ..., "v""m" be the corresponding eigenvectors. Suppose that formula_59 is the dominant eigenvalue, so that formula_60 for formula_61.
The initial vector formula_9 can be written:
formula_63
If formula_9 is chosen randomly (with uniform probability), then "c"1 ≠ 0 with probability 1. Now,
formula_65
On the other hand:
formula_66
Therefore, formula_11 converges to (a multiple of) the eigenvector formula_18. The convergence is geometric, with ratio
formula_69
where formula_70 denotes the second dominant eigenvalue. Thus, the method converges slowly if there is an eigenvalue close in magnitude to the dominant eigenvalue.
Applications.
Although the power iteration method approximates only one eigenvalue of a matrix, it remains useful for certain computational problems. For instance, Google uses it to calculate the PageRank of documents in their search engine, and Twitter uses it to show users recommendations of whom to follow. The power iteration method is especially suitable for sparse matrices, such as the web matrix, or as the matrix-free method that does not require storing the coefficient matrix formula_1 explicitly, but can instead access a function evaluating matrix-vector products formula_72. For non-symmetric matrices that are well-conditioned the power iteration method can outperform more complex Arnoldi iteration. For symmetric matrices, the power iteration method is rarely used, since its convergence speed can be easily increased without sacrificing the small cost per iteration; see, e.g., Lanczos iteration and LOBPCG.
Some of the more advanced eigenvalue algorithms can be understood as variations of the power iteration. For instance, the inverse iteration method applies power iteration to the matrix formula_73. Other algorithms look at the whole subspace generated by the vectors formula_11. This subspace is known as the Krylov subspace. It can be computed by Arnoldi iteration or Lanczos iteration.
Gram iteration is a super-linear and deterministic method to compute the largest eigenpair.
References.
 ;templatestyles src="Reflist/styles.css" / ;