Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
In linear algebra, one of the most important problems is designing efficient and stable algorithms for finding the eigenvalues of a matrix. These eigenvalue algorithms may also find eigenvectors.-Characteristic polynomial:...
In mathematics, a matrix is a rectangular array of numbers, symbols, or expressions. The individual items in a matrix are called its elements or entries. An example of a matrix with six elements isMatrices of the same size can be added or subtracted element by element...
A, the algorithm will produce a number λ (the eigenvalue) and a nonzero vector v (the eigenvector), such that Av = λv.
The algorithm is also known as the Von Mises iteration.
The power iteration is a very simple algorithm. It does not compute a matrix decomposition
Matrix decomposition
In the mathematical discipline of linear algebra, a matrix decomposition is a factorization of a matrix into some canonical form. There are many different matrix decompositions; each finds use among a particular class of problems.- Example :...
, and hence it can be used when A is a very large sparse matrix
Sparse matrix
In the subfield of numerical analysis, a sparse matrix is a matrix populated primarily with zeros . The term itself was coined by Harry M. Markowitz....
. However, it will find only one eigenvalue (the one with the greatest absolute value
Absolute value
In mathematics, the absolute value |a| of a real number a is the numerical value of a without regard to its sign. So, for example, the absolute value of 3 is 3, and the absolute value of -3 is also 3...
) and it may converge only slowly.
The method
The power iteration algorithm starts with a vector b0, which may be an approximation to the dominant eigenvector or a random vector. The method is described by the iteration
So, at every iteration, the vector bk is multiplied by the matrix A and normalized.
Under the assumptions:
A has an eigenvalue that is strictly greater in magnitude than its other eigenvalues
The starting vector has a nonzero component in the direction of an eigenvector associated with the dominant eigenvalue.
then:
A subsequence of converges to an eigenvector associated with the dominant eigenvalue
Note that the sequence does not necessarily converge. It can be shown that:
where: is an eigenvector associated with the dominant eigenvalue, and . The presence of the term
implies that
does not converge unless
Under the two assumptions listed above, the sequence defined by:
converges to the dominant eigenvalue.
This can be run as a simulation program with the following simple algorithm:
for each(simulation) {
for(i=0; i
for(j=0; j
tmp[i] += b[j]*A[i][j];
}
}
for(k=0; k
norm_factor += tmp[k];
}
b = tmp/norm_factor;
}
After which the values in b are the result. This algorithm is the one used to calculate such things as the Google PageRank
PageRank
PageRank is a link analysis algorithm, named after Larry Page and used by the Google Internet search engine, that assigns a numerical weighting to each element of a hyperlinked set of documents, such as the World Wide Web, with the purpose of "measuring" its relative importance within the set...
.
The method can also be used to calculate the spectral radius
Spectral radius
In mathematics, the spectral radius of a square matrix or a bounded linear operator is the supremum among the absolute values of the elements in its spectrum, which is sometimes denoted by ρ.-Matrices:...
Let be decomposed into its Jordan canonical form: ,
where the first column of is an eigenvector of corresponding to the dominant eigenvalue .
Since the dominant eigenvalue of is unique,
the first Jordan block of is the matrix , where is the largest eigenvalue of A in magnitude.
The starting vector
can be written as a linear combination of the columns of V: .
By assumption, has a nonzero component in the direction of the dominant eigenvalue, so .
In mathematics, a recurrence relation is an equation that recursively defines a sequence, once one or more initial terms are given: each further term of the sequence is defined as a function of the preceding terms....
for
can be rewritten as: ,
where the expression: is more amenable to the following analysis.
The expression above simplifies as
as .
The limit follows from the fact that the eigenvalue of
is less than in 1 in magnitude, so
as
It follows that:
as
Using this fact,
can be written in a form that emphasizes its relationship with when k is large:
where
and
as
The sequence 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 may not converge, 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 v1, v2, …, vm be the corresponding eigenvectors. Suppose that is the dominant eigenvalue, so that for .
The initial vector can be written:
If is chosen randomly (with uniform probability), then c1 ≠ 0 with probability 1
Almost surely
In probability theory, one says that an event happens almost surely if it happens with probability one. The concept is analogous to the concept of "almost everywhere" in measure theory...
. Now,
The expression within parentheses converges to because for . On the other hand, we have
Therefore, converges to (a multiple of) the eigenvector . The convergence is geometric, with ratio
where denotes the second dominant eigenvalue. Thus, the method converges slowly if there is an eigenvalue close in magnitude to the dominant eigenvalue.
Applications
Power iteration is not used very much because it can find only the dominant eigenvalue. Nevertheless, the algorithm is very useful in some specific situations. For instance, Google
Google
Google Inc. is an American multinational public corporation invested in Internet search, cloud computing, and advertising technologies. Google hosts and develops a number of Internet-based services and products, and generates profit primarily from advertising through its AdWords program...
PageRank is a link analysis algorithm, named after Larry Page and used by the Google Internet search engine, that assigns a numerical weighting to each element of a hyperlinked set of documents, such as the World Wide Web, with the purpose of "measuring" its relative importance within the set...
of documents in their search engine. For matrices that are well-conditioned and as sparse as the web matrix, the power iteration method can be more efficient than other methods of finding the dominant eigenvector.
Some of the more advanced eigenvalue algorithms can be understood as variations of the power iteration. For instance, the inverse iteration
Inverse iteration
In numerical analysis, inverse iteration is an iterative eigenvalue algorithm. It allows to find an approximateeigenvector when an approximation to a corresponding eigenvalue is already known....
method applies power iteration to the matrix . Other algorithms look at the whole subspace generated by the vectors . This subspace is known as the Krylov subspace
Krylov subspace
In linear algebra, the order-r Krylov subspace generated by an n-by-n matrix A and a vector b of dimension n is the linear subspace spanned by the images of b under the first r powers of A , that is,...
In numerical linear algebra, the Arnoldi iteration is an eigenvalue algorithm and an important example of iterative methods. Arnoldi finds the eigenvalues of general matrices; an analogous method for Hermitian matrices is the Lanczos iteration. The Arnoldi iteration was invented by W. E...
or Lanczos iteration.
External links
Power method, part of lecture notes on numerical linear algebra by E. Bruce Pitman, State University of New York.
does not necessarily converge. It can be shown that:
is an eigenvector associated with the dominant eigenvalue, and 
. The presence of the term 
defined by:
be decomposed into its Jordan canonical form: 
,
is an eigenvector of 
corresponding to the dominant eigenvalue 
.
is unique,
is the 
matrix
, where
is the largest eigenvalue of A in magnitude.
.
has a nonzero component in the direction of the dominant eigenvalue, so
.
,
is more amenable to the following analysis.
.
when k is large:
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 
may not converge,
is nearly an eigenvector of A for large k.
is the dominant eigenvalue, so that 
for 
.
can be written:
is chosen randomly (with uniform probability), then c1 ≠ 0 with probability 1
because 
for 
. On the other hand, we have
converges to (a multiple of) the eigenvector 
. The convergence is geometric, with ratio
denotes the second dominant eigenvalue. Thus, the method converges slowly if there is an eigenvalue close in magnitude to the dominant eigenvalue.
. Other algorithms look at the whole subspace generated by the vectors 
. This subspace is known as the Krylov subspace
has a nonzero component in the direction of an eigenvector associated with the dominant eigenvalue.
converges to an eigenvector associated with the dominant eigenvalue