In mathematics, the power iteration is an eigenvalue algorithm: given a matrix A, the algorithm will produce a number λ (the eigenvalue) and a nonzero vector v (the eigenvector), such that Av = λv. Mathematics is the body of Knowledge and Academic discipline that studies such concepts as Quantity, Structure, Space and In Linear algebra, one of the most important problems is designing efficient and stable Algorithms for finding the Eigenvalues of a matrix In Mathematics, a matrix (plural matrices) is a rectangular table of elements (or entries) which may be Numbers or more generally In Mathematics, given a Linear transformation, an of that linear transformation is a nonzero vector which when that transformation is applied to it changes

The power iteration is a very simple algorithm. It does not compute a matrix decomposition, and hence it can be used when A is a very large sparse matrix. In the mathematical discipline of Linear algebra, a matrix decomposition is a Factorization of a matrix into some Canonical form. In the mathematical subfield of Numerical analysis a sparse matrix is a matrix populated primarily with zeros However, it will find only one eigenvalue (the one with the greatest absolute value) and it may converge only slowly. In Mathematics, the absolute value (or modulus) of a Real number is its numerical value without regard to its sign.

## 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

$b_{k+1} = \frac{Ab_k}{\|Ab_k\|}.$

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 b0 has a nonzero component in the direction of an eigenvector associated with the dominant eigenvalue.

then:

• A subsequence of $\left( b_{k} \right)$ converges to an eigenvector associated with the dominant eigenvalue

Note that the sequence $\left( b_{k} \right)$ does not necessarily converge. It can be shown that:
bk = eiφkv1 + rk where: v1 is an eigenvector associated with the dominant eigenvalue, and $\| r_{k} \| \rightarrow 0$. The presence of the term eiφk implies that $\left( b_{k} \right)$ does not converge unless eiφk = 1 Under the two assumptions listed above, the sequence $\left( \mu_{k} \right)$ defined by: $\mu_{k} = \frac{b_{k}^{*}Ab_{k}}{b_{k}^{*}b_{k}}$ converges to the dominant eigenvalue.

The method can also be used to calculate the spectral radius of a matrix by computing the Rayleigh quotient

$\frac{b_k^\top A b_k}{b_k^\top b_k} = \frac{b_{k+1}^\top b_k}{b_k^\top b_k}.$

## Analysis

Let A be decomposed into its Jordan canonical form: A = VJV − 1, where the first column of V is an eigenvector of A corresponding to the dominant eigenvalue λ1. In Mathematics, the spectral radius of a matrix or a Bounded linear operator is the Supremum among the Absolute values of the elements In Mathematics, for a given complex Hermitian matrix A and nonzero vector x the Rayleigh quotient R(A x is defined In Linear algebra, Jordan normal form (often called Jordan canonical form)shows that a given square matrix M over a field K Since the dominant eigenvalue of A is unique, the first Jordan block of J is the $1 \times 1$ matrix $\begin{bmatrix} \lambda_{1} \end{bmatrix}$, where λ1 is the largest eigenvalue of A in magnitude. The starting vector b0 can be written as a linear combination of the columns of V: $b_{0} = c_{1}v_{1} + c_{2}v_{2} + \cdots + c_{n}v_{n}$. By assumption, b0 has a nonzero component in the direction of the dominant eigenvalue, so $c_{1} \ne 0$.

The computationally useful recurrence relation for bk + 1 can be rewritten as: $b_{k+1}=\frac{Ab_{k}}{\|Ab_{k}\|}=\frac{A^{k+1}b_{0}}{\|A^{k+1}b_{0}\|}$, where the expression: $\frac{A^{k+1}b_{0}}{\|A^{k+1}b_{0}\|}$ is more amenable to the following analysis. "Difference equation" redirects here It should not be confused with a Differential equation.
$\begin{matrix}b_{k} &=& \frac{A^{k}b_{0}}{\| A^{k} b_{0} \|} \\ &=& \frac{\left( VJV^{-1} \right)^{k} b_{0}}{\|\left( VJV^{-1} \right)^{k}b_{0}\|} \\ &=& \frac{ VJ^{k}V^{-1} b_{0}}{\| V J^{k} V^{-1} b_{0}\|} \\ &=& \frac{ VJ^{k}V^{-1} \left( c_{1}v_{1} + c_{2}v_{2} + \cdots + c_{n}v_{n} \right)} {\| V J^{k} V^{-1} \left( c_{1}v_{1} + c_{2}v_{2} + \cdots + c_{n}v_{n} \right)\|} \\ &=& \frac{ VJ^{k}\left( c_{1}e_{1} + c_{2}e_{2} + \cdots + c_{n}e_{n} \right)} {\| V J^{k} \left( c_{1}e_{1} + c_{2}e_{2} + \cdots + c_{n}e_{n} \right) \|} \\ &=& \left( \frac{\lambda_{1}}{|\lambda_{1}|} \right)^{k} \frac{c_{1}}{|c_{1}|} \frac{ v_{1} + \frac{1}{c_{1}} V \left( \frac{1}{\lambda_1} J \right)^{k} \left( c_{2}e_{2} + \cdots + c_{n}e_{n} \right)} {\| v_{1} + \frac{1}{c_{1}} V \left( \frac{1}{\lambda_1} J \right)^{k} \left( c_{2}e_{2} + \cdots + c_{n}e_{n} \right) \| } \end{matrix}$
The expression above simplifies as $k \rightarrow \infty$
$\left( \frac{1}{\lambda_{1}} J \right)^{k} = \begin{bmatrix}[1] & & & & \\& \left( \frac{1}{\lambda_{1}} J_{2} \right)^{k}& & & \\& & \ddots & \\& & & \left( \frac{1}{\lambda_{1}} J_{m} \right)^{k} \\\end{bmatrix}\rightarrow\begin{bmatrix}1 & & & & \\& 0 & & & \\& & \ddots & \\& & & 0 \\\end{bmatrix}$ as $k \rightarrow \infty$.
The limit follows from the fact that the eigenvalue of $\frac{1}{\lambda_{1}} J_{i}$ is less than in 1 in magnitude, so $\left( \frac{1}{\lambda_{1}} J_{i} \right)^{k} \rightarrow 0$ as $k \rightarrow \infty$
It follows that:
$\frac{1}{c_{1}} V \left( \frac{1}{\lambda_1} J \right)^{k} \left( c_{2}e_{2} + \cdots + c_{n}e_{n} \right)\rightarrow 0$ as $k \rightarrow \infty$
Using this fact, bk can be written in a form that emphasizes its relationship with v1 when k is large:
$\begin{matrix}b_{k} &=& \left( \frac{\lambda_{1}}{|\lambda_{1}|} \right)^{k} \frac{c_{1}}{|c_{1}|} \frac{ v_{1} + \frac{1}{c_{1}} V \left( \frac{1}{\lambda_1} J \right)^{k} \left( c_{2}e_{2} + \cdots + c_{n}e_{n} \right)} {\| v_{1} + \frac{1}{c_{1}} V \left( \frac{1}{\lambda_1} J \right)^{k} \left( c_{2}e_{2} + \cdots + c_{n}e_{n} \right) \| } &=& e^{i \phi k} \frac{c_{1}}{|c_{1}|} v_{1} + r_{k}\end{matrix}$ where eiφ = λ1 / | λ1 | and $\| r_{k} \| \rightarrow 0$ as $k \rightarrow \infty$
The sequence $\left( b_{k} \right)$ 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 $\left(b_{k}\right)$ may not converge, bk 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. In Linear algebra, a Square matrix A is called diagonalizable if it is similar to a Diagonal matrix, i Suppose that λ1 is the dominant eigenvalue, so that | λ1 | > | λj | for j > 1.

The initial vector b0 can be written:

$b_0 = c_{1}v_{1} + c_{2}v_{2} + \cdots + c_{m}v_{m}.$

If b0 is chosen randomly (with uniform probability), then c1 ≠ 0 with probability 1. In Probability theory, one says that an event happens almost surely (a Now,

$\begin{matrix}A^{k}b_0 & = & c_{1}A^{k}v_{1} + c_{2}A^{k}v_{2} + \cdots + c_{m}A^{k}v_{m} \\& = & c_{1}\lambda_{1}^{k}v_{1} + c_{2}\lambda_{2}^{k}v_{2} + \cdots + c_{m}\lambda_{m}^{k}v_{m} \\& = & c_{1}\lambda_{1}^{k} \left( v_{1} + \frac{c_{2}}{c_{1}}\left(\frac{\lambda_{2}}{\lambda_{1}}\right)^{k}v_{2} + \cdots + \frac{c_{m}}{c_{1}}\left(\frac{\lambda_{m}}{\lambda_{1}}\right)^{k}v_{m}\right). \end{matrix}$

The expression within parentheses converges to v1 because | λj / λ1 | < 1 for j > 1. On the other hand, we have

$b_k = \frac{A^kb_0}{\|A^kb_0\|}.$

Therefore, bk converges to (a multiple of) the eigenvector v1. The convergence is geometric, with ratio

$\left| \frac{\lambda_2}{\lambda_1} \right|,$

where λ2 denotes the second dominant eigenvalue. In Mathematics, a geometric progression, also known as a geometric sequence, is a Sequence of Numbers where each term after the first is found 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 uses it to calculate the page rank of documents in their search engine. Google Inc is an American public corporation, earning revenue from advertising related to its Internet search, e-mail, online PageRank is a link analysis algorithm that assigns a numerical weighting to each element of a Hyperlinked set of documents such as the World Wide Web, [1]

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 A − 1. In Numerical analysis, inverse iteration is an iterative Eigenvalue algorithm. Other algorithms look at the whole subspace generated by the vectors bk. This subspace is known as the Krylov subspace. In Linear algebra the Krylov subspace generated by an n -by- n matrix A, and an n -vector b, is the subspace \mathcal{K}_n It can be computed by Arnoldi iteration or Lanczos iteration. In numerical Linear algebra, the Arnoldi iteration is an Eigenvalue algorithm and an important example of Iterative methods Arnoldi finds the The Lanczos algorithm is an iterative algorithm invented by Cornelius Lanczos that is an adaptation of power methods to find Eigenvalues and Eigenvectors