Page 255 - Compact Numerical Methods For Computers

242 Compact numerical methods for computers
we may be tempted to proceed with inverse iteration via conjugate gradients for
any real symmetric problem.
Ruhe and Wiberg (1972) warn against allowing too large an increase in the
norm of y in a single step of algorithm 24, and present techniques for coping with
the situation. Of these, the one recommended amounts only to a modification of
the shift. However, since Ruhe and Wiberg were interested in refining eigenvec-
tors already quite close to exact, I feel that an ad hoc shift may do just as well if a
sudden increase in the size of the vector y, that is, a large step length k, is
observed.
Thus my suggestion for solution of the generalised symmetric matrix eigenvalue
problem by inverse iteration using the conjugate gradients algorithm 24 is as
follows.
(i) Before each iteration, the norm (any norm will do) of the residual vector

(19.21)
r =(A- eB)x
should be computed and this norm compared to some user-defined tolerance as a
convergence criterion. While this is less stringent than the test made at STEPs 14
and 15 of algorithm 10, it provides a constant running check of the closeness of the
current trial solution (e,x) to an eigensolution. Note that a similar calculation
could be performed in algorithm 10 but would involve keeping copies of the
matrices A and B in the computer memory. It is relatively easy to incorporate a
restart procedure into inverse iteration so that tighter tolerances can be entered
without discarding the current approximate solution. Furthermore, by using b=0
as the starting vector in algorithm 24 at each iteration and only permitting n
conjugate gradient steps or less (by deleting STEP 12 of the algorithm), the
matrix-vector multiplication of STEP 1 of algorithm 24 can be made implicit in the
computation of residuals (19.21) since
c=Bx. (19.22)
Note that the matrix H to be employed at STEP 5 of the algorithm is

(19.23)
H= (A-sB) =A' .
(ii) To avoid too large an increase in the size of the elements of b, STEP 7 of
algorithm 24 should include a test of the size of the step-length parameter k. I use
the test
If ABS(k)>1/SQR(eps), then . . .

where eps is the machine precision, to permit the shift s to be altered by the user. I
remain unconvinced that satisfactory simple automatic methods yet exist to
calculate the adjustment to the shift without risking convergence to an eigensolu-
tion other than that desired. The same argument applies against using the
Rayleigh quotient to provide a value for the shift s. However, since the Rayleigh
quotient is a good estimate of the eigenvalue (see § 10.2, p 100), it is a good idea to
compute it.
(iii) In order to permit the solution b of
(19.24)
Hb = (A-s B) b=Bx=c