<< numerical_analysis

Eigenvalues

1. Introduction

Recall that for matix $A$, if $A\mathit{v}=\lambda \mathit{v}$, we define $\lambda$ as the eigenvalue and $\mathit{v}$ as the corresponding eigenvector of $A$.

To compute the eigenvalues and eigenvectors by definition, we need to solve equation $|\lambda I-A|=0$. The order of this equation is at most the order of matrix. For instance, to compute the eigenvalue of $A=\left[\begin{array}{cc}0& 1\\ 1& 1\end{array}\right]$, we must solve the euqation $$\left|\begin{array}{cc}\lambda & 1\\ 1& \lambda -1\end{array}\right|=\lambda (\lambda -1)-1=0$$ However, Abel–Ruffini theorem states that there is no solution in radicals to general polynomial equations of degree five or higher with arbitrary coefficients. Hence computing the eigenvalue/eigenvector by definition is not an universal approach.

The dominant eigenvalue, or largest magnitude eigenvalue of $A$ is an eigenvalue $\lambda$ whose magnitude is greater than all other eigenvalues. If it exists, an eigenvector associated to $\lambda$ is called a dominant eigenvector.

The dominant eigenvalues is much more significant than others in many practical problems. For instance, whether the iteration matrix converges when solving linear equations depends on the spectral radius (a.k.a. dominant eigenvalue) of matix.

Power method is one of the numerical technique to compute dominant eigenvalue, and based on which we developed inverse power method to compute smallest magnitude eigenvalue.

2. Power Method

# Power Method Introduction

Any vector $X^{(0)}$ (as the initial vector) can be expressed by $n$ linear independent eigenvector of $A$ $$X^{(0)}={\alpha }_1{\mathit{v}}_1+{\alpha }_2{\mathit{v}}_2+\cdots +{\alpha }_n{\mathit{v}}_n$$

And the multiplication $A{X}^{(0)}$ can be expressed by $$\begin{array}{rl}{X}^{(1)}& =A{X}^{(0)}\\ & =A({\alpha }_1{\mathit{v}}_1+{\alpha }_2{\mathit{v}}_2+\cdots +{\alpha }_n{\mathit{v}}_n)\\ & =A{\alpha }_1{\mathit{v}}_1+A{\alpha }_2{\mathit{v}}_2+\cdots +A{\alpha }_n{\mathit{v}}_n\\ & ={\lambda }_1{\alpha }_1{\mathit{v}}_1+{\lambda }_2{\alpha }_2{\mathit{v}}_2+\cdots +{\lambda }_n{\alpha }_n{\mathit{v}}_n\end{array}$$

Applying mathematical induction , we have $$X^{(k)}=A{X}^{(k-1)}={\lambda }_1^k{\alpha }_1{\mathit{v}}_1+{\lambda }_2^k{\alpha }_2{\mathit{v}}_2+\cdots +{\lambda }_n^k{\alpha }_n{\mathit{v}}_n$$ This expression indicates that how $X^{(k)}$ change when iterating depends on the distribution of eigenvalues. We’ll discuss two simple cases.

# Two Cases when Applying Power Method

Case 1. If the ratio ${\displaystyle \frac{x^{(k+1)}}{x^{(k)}}}$ converges, the largest magnitude eigenvalue is unique and is a simple root. The dominant eigenvalue and the dominant eigenvector can be computed by $$\{\begin{array}{l}{\lambda }_1\approx {\displaystyle \frac{x_i^{(k+1)}}{x_i^{(k)}}},i=1,2,\dots ,n\\ {\mathit{v}}_1\approx X^{(k)}\end{array}$$

Proof. For the unique dominant eigenvalue ${\lambda }_1$, $$\begin{array}{rl}{X}^{(k)}& ={\lambda }_1^k{\alpha }_1{\mathit{v}}_1+{\lambda }_2^k{\alpha }_2{\mathit{v}}_2+\cdots +{\lambda }_n^k{\alpha }_n{\mathit{v}}_n\\ & ={\lambda }_1^k[{\lambda }_1^k{\alpha }_1{\mathit{v}}_1+{\left(\frac{{\lambda }_2}{{\lambda }_1}\right)}^k{\alpha }_2{\mathit{v}}_2+\cdots +{\left(\frac{{\lambda }_n}{{\lambda }_1}\right)}^k{\alpha }_n{\mathit{v}}_n]\end{array}$$ For sufficiently large $k$, we have $\left|{\left({\displaystyle \frac{{\lambda }_i}{{\lambda }_1}}\right)}^k\right|\to 0$ for $i\ne 1$ since ${\lambda }_1$ is the dominant eigenvalue. Hence $$\begin{array}{rl}{X}^{(k)}& \approx {\lambda }_1^k{\alpha }_1{\mathit{v}}_1\\ X^{(k+1)}& \approx {\lambda }_1^{k+1}{\alpha }_1{\mathit{v}}_1={\lambda }_1{\lambda }^k{\alpha }_1{\mathit{v}}_1={\lambda }_1{X}^{(k)}\end{array}$$

Case 2. If the ratio ${\displaystyle \frac{x^{(k+1)}}{x^{(k)}}}$ does not converges but ${\displaystyle \frac{x^{(2k+2)}}{x^{(2k)}}}$ does, then dominant eigenvalues are the real roots with different signs. The dominant eigenvalue and eigenvector can be computed by $$\{\begin{array}{l}{\lambda }_1=\sqrt{{\displaystyle \frac{x_1^{(k+2)}}{x_i^{(k)}}}},i=1,2,\dots ,n\\ {\mathit{v}}_1=X^{(k+1)}+{\lambda }_1{X}^{(k)}\\ {\mathit{v}}_2=X^{(k+1)}-{\lambda }_1{X}^{(k)}\end{array}$$

Proof. For two dominant eigenvalues ${\lambda }_1,{\lambda }_2$ and ${\lambda }_1=-{\lambda }_2$ $$\begin{array}{rl}{X}^{(k)}& ={\lambda }_1^k{\alpha }_1{\mathit{v}}_1+{\lambda }_2^k{\alpha }_2{\mathit{v}}_2+\cdots +{\lambda }_n^k{\alpha }_n{\mathit{v}}_n\\ & ={\lambda }_1^k[{\lambda }_1^k{\alpha }_1{\mathit{v}}_1+(-1{)}^k{\alpha }_2{\mathit{v}}_2+{\left(\frac{{\lambda }_3}{{\lambda }_1}\right)}^k{\alpha }_3{\mathit{v}}_n+\cdots +{\left(\frac{{\lambda }_n}{{\lambda }_1}\right)}^k{\alpha }_n{\mathit{v}}_n]\end{array}$$ For sufficiently large $k$, we have $$\begin{array}{rl}{X}^{(k)}& \approx {\lambda }_1^k({\alpha }_1{\mathit{v}}_1+(-1{)}^k{\alpha }_2{\mathit{v}}_2)\\ X^{(k+1)}& \approx {\lambda }_1^{k+1}({\alpha }_1{\mathit{v}}_1+(-1{)}^{k+1}{\alpha }_2{\mathit{v}}_2)\\ X^{(k+2)}& \approx {\lambda }_1^{k+2}({\alpha }_1{\mathit{v}}_1+(-1{)}^{k+2}{\alpha }_2{\mathit{v}}_2)\end{array}$$

Those trends that do not fit the two cases above require other special processings.

# Normalized Power Method

If the dominant eigenvalue is larger or smaller than $1$, some components of $X^{(k)}$ will increase or decrease continuously when iterating, which leads to the precision problem due to IEEE754. Hence we can normalize the vector after each step: $$\begin{gathered} Y_0=\frac{X^{(0)}}{{\Vert X^{(0)}\Vert }_{\mathrm{\infty }}} \\ \{\begin{array}{l}{X}^{(k+1)}=A{Y}^{(k)}\\ Y^{(k+1)}={\displaystyle \frac{X^{(k+1)}}{{\Vert X^{(k+1)}\Vert }_{\mathrm{\infty }}}}\end{array} \end{gathered}$$ The normalization process gurantees ${\Vert Y^{(k)}\Vert }_{\mathrm{\infty }}=1$, that is, the component that represents dominant eigenvalue of $A$ remains $\pm 1$.

There are three cases for normalized power method:

1. If $\{X^k\}$ converges, there is unique positive dominant eigenvalue $$\{\begin{array}{l}{\displaystyle {\lambda }_1\approx \underset{1\le i\le n}{max}|x_i^{(k)}|=|x_j^{(k)}|}\\ {\mathit{v}}_1\approx Y^{(k)}\end{array}$$

2. If $\{X^{(2k)}\},\{X^{(2k+1)}\}$ converges to two opposite vectors, there is unique negative dominant eigenvalue $$\{\begin{array}{l}{\displaystyle {\lambda }_1\approx -\underset{1\le i\le n}{max}|x_i^{(k)}|=-|x_j^{(k)}|}\\ {\mathit{v}}_1\approx Y^{(k)}\end{array}$$

3. If $\{X^{(2k)}\},\{X^{(2k+1)}\}$ converges to two different vectors, there are two different dominant eigenvectors with opposite sign. For sufficiently large $k$, we exectue one more unnormalized operation $X^{(k+1)}=A{X}^{(k)}=A^2{Y}^{(k-1)}$, then $$\{\begin{array}{l}{\lambda }_1\approx {\displaystyle \sqrt{\frac{x_i^{(k+1)}}{y_i^{(k-1)}}}}\\ {\lambda }_2=-{\lambda }_1\\ {\mathit{v}}_1=X^{(k+1)}+{\lambda }_1{X}^{(k)}\\ {\mathit{v}}_2=X^{(k+1)}-{\lambda }_1{X}^{(k)}\end{array}$$

4. It requires special pocessing if $\{X^{(k)}\}$ does not fit any cases mentioned above.

3. Inverse Power Method

Inverse power method is used to compute the smallest magnitude eigenvalue.

In equation $$A\mathit{v}=\lambda \mathit{v}$$ we multiple $A^{-1}$ on both sides: $$A^{-1}\mathit{v}={\lambda }^{-1}\mathit{v}$$ That is, the smallest magnitude eigenvalue of $A$ is exactly the reciprocal of dominant eigenvalue of $A^{-1}$.

In practice, we do apply power method after computing $A^{-1}$ but keep solving equation $$A{X}^{(k+1)}=X^{(k)}$$ decomposition method is applied to decompose $A=LU$ first then we solve $$\{\begin{array}{l}L{Z}^{(k+1)}=X^{(k)}\\ U{X}^{(k+1)}=Z^{(k+1)}\end{array}$$ We can also normalize the inverse power method as well to avoid the precision problem: $$\{\begin{array}{l}{Y}^{(k)}={\displaystyle \frac{X^{(k)}}{{\Vert X^{(k)}\Vert }_{\mathrm{\infty }}}}\\ A{X}^{(k+1)}=Y^{(k)}\end{array}$$