Power iteration ($x_{k+1}=A{x}_k/\Vert A{x}_k{\Vert }_2$)

Power iteration finds a dominant eigenvalue and its eigenvector by repeatedly applying a matrix and rescaling the resulting vector. The essential idea is selective amplification: components along different eigenvectors grow at different rates, so one direction can eventually dominate. It is the computational form of the power method and is useful when applying a large sparse matrix to a vector is cheap but computing its whole spectral decomposition is expensive.

For a square matrix over the real numbers or complex numbers $A$, choose a unit vector $x_0$ and repeatHere $\Vert \cdot {\Vert }_2$ is the Euclidean norm. If $y_{k+1}=0$, stop before division: the current vector is an eigenvector for the zero eigenvalue, and this iteration cannot continue. Otherwise, in exact arithmetic,Repeated normalization keeps the stored vectors at manageable size without changing their directions; it does not guarantee that an individual multiplication cannot exceed the range of floating-point arithmetic. The dominant eigenvalue means largest modulus, which need not mean largest signed real value.^[ref]

Consider the symmetric matrix and initial unit vectorIts orthonormal eigenbasis consists of $u_1=(1,1{)}^T/\sqrt{2}$ and $u_2=(1,-1{)}^T/\sqrt{2}$, with eigenvalues $3$ and $1$. Since $x_0=(u_1+u_2)/\sqrt{2}$, direct multiplication givesThe first unnormalized vectors are $(1,0{)}^T$, $(2,1{)}^T$, $(5,4{)}^T$, and $(14,13{)}^T$. If ${\theta }_k$ is the acute angle from the line spanned by the dominant eigenvector, then $\tan {\theta }_k=3^{-k}$. Every application divides the unwanted-to-wanted component ratio by three: normalization changes lengths, while the spectral gap selects the direction.

The right panel compares the power iteration direction error, Rayleigh quotient error, and eigenpair residual. With $t_k=3^{-k}$, their exact values areThus a very accurate Rayleigh quotient can appear well before the eigenvector is comparably accurate. This is an example of quadratic Rayleigh-quotient improvement for the power method.

Suppose $A\in {\mathbb{C}}^{n\times n}$ is a diagonalizable matrix, $n\ge 2$, with an eigenbasis $v_1,\dots ,v_n$ and spectral decompositionAssume the dominant eigenvalue ${\lambda }_1$ is a simple eigenvalue andThen the normalized power iteration approaches the one-dimensional eigenspace of ${\lambda }_1$. Its asymptotic direction-error bound has factor $\gamma =|{\lambda }_2/{\lambda }_1|<1$. This spectral gap is a gap in modulus: if $g=|{\lambda }_1|-|{\lambda }_2|$, then $\gamma =1-g/|{\lambda }_1|$. A small relative gap gives slow convergence.^[ref]

The short proof is the exact eigenbasis identityThe remaining sum has norm bounded by a constant times ${\gamma }^k$. This proves convergence of direction, allowing a changing sign or complex factor. A tiny $c_1$ or a poorly conditioned, nonorthogonal eigenbasis can delay visible convergence: the condition number of $V$ affects constants, while $\gamma$ controls the eventual rate. The bound need not be an equality; if the initial coefficient of the second-largest eigenvalue vanishes, the active spectrum of the power method gives a faster rate. When $\gamma =0$, all unwanted components disappear after one multiplication.^[ref]

The hypothesis is $c_1=(V^{-1}{x}_0{)}_1\ne 0$, not an ordinary nonzero inner product with the right eigenvector. Let $w_1^{\ast }$ be the first row of $V^{-1}$, a left eigenvector normalized so $w_1^{\ast }{v}_j$ is $1$ for $j=1$ and $0$ otherwise; $\ast$ denotes conjugate transpose. Then $c_1=w_1^{\ast }{x}_0$. For a Hermitian matrix, choose an orthonormal eigenbasis and the criterion becomes $v_1^{\ast }{x}_0\ne 0$: the starting vector must be nonorthogonal to the dominant eigenvector. For a general diagonalizable matrix, the nonorthogonal eigenbasis makes these two tests different, as illustrated under power iteration failure cases.

For a unit vector $u$ spanning the target eigenspace and a normalized iterate $x_k$, defineThis is the norm of the component in the orthogonal complement of $u$, equivalently the sine of the acute angle to its line. It ignores the arbitrary sign or complex unit factor of an eigenvector. Under power iteration convergence for a diagonalizable matrix, ${\epsilon }_k=O({\gamma }^k)$ in Big O notation. The orthogonal projection defines how we measure direction; it does not assume that the eigenbasis of $A$ is orthogonal. In computation, the projection form avoids subtracting nearly equal numbers inside the square root.

Under power iteration convergence for a diagonalizable matrix, take $v_1=u_1$ to be a unit vector. The displayed formula describes both the dominant eigenvector direction and its rotating complex unit factor. With real data and a positive dominant eigenvalue, $x_k$ converges to $u_1$ or $-u_1$ according to the sign of $c_1$. With a negative dominant eigenvalue, consecutive vectors approach opposite signs even though their power iteration direction error tends to zero.

For complex data write ${\lambda }_1=|{\lambda }_1|e^{i\varphi }$, where $\varphi$ is its complex argument. The leading factor turns by $e^{i\varphi }$ per step, so the vectors generally do not converge. For example, $A=\mathrm{diag}(2i,1)$ and $x_0=(1,1{)}^T/\sqrt{2}$ give $A^k{x}_0=((2i{)}^k,1{)}^T/\sqrt{2}$: the first component cycles through four phases while the ratio of component moduli tends to zero. Its power iteration direction error is $2^{-k}/\sqrt{1+2^{-2k}}$. Multiplying $x_k$ by $e^{-i(\arg c_1+k\varphi )}$ gives a sequence converging to $u_1$.

A stopping rule based only on $\Vert x_{k+1}-x_k{\Vert }_2$ therefore rejects successful sign-alternating iterations. A comparison invariant under complex unit factors isEven this comparison can be small for a slowly changing wrong mixture; the eigenpair residual supplies a separate diagnostic.

For each unit vector iterate compute the Rayleigh quotient ${\rho }_k=x_k^{\ast }A{x}_k$ and the eigenpair residual $r_k=A{x}_k-{\rho }_k{x}_k$. Use the same multiplication $A{x}_k$ for both diagnostics and the next normalized iterate. For any complex matrix, this Rayleigh quotient minimizes $\Vert A{x}_k-\mu x_k{\Vert }_2$ over complex scalars $\mu$, because $x_k^{\ast }{r}_k=0$. Under power iteration convergence for a diagonalizable matrix, ${\rho }_k\to {\lambda }_1$ and $\Vert r_k{\Vert }_2\to 0$, even when the vectors alternate signs or phases.^[ref]

A dimensionless stopping quantity iswhen the denominator is positive; $\Vert A{\Vert }_2$ is the operator norm, and a known upper bound may replace it if computing it is costly. A small eigenpair residual certifies a small backward error of an approximate eigenpair, but does not establish that the eigenvalue found is dominant.

For a Hermitian matrix with orthonormal eigenbasis $u_j$, write $x_k={\sum }_j{a}_j{u}_j$. Then the independently useful identityshows that some eigenvalue lies within $\Vert r_k{\Vert }_2$ of ${\rho }_k$. If a specific target eigenvalue ${\lambda }_1$ is separated from all the others by ${\delta }_k={\min }_{j>1}|{\lambda }_j-{\rho }_k|>0$, it also gives ${\epsilon }_k\le \Vert r_k{\Vert }_2/{\delta }_k$. This separation is measured from the computed Rayleigh quotient; it differs from the dominant-modulus spectral gap. For a nonnormal matrix, the same orthogonal expansion is unavailable and a small eigenpair residual alone need not imply a comparably small distance to the spectrum.

A tied largest modulus can prevent even direction convergence. With $D=\mathrm{diag}(2,-2)$ and $x_0=(1,1{)}^T/\sqrt{2}$,The two directions form a cycle; neither is an eigenvector. There is no dominant-modulus spectral gap. A tied modulus is not a universal failure: an initial eigenvector remains on its line, and $A=2I$ preserves every direction. Subspace iteration addresses a separated cluster by targeting a dominant invariant subspace instead of one eigenvector.

An orthogonal start can fail despite a strict spectral gap. For $A=\left(\begin{array}{cc}2& 1\\ 1& 2\end{array}\right)$ and $x_0=(1,-1{)}^T/\sqrt{2}$, the dominant component is zero, so $A{x}_0=x_0$ and every iterate equals $x_0$. The Rayleigh quotient is exactly $1$ and the eigenpair residual is zero, although the dominant eigenvalue is $3$. Exact arithmetic never creates a missing component.^[ref]

The third panel contrasts these failures with $N=\mathrm{diag}(-3,1)$, $x_0=(1,1{)}^T/\sqrt{2}$, for whichHere the horizontal eigenvector direction converges with a strict spectral gap, while the normalized vectors alternate signs. This is the successful direction convergence described under sign and phase in power iteration.

For a nonorthogonal eigenbasis, even the word “orthogonal” must be used carefully. The diagonalizable matrix $C=\left(\begin{array}{cc}3& 2\\ 0& 1\end{array}\right)$ has right eigenvectors $v_1=(1,0{)}^T$, $v_2=(-1,1{)}^T$, and dominant left eigenvector $w_1=(1,1{)}^T$. For $x_0=(a,b{)}^T$, the dominant coefficient is $c_1=w_1^T{x}_0=a+b$. The starting vector $v_2$ is nonorthogonal to $v_1$ but stays at the smaller eigenvalue $1$; $(0,1{)}^T$ is orthogonal to $v_1$ but has $c_1=1$ and converges to the dominant direction. The left eigenvector test, not the right-eigenvector inner product, controls the outcome.

A random vector drawn from a continuous probability distribution with a probability density function on the full real or complex vector space has $c_1\ne 0$ with probability one. This avoids the exact missing-component hyperplane, but does not guarantee a large component or fast convergence. Floating-point arithmetic may seed a missing component, yet a structurally preserved zero can remain zero, so accidental perturbations are not a convergence guarantee.