Page 25 - Compact Numerical Methods For Computers

A starting point 15
myself the effort of having to duplicate their calculation to prove the correctness of
the results. Therefore, if at all possible, such checks are always built into my
programs.
The fourth point is important if users are to be able to try out the ideas presented
in this book. As a user myself, I do not wish to spend many hours mastering the
details of a code. The programs are to be treated as tools, not an end in themselves.
These principles lead to the choice of the Givens’ reduction in algorithm 4 as a
method for the solution of least-squares problems where the amount of data is too
great to allow all of it to be stored in the memory at once. Similarly, algorithms 24
and 25 require the user to provide a rule for the calculation of the product of a
matrix and a vector as a step in the solution of linear equations or the algebraic
eigenproblem. However, the matrix itself need not be stored explicitly. This
avoids the problem of designing a special method to take advantage of one type of
matrix, though it requires rather more initiative from the user as it preserves this
measure of generality.
In designing the particular forms of the algorithms which appear, a conscious
effort has been made to avoid the requirement for many tolerances. Some
machine-dependent quantities are unfortunately needed (they can in some cases
be calculated by the program but this does lengthen the code), but as far as
possible, and especially in determining when iterative algorithms have converged,
devices are used which attempt to ensure that as many digits are determined as
the machine is able to store. This may lead to programs continuing to execute long
after acceptable answers have been obtained. However, I prefer to sin on the side
of excess rather than leave results wanting in digits. Typically, the convergence
test requires that the last and present iterates be identical to the precision of the
machine by means of a test such as
if x + delta + offset = x + offset then halt;

where offset is some modest number such as 10. On machines which have an
accumulator with extra digits, this type of test may never be satisfied, and must be
replaced by
y: = x + delta + offset;
z: = x + offset;
if y = z then halt;
The ‘tolerance’ in this form of test is provided by the offset: within the computer the
representations of y and z must be equal to halt execution. The simplicity of this type
of test usually saves code though, as mentioned, at the possible expense of execution
time.

1.6. A METHOD FOR EXPRESSING ALGORITHMS
In the first edition of this work, algorithms were expressed in step-and-description
form. This allowed users to program them in a variety of programming languages.
Indeed, one of the strengths of the first edition was the variety of implementations.
At the time it appeared, a number of computers had their own languages or dialects,