Page 92 - Compact Numerical Methods For Computers

Linear equations—a direct approach 81
approximately the same size. Is this worth the bother? I can only add that I rarely
scale sets of equations unless there is some very obvious and natural way to do it.
Similar comments apply to iterative improvement of a computed solution
(Dahlquist and Björck 1974, pp 183-5, Bowdler et al 1966). Given a computed
solution
(6.36)
if
(6.37)

then a triangular decomposition of A permits solution of
Ac = LRc = r (6.38)

for c and computation of a new solution

(6.39)
The process can be repeated until the computed solution has converged, but in
virtually all cases the improvement of the solution occurs in the first application of
(6.36) to (6.39). A similar algorithm can be used to improve least-squares
solutions (Dahlquist and Björck 1974, pp 204–5). Unfortunately these improve-
ment procedures are dependent on accurate computation of residuals, and
double-precision arithmetic must be called into play. As the systems for which this
book is designed often lack this feature, one may fall into the habit of not using
iterative improvement of linear-equation or least-squares solutions.
Even when computing in an environment where double-length arithmetic is
available, I generally do not bother to employ it. Personally, very little of my
work has concerned numbers which have arisen out of precise measurement. In
fact, my clients are often only sure of the first one or two digits of their data, so
that it is unnecessary to provide an extremely accurate solution, though it is
important in many cases to identify near-linear dependencies (hence singularities)
by means of a technique such as the singular-value decomposition.
So far in this section I have mentioned only techniques of which I do not
generally make use. To finish, then, consider the one excursion from algorithms 5
and 6 which has diverted me from time to time. This is the purely organisational
question of how the information in the working array A should be organised and
accessed. In the algorithms as presented, I have chosen to perform interchanges
explicitly and store the coefficient matrix and right-hand sides together in a single
two-dimensional array. The choice of a single working array with solutions
overwriting the right-hand sides b I feel to be the sensible one for small-computer
implementations. The choice of method for accessing the elements of this array is
less simple. Besides the direct, two-dimensional method which has been used, it is
possible to perform pivot interchanges implicitly if the pivot positions are saved,
for instance in an integer vector q so that the ith pivot is stored in A[q[i,i]. Thus
if the algorithm is started so that

q[i] = i for i = 1, 2, . . . , n (6.40)