Section 5.2 The Power method
The most common situation in applications is the determination of the eigenvalues of some symmetric positive-definite matrix, so from now on we assume we have such a matrix. The power method is a very simple iterative method able to evaluate numerically the largest eigenvalue in absolute value of a matrix \(A\) (and so also its smallest one, which is the inverse of the largest eigenvalue of its inverse \(A^{-1}\)). We call this eigenvalue the dominant eigenvalue of \(A\text{.}\) Denote by \(\{e_1,\dots,e_n\}\) a (unknown!) basis of eigenvectors, so that \(Ae_i=\lambda_ie_i\text{,}\) and take a generic vector \(v=v_1e_1+\dots+v_ne_n\) (generic means that no \(v_i\) component is zero). Then
\begin{equation*}
A^k(v) = v_1\lambda^k_1e_1+\dots+v_n\lambda^k_ne_n
\end{equation*}
The algorithm. If it happens that \(\lambda_n\) is larger than all other eigenvalues, then \(A^k(v)\simeq\lambda^k_ne_n\) and this approximation gets better and better with higher and higher powers of \(A\text{.}\) We exploit this fact in the following iterative algorithm: - Choose a random vector \(v_0\) and set some threshold \(\epsilon\text{;}\)
- \(\hbox{until }\|v-vold\|>\epsilon\)
- \(\displaystyle vold = v\)
- \(\displaystyle z = Av\)
- \(\displaystyle v = z/\|z\|\)
- end
\begin{equation*}
\frac{v^TAv}{v^Tv}
\end{equation*}
is the eigenvalue of highest modulus and \(v\) is one of its eigenvectors. In essence, this is exactly the method used by google to rank web pages when a user searches for keywords!
An example