Page 257 - Compact Numerical Methods For Computers

244 Compact numerical methods for computers
If
e >e >. . .>e n (19.31)
2
1
then the minimum value of R is e and occurs when x is proportional to f . The
n n
maximum value is e . Alternatively, this value can be obtained via minimisation of
1
-R. Furthermore, if B is the identity, then minimising the Rayleigh quotient
T
T
R'=x (A-k1 )2x/x x (19.32)
n
will give the eigensolution having its eigenvalue closest to k.
While any of the general methods for minimising a function may be applied to
this problem, concern for storage requirements suggests the use of the conjugate
gradients procedure. Unfortunately, the general-purpose algorithm 22 may con-
verge only very slowly. This is due (a) to the inaccuracy of the linear search, and
(b) to loss of conjugacy between the search directions t , j=1, 2, . . . , n. Both these
j
problems are exacerbated by the fact that the Rayleigh quotient is homogeneous
of degree zero, which means that the Rayleigh quotient takes the same value for
any vector Cx, where C is some non-zero constant. This causes the Hessian of the
Rayleigh quotient to be singular, thus violating the conditions normally required
for the conjugate gradients algorithm. Bradbury and Fletcher (1966) address this
difficulty by setting to unity the element of largest magnitude in the current
eigenvector approximation and adjusting the other elements accordingly. This
adjustment is made at each iteration. However, Geradin (1971) has tackled the
problem more directly, that is, by examining the Hessian itself and attempting to
construct search directions which are mutually conjugate with respect to it. This
treatment, though surely not the last word on the subject, is essentially repeated
here. The implementation details are my own.
Firstly, consider the linear search subproblem, which in the current case can
be solved analytically. It is desired to minimise
T T
R=(x+k t) A(x+k t) / (x+k t) B(x+k t) (19.33)
with respect to k. For convenience this will be rewritten
R=N(k) /D(k) (19.34)
with N and D used to denote the numerator and denominator, respectively.
Differentiating with respect to k gives
2
dR/d k=0=(DdN/d k-NdD/d k) /D . (19.35)
Because of the positive definiteness of B, D can never be zero unless
x+kt =0. (19.36)
Therefore, ignoring this last possibility, we set the numerator of expression
(19.35) to zero to obtain the quadratic equation
2
uk +vk +w =0 (19.37)
where
T T T T
u = (t At)(x Bt)-(x At)(t Bt) (19.38)