Page 137 - Compact Numerical Methods For Computers

126 Compact numerical methods for computers

10.3. THE JACOBI ALGORITHM FOR THE EIGENSOLUTIONS OF A
REAL SYMMETRIC MATRIX

Equation (10.1) immediately leads to
T
V AV = E (10.31)
(using V in place of X). The fact that a real symmetric matrix can be diagonalised
by its eigenvectors gives rise to a number of approaches to the algebraic
eigenvalue problem for such matrices. One of the earliest of these was suggested
by Jacobi (1846). This proposes the formation of the sequence of matrices
A ( 0 ) =A
(k+1) (k) T (k) (k) (10.32)
A =(V ) A V
(k)
where the V are the plane rotations introduced in §3.3. The limit of the
sequence is a diagonal matrix under some conditions on the angles of rotation.
(k)
Each rotation is chosen to set one off-diagonal element of the matrix A to zero.
In general an element made zero by one rotation will be made non-zero by
another so that a series of sweeps through the off-diagonal elements are needed to
reduce the matrix to diagonal form. Note that the rotations in equation (10.32)
preserve symmetry, so that there are n(n -1)/2 rotations in one sweep if A is of
order n.
Consider now the effect of a single rotation, equation (3.11), in the ij plane.
Then for m i, j
(10.33)
(10.34)
while
(10.35)
(10.36)
(10.37)

By allowing
(10.38)
and
(10.39)

the angle calculation defined by equations (3.22)-(3.27) will cause to be
zero. By letting

(10.40)

be the measure of the non-diagonal character of A (k) in a similar fashion to the
non-orthogonality measure (3.17), it is straightforward (if a little tedious) to show