- Licence
- CC BY-SA 4.0Adapted from en.wikibooks.org
- Languages
- English
- Topics
- Education
- Publications
- Linear Algebra
In practice, calculating eigenvalues and eigenvectors is a difficult problem.
Finding, and solving, the characteristic polynomial
of the large matrices often encountered in applications is too slow and too
hard.
Other techniques, indirect ones that avoid the characteristic polynomial,
are used.
Here we shall see such a method that is suitable for large matrices that are
"sparse" (the great majority of the entries are zero).
Suppose that the n \ × \ n matrix T has the n distinct eigenvalues{λ}_{1}, {λ}_{2}, ..., {λ}_{n}.
Then {ℝ}^{n} has a basis that is composed of the associated eigenvectors⟨ {\overset{→}{ζ}}_{1} , … , {\overset{→}{ζ}}_{n} ⟩.
For any \overset{→}{v} ∈ {ℝ}^{n}, where\overset{→}{v} = {c}_{1} {\overset{→}{ζ}}_{1} + … + {c}_{n} {\overset{→}{ζ}}_{n}, iterating T on \overset{→}{v}
gives these.
\begin{matrix}T \overset{→}{v} & = {c}_{1} {λ}_{1} {\overset{→}{ζ}}_{1} + {c}_{2} {λ}_{2} {\overset{→}{ζ}}_{2} + … + {c}_{n} {λ}_{n} {\overset{→}{ζ}}_{n} \\ {T}^{2} \overset{→}{v} & = {c}_{1} {λ}_{1}^{2} {\overset{→}{ζ}}_{1} + {c}_{2} {λ}_{2}^{2} {\overset{→}{ζ}}_{2} + … + {c}_{n} {λ}_{n}^{2} {\overset{→}{ζ}}_{n} \\ {T}^{3} \overset{→}{v} & = {c}_{1} {λ}_{1}^{3} {\overset{→}{ζ}}_{1} + {c}_{2} {λ}_{2}^{3} {\overset{→}{ζ}}_{2} + … + {c}_{n} {λ}_{n}^{3} {\overset{→}{ζ}}_{n} \\ & ⋮ \\ {T}^{k} \overset{→}{v} & = {c}_{1} {λ}_{1}^{k} {\overset{→}{ζ}}_{1} + {c}_{2} {λ}_{2}^{k} {\overset{→}{ζ}}_{2} + … + {c}_{n} {λ}_{n}^{k} {\overset{→}{ζ}}_{n}\end{matrix}
If one of the eigenvalues, say, {λ}_{1},
has a larger absolute value than any of the other eigenvalues
then its term will dominate the above expression.
Put another way, dividing through by {λ}_{1}^{k} gives this,
\frac{{T}^{k} \overset{→}{v}}{{λ}_{1}^{k}} = {c}_{1} {\overset{→}{ζ}}_{1} + {c}_{2} \frac{{λ}_{2}^{k}}{{λ}_{1}^{k}} {\overset{→}{ζ}}_{2} + … + {c}_{n} \frac{{λ}_{n}^{k}}{{λ}_{1}^{k}} {\overset{→}{ζ}}_{n}
and, because {λ}_{1} is assumed to have the largest absolute value,
as k gets larger the fractions go to zero.
Thus, the entire expression goes to {c}_{1} {\overset{→}{ζ}}_{1}.
That is (as long as {c}_{1} is not zero),
as k increases, the vectors {T}^{k} \overset{→}{v} will tend toward the direction of
the eigenvectors associated with the dominant eigenvalue,
and, consequently,
the ratios of the lengths | \ {T}^{k} \overset{→}{v} \ | / | \ {T}^{k − 1} \overset{→}{v} \ |
will tend toward that dominant eigenvalue.
For example, (sample computer code for this follows the exercises), because
the matrix
T = ( \begin{matrix}3 & 0 \\ 8 & − 1\end{matrix} )
is triangular, its eigenvalues are just the entries on the diagonal, 3
and − 1.
Arbitrarily taking \overset{→}{v} to have the components 1 and 1 gives
\begin{matrix}\overset{→}{v} & T \overset{→}{v} & {T}^{2} \overset{→}{v} & ⋯ & {T}^{9} \overset{→}{v} & {T}^{10} \overset{→}{v} \\ ( \begin{matrix}1 \\ 1\end{matrix} ) & ( \begin{matrix}3 \\ 7\end{matrix} ) & ( \begin{matrix}9 \\ 17\end{matrix} ) & ⋯ & ( \begin{matrix}19 \ 683 \\ 39 \ 367\end{matrix} ) & ( \begin{matrix}59 \ 049 \\ 118 \ 097\end{matrix} )\end{matrix}
and the ratio between the lengths of the last two is {}2.999 \ 9.
Two implementation issues must be addressed.
The first issue is that,
instead of finding the powers of T and applying them to \overset{→}{v},
we will compute {\overset{→}{v}}_{1} as T \overset{→}{v} and then compute {\overset{→}{v}}_{2} asT {\overset{→}{v}}_{1}, etc. (i.e., we never separately calculate{T}^{2}, {T}^{3}, etc.).
These matrix-vector products can be done quickly even if T is large,
provided that it is sparse.
The second issue is that,
to avoid generating numbers that are so large that they
overflow our computer's capability, we can normalize
the {\overset{→}{v}}_{i}'s at each step.
For instance, we can divide each {\overset{→}{v}}_{i} by its length
(other possibilities are to divide it by its largest component, or simply
by its first component).
We thus implement this method by generating
\begin{matrix}{\overset{→}{w}}_{0} & = {\overset{→}{v}}_{0} / | {\overset{→}{v}}_{0} | \\ {\overset{→}{v}}_{1} & = T {\overset{→}{w}}_{0} \\ {\overset{→}{w}}_{1} & = {\overset{→}{v}}_{1} / | {\overset{→}{v}}_{1} | \\ {\overset{→}{v}}_{2} & = T {\overset{→}{w}}_{2} \\ & ⋮ \\ {\overset{→}{w}}_{k − 1} & = {\overset{→}{v}}_{k − 1} / | {\overset{→}{v}}_{k − 1} | \\ {\overset{→}{v}}_{k} & = T {\overset{→}{w}}_{k}\end{matrix}
until we are satisfied.
Then the vector {\overset{→}{v}}_{k} is an approximation of an eigenvector, and
the approximation of the dominant eigenvalue is
the ratio | {\overset{→}{v}}_{k} | / | {\overset{→}{w}}_{k − 1} | = | {\overset{→}{v}}_{k} |.
One way we could be "satisfied"
is to iterate until our approximation of the eigenvalue settles down.
We could decide, for instance, to stop the iteration
process not after some fixed number of steps, but instead
when | {\overset{→}{v}}_{k} | differs from | {\overset{→}{v}}_{k − 1} |
by less than one percent, or when they agree up to the
second significant digit.
The rate of convergence is determined by the rate at which
the powers of | {λ}_{2} / {λ}_{1} | go to zero,
where {λ}_{2} is the eigenvalue of second largest norm.
If that ratio is much less than one then convergence is fast, but
if it is only slightly less than one then convergence can be quite slow.
Consequently, the method of powers
is not the most commonly used way of finding eigenvalues
(although it is the simplest one, which is why it is here as
the illustration of the possibility of computing eigenvalues
without solving the characteristic polynomial).
Instead, there are a variety of methods that generally work by first
replacing the given matrix T with another that is similar to it
and so has the same eigenvalues, but is in some reduced form
such as tridiagonal form: the only nonzero
entries are on the diagonal, or just above or below it.
Then special techniques can be used
to find the eigenvalues.
Once the eigenvalues are known,
the eigenvectors of T can be easily computed.
These other methods are outside of our scope.
A good reference is (Goult et al. 1975).
Exercises
Problem 1
Use ten iterations to estimate the largest eigenvalue of these
matrices, starting from the vector with components 1 and 2.
Compare the answer with the one obtained by solving the characteristic
equation.
( \begin{matrix}1 & 5 \\ 0 & 4\end{matrix} )( \begin{matrix}3 & 2 \\ − 1 & 0\end{matrix} )
Problem 2
Redo the prior exercise by iterating until| {\overset{→}{v}}_{k} | − | {\overset{→}{v}}_{k − 1} | has absolute value less than
0.01
At each step, normalize by dividing each vector by its length.
How many iterations are required?
Are the answers significantly different?
Problem 3
Use ten iterations to estimate the largest eigenvalue of these
matrices, starting from the vector with components 1, 2, and 3.
Compare the answer with the one obtained by solving the characteristic
equation.
( \begin{matrix}4 & 0 & 1 \\ − 2 & 1 & 0 \\ − 2 & 0 & 1\end{matrix} )( \begin{matrix}− 1 & 2 & 2 \\ 2 & 2 & 2 \\ − 3 & − 6 & − 6\end{matrix} )
Problem 4
Redo the prior exercise by iterating until| {\overset{→}{v}}_{k} | − | {\overset{→}{v}}_{k − 1} | has absolute value less than
0.01.
At each step, normalize by dividing each vector by its length.
How many iterations does it take?
Are the answers significantly different?
Problem 5
What happens if {c}_{1} = 0?
That is, what happens if the initial vector does not to have any
component in the direction of the relevant eigenvector?
Problem 6
How can the method of powers
be adopted to find the smallest eigenvalue?
This is the code for the computer algebra system Octave that was used to
do the calculation above.
(It has been lightly edited to remove blank lines, etc.)
Computer Code
>T=[3, 0;
8, -1]
T=
3 0
8 -1
>v0=[1; 2]
v0=
1
1
>v1=T*v0
v1=
3
7
>v2=T*v1
v2=
9
17
>T9=T**9
T9=
19683 0
39368 -1
>T10=T**10
T10=
59049 0
118096 1
>v9=T9*v0
v9=
19683
39367
>v10=T10*v0
v10=
59049
118096
>norm(v10)/norm(v9)
ans=2.9999
Remark: we are ignoring the power of Octave here;
there are built-in functions to automatically
apply quite sophisticated methods to find eigenvalues and eigenvectors.
Instead, we are using just the system as a calculator.
References
- Goult, R.J.; Hoskins, R.F.; Milner, J.A.; Pratt, M.J. (1975), Computational Methods in Linear Algebra, Wiley.
Where this page came from
This page was imported from Wikibooks. From “Linear Algebra” on Wikibooks, by its contributors, under CC BY-SA 4.0. Changed here: set as a page; navigation and edit links left out; each image under its own licence, credited in its caption.
Nobody has written it yet — it is the source material at a new address, which is why search engines are asked to skip it and why no one earns from it. It is up for grabs: take it on, and it is yours to rewrite and to earn from.
Comments
