7.4 Jacobi’s method 215
The importance of a similarity transformation lies in the fact that the resulting matrix has the
same eigenvalues, but the eigenvectors are in general different. To prove this we start with
the eigenvalue problem and a similarity transformed matrixB.
Ax=λx and B=STAS.We multiply the first equation on the left bySTand insertSTS=IbetweenAandx. Then we
get
(STAS)(STx) =λSTx, (7.4)
which is the same as
B
(
STx)
=λ(
STx)
The variableλis an eigenvalue ofBas well, but with eigenvectorSTx.
The basic philosophy is to
- either apply subsequent similarity transformations so that
STN...ST 1 AS 1 ...SN=D, (7.5)- or apply subsequent similarity transformations so thatAbecomes tridiagonal. Thereafter,
techniques for obtaining eigenvalues from tridiagonal matrices can be used.
Let us look at the first method, better known as Jacobi’s method or Given’s rotations.
7.4 Jacobi’s method
Consider an (n×n) orthogonal transformation matrix
S=
1 0 ... 0 0 ... 0 0
0 1 ... 0 0 ... 0 0
... ... ... ... ... ... 0 ...
0 0 ... cosθ 0 ... 0 sinθ
0 0 ... 0 1 ... 0 0
... ... ... ... ... ... 0 ...
0 0 ... 0 0 ... 1 0
0 0 ...−sinθ... ... 0 cosθ
with propertyST=S−^1. It performs a plane rotation around an angleθ in the Euclidean
n−dimensional space. It means that the matrix elements that differ from zero are given by
skk=sll=cosθ,skl=−slk=−sinθ,sii=−sii= 1 i 6 =k i 6 =l,A similarity transformation
B=STAS,
results in