Page 133 - Compact Numerical Methods For Computers

122 Compact numerical methods for computers

it so. Thus we can define
h = 0 for E > e (10.23a)
h = –(|E| + e ) = E – e ½ for E < e (10.23b)
½
to ensure a positive definite matrix A' results from the shift (10.19). The machine
precision e is used simply to take care of those situations, such as a matrix with a
null row (and column), where the lower bound E is in fact a small eigenvalue.
Unfortunately, the accuracy of eigensolutions computed via this procedure is
sensitive to the shift. For instance, the largest residual element R, that is, the
element of largest magnitude in the matrix

AX – XE (10.24)
and the largest inner product P, that is, the off-diagonal element of largest
magnitude in the matrix
T
X X – 1 n (10.25)
for the order-10 Ding Dong matrix (see appendix 1) are: for h = –3.57509,
R = 5·36442E–6 and P = 1·24425E–6 while for h = –10·7238, R = 1·49012E–5
and P = 2·16812E–6. These figures were computed on a Data General NOVA
(23-bit binary arithmetic) using single-length arithmetic throughout as no ex-
tended precision was available. The latter shift was obtained using

for E > 0 (10.26a)
for E < 0. (10.26b)

In general, in a test employing all nine test matrices from appendix 1 of order 4
and order 10, the shift defined by formulae (10.23) gave smaller residuals and
inner products than the shift (10.26). The eigenvalues used in the above examples
were computed via the Rayleigh quotient
(10.27)
rather than the singular value, that is, equation (10.20). In the tests mentioned
above, eigenvalues computed via the Rayleigh quotient gave smaller residuals
than those found merely by adding on the shift. This is hardly surprising if the
nature of the problem is considered. Suppose that the true eigenvectors are ff ,
i
i = 1, 2, . . . , n. Let us add a component cw to ff , where w is some normalised
j
f
combination of the f , i j, and c measures the size of the component (error); the
i
normalised approximation to the eigenvector is then
f
2 -½
x = (l + c ) (f + cw). (10.28)
j
j
f
The norm of the deviation (x – f j ) is found, using the binomial expansion and
j
4 2
ignoring terms in c and higher powers relative to those in c , to be approximately
equal to c. The Rayleigh quotient corresponding to the vector given by (10.28) is
2 T 2
Q = ( E + c w Aw)/(1+ c ) (10.29)
j jj
since is zero by virtue of the orthogonality of the eigenvectors. The
deviation of Q from the eigenvalue is
j