| Franz J. Vesely > CompPhys Tutorial > Linear Algebra |
2.4 Eigenvalues and EigenvectorsGiven a quadratic matrix $A$, the eigenvalues $\lambda_{i}$ are defined by
$
\left| { A}-\lambda_{i} { I} \right| = 0 \;\;\;\; (i=1, \dots N)
$
and the corresponding eigenvectors $\vec{a}_{i}$ are
$
\left[ { A} - \lambda_{i} { I} \right] \cdot \vec{a}_{i} = 0 ,
$
Normally one uses library subroutines, such as NAG F01xxx or ESSL SGEEV. If only a few eigenvalues and the associated eigenvectors are needed then simple iterative procedures may be used. Subsections 2.4.1 Largest Eigenvalue and Related EigenvectorRegard the $N$ eigenvectors $\vec{a}_{i}$ of $A$ as the base vectors in $N$-space. Then any $N$-vector may be written
$
\vec{x}_{0}= \sum \limits_{i=1}^{N} c_{i} \vec{a}_{i}
$
with appropriate coefficients $c_{i}$. Let $\vec{a}_{m}$ be the eigenvector corresponding to the largest (by absolute value) eigenvalue $\lambda_{m}$. Multiply $\vec{x}_{0}$ several times by ${ A}$, each time normalizing the result:
$
\vec{x}_{k}'={ A} \cdot \vec{x}_{k-1}
\;\;\; \Longrightarrow \;\;\;
\vec{x}_{k}=
\frac{\textstyle \vec{x}_{k}'}{\textstyle \left| \vec{x}_{k}' \right| }
$
After a few iterations, then,
$
\vec{x}_{k} \propto \sum \limits_{i=1}^{N} c_{i} \lambda_{i}^{k} \vec{a}_{i}
\approx c_{m} \lambda_{m}^{k} \vec{a}_{m}
$
To obtain the eigenvalue $\lambda_{m}$, use
$
\lambda_{m} = \frac{\textstyle {x_{\beta}'}^{(k)}}{\textstyle x_{\beta}^{(k-1)}}
\;\;\;\;\; {\rm or}\;\;\;\;\;
\lambda_{m} = \vec{x}_{k+1} \cdot \vec{x}_{k}'
$
where ${x_{\beta}'}^{(k)}$ is any cartesian component of the unnormalized vector $\vec{x}_{k}'$. EXAMPLE: Let
$
{ A}=\left( \begin{array}{cc}3&1\\\\2&4\end{array} \right)
$
and use
$
\vec{x}_{0}=\left( \begin{array}{r} \sqrt{2}/2 \\ \\ \sqrt{2}/2 \end{array} \right)
$
choose as the starting vector. The iterated and normalized vectors are
$
\vec{x}_{1}=\left( \begin{array}{r} 0.555 \\ \\0.832 \end{array} \right)\; ; \;\vec{x}_{2}=\left(
\begin{array}{r} 0.490 \\ \\0.872 \end{array} \right)\; ; \;
\vec{x}_{3}=\left( \begin{array}{r} 0.464 \\ \\0.886 \end{array} \right)\; ; \dots
$
From $\vec{x}_{3}$ and the unnormalized
$
\vec{x}_{4}'=\left( \begin{array}{r} 2.279 \\ \\4.471 \end{array} \right)
$
we find $\lambda_{m}=4.907$. The exact solution is
$
\vec{a}_{m}=\left( \begin{array}{r} 0.45 \\ \\0.90 \end{array} \right) \;\; {\rm and} \;\; \lambda_{m}=5 .
$
2.4.2 Arbitrary Eigenvalue/-vector: Inverse IterationTask: Find the eigenvalue $\lambda_{n}$ nearest to some given number $\lambda$.Method: Start with arbitrary vector $\vec{x}_{0}$, and proceed:
$
\vec{x}_{k}'= \left[ { A} - \lambda { I} \right]^{-1}
\cdot \vec{x}_{k-1}
\;\;\;\; \Longrightarrow \;\;\;\;
\vec{x}_{k}=
\frac{\textstyle \vec{x}_{k}'}{\textstyle \left| \vec{x}_{k}' \right| }
$
After a few iterations the vector
$
\vec{x}_{k} \propto \sum \limits_{i=1}^{N} c_{i} \left[ \lambda_{i} - \lambda
\right]^{-k} \vec{a}_{i}
$
will approach
$
\vec{x}_{k} \rightarrow c_{n} \left[ \lambda_{n} - \lambda
\right]^{-k} \vec{a}_{n}
$
To evaluate $\lambda_{n}$, use
$
\lambda_{n} - \lambda =
\frac{\textstyle {x_{\beta}}^{(k)}}{\textstyle {x_{\beta}'}^{(k-1)}}
\;\;\;\;\; {\rm or}\;\;\;\;\;
\lambda_{n} = \lambda
+ \frac{\textstyle 1}{\textstyle \vec{x}_{k-1} \cdot \vec{x}_{k}'}
$
EXAMPLE: Use ${ A}$ as before, but search in the vicinity of $\lambda=1$:
$
\left[ { A} - \lambda { I} \right]^{-1} = \frac{\textstyle 1}{\textstyle 4}
\left( \begin{array}{cc}3&-1\\\\-2&2\end{array} \right)
$
Starting out from
$
\vec{x}_{0}=\left( \begin{array}{r} 1 \\ \\0 \end{array} \right)
$
we get
$
\vec{x}_{1}=\left( \begin{array}{r} 0.832 \\ \\-0.555 \end{array} \right); \vec{x}_{2}=\left( \begin{array}{r}
0.740 \\ \\-0.673 \end{array} \right);
\vec{x}_{3}=\left( \begin{array}{r} 0.715 \\ \\-0.699 \end{array} \right); \vec{x}_{4}=\left( \begin{array}{r}
0.709 \\ \\-0.705 \end{array} \right)\dots
$
From
$
\vec{x}_{5}'=\left( \begin{array}{r} 0.708 \\ \\-0.707 \end{array} \right)
$
we have $\vec{x}_{5}' \cdot \vec{x}_{4}=1.0015$, yielding $\lambda_{n}=2.001$. The exact eigenvalues are $5$ and $2$; the eigenvector corresponding to $\lambda=2$ is
$
\vec{a}=\left( \begin{array}{r} 0.707 \\ \\-0.707 \end{array} \right)
$
vesely 2005-10-10
|