Graphics Programs Reference
In-Depth Information
c=
-3.7417
9.1309
4.7716
P=
1.0000
0
0
0
0
-0.5345
-0.2551
0.8057
0
-0.8018
-0.1484
-0.5789
0
0.2673
-0.9555
-0.1252
9.5
Eigenvalues of Symmetric Tridiagonal Matrices
Sturm Sequence
Inprinciple, the eigenvalues of amatrix
A
can be determined by finding the roots of
the characteristicequation
0. This methodis impracticalfor large matrices
since the evaluation of the determinant involves
n
3
|
A
−
λ
I
| =
3multiplications. However, if the
matrix istridiagonal(we also assume ittobesymmetric), its characteristic polynomial
/
d
1
−
λ
c
1
0
0
···
0
c
1
d
2
−
λ
c
2
0
···
0
0
c
2
d
3
−
λ
c
3
···
0
P
n
(
λ
)
= |
A
−
λ
I
| =
0
0
c
3
d
4
−
λ
···
0
.
.
.
.
.
.
.
.
0
0
...
0
c
n
−
1
d
n
−
λ
can becomputedwith only3(
n
−
1) multiplications using the following sequence of
operations:
P
0
(
λ
)
=
1
λ
=
d
1
−
λ
P
1
(
)
(9.49)
c
i
−
1
P
i
−
2
(
P
i
(
λ
)
=
(
d
i
−
λ
)
P
i
−
1
(
λ
)
−
λ
),
i
=
2
,
3
,...,
n
The polynomials
P
0
(
λ
)
,
P
1
(
λ
)
,...,
P
n
(
λ
)form a
Sturm sequence
thathas the fol-
lowing property:
The number of sign changes in the sequence
P
0
(
a
)
,
P
1
(
a
)
,...,
P
n
(
a
) isequaltothe
number of roots of
P
n
(
)that aresmaller than
a
. If amember
P
i
(
a
) of the sequence
iszero, its sign istobetaken opposite to thatof
P
i
−
1
(
a
).
λ
As we see shortly, Sturm sequence propertymakes it relatively easy to bracket the
eigenvalues of a tridiagonal matrix.
Search WWH ::
Custom Search