Page 254 - Compact Numerical Methods For Computers

Conjugate gradients method in linear algebra 241
convergence tolerance be scaled to the problem. Thus I have used
tol=n*S1*S1*eps*eps

where eps is the machine precision. The points to be noted in the solutions are as
follows:
(i) the rapid convergence in terms of matrix-vector products needed to arrive at
a solution (recall that the problem is singular since no ‘zero’ of height has been
specified), and
(ii) the reduction in the variance of the computed height differences from their
known values.

All the computations were performed on a Data General NOVA operating in
23-bit binary arithmetic.

TABLE 19.2. Surveying-data fitting by algorithm 24.
Variance of Variance
m = Matrix Height Perturbation Perturbation computed height reduction
n n(n-1)/2 products scale S1 scale S2 variance? differences? factor
4 6 3 100 0·01 9·15E-6 1·11E-6 0·12
4 6 2 100 1 9·15E-2 1·11E-2 0·12
4 6 2 10000 1 9·15E-2 1·11E-2 0·12
10 45 3 1000 0·1 9·25E-4 2·02E-4 0·22
20 190 3 1000 0·1 8·37E-4 6·96E-5 0·08
20 190 3 1000 100 836·6 69·43 0·08
20 190 5 1000 2000 334631 26668·7 0·08
† From ‘known’ values.

19.3. INVERSE ITERATION BY ALGORITHM 24

The algorithm just presented, since it solves systems of linear equations, can be
employed to perform inverse iteration on symmetric matrix eigenproblems via
either of the schemes (9.10) or (9.12), that is, the ordinary and generalised
symmetric matrix eigenproblems. The only difficulties arise because the matrix
A' = A - s B (19.19)

where s is some shift, is not positive definite. (Only the generalised problem will
be treated.) In fact, it is bound to be indefinite if an intermediate eigenvalue is
sought. Superficially, this can be rectified immediately by solving the least-squares
problem
T T
(A') (A')y =(A') Bx (19.20)
i i
in place of (9.12a). However, as with the Froberg problem of example 19.1, this is
done at the peril of worsening the condition of the problem. Since Hestenes
(1975) has pointed out that the conjugate gradients method may work for
indefinite systems-it is simply no longer supported by a convergence theorem-