Graphics Programs Reference
In-Depth Information
L
d
2
i
3
dt
2
dt
2
L
d
2
i
3
dt
2
dt
2
d
2
i
2
d
2
i
4
3
C
i
3
=
−
+
−
+
0
L
d
2
i
4
dt
2
dt
2
d
2
i
3
L
d
2
i
4
dt
2
4
C
i
4
=
−
+
+
0
22.
Several iterative methodsexist for finding the eigenvalues of amatrix
A
. Oneof
these is the
LR method
, which requires the matrix to besymmetric and positive
definite. Its algorithmvery simple:
Let
A
0
=
A
do with
i
,...
Use Choleski's decomposition
A
i
=
=
0
,
1
,
2
L
i
L
i
to compute
L
i
L
i
L
i
Form
A
i
+
1
=
end do
It can be shown that the diagonal elements of
A
i
+
1
converge to the eigenvalues of
A
.Write aprogram that implements the LR method and test it with
⎡
⎣
⎤
⎦
4 31
3 4 2
123
=
A
9.4
Householder Reduction to Tridiagonal Form
It was mentionedbeforethatsimilarity transformationscan be used to transform an
eigenvalue problem to a form that iseasier to solve. The most desirable of the “easy”
forms is, of course, the diagonalform that results from the Jacobi method. However,
the Jacobi methodrequires about 10
n
3
to 20
n
3
multiplications, so that the amountof
computationincreases very rapidlywith
n
.We are generallybetter off by reducing the
matrix to the tridiagonalform, which can be done in precisely
n
2 transformations
by the Householdermethod. Once the tridiagonalform is achieved, westill haveto
extract the eigenvalues and the eigenvectors, but there are effective meansofdealing
with that, as we see in the next article.
−
Householder Matrix
Householder'stransformationutilizes the
Householder matrix
uu
T
H
Q
=
I
−
(9.36)
Search WWH ::
Custom Search