ROUNDING-OFF ERRORS IN MATRIX PROCESSES
By A. M. TURING
{National Physical Laboratory, Teddington, Middlesex)
[Received 4 November 1947]
SUMMARY
A number of methods of solving sets of linear equations and inverting matrices
are discussed. The theory of the rounding-off errors involved is investigated for
some of the methods. In all cases examined, including the well-known 'Gauss
elimination process', it is found that the errors are normally quite moderate: no
exponential build-up need occur.
Included amongst the methods considered is a generalization of Choleski's method
which appears to have advantages over other known methods both as regards
accuracy and convenience. This method may also be regarded as a rearrangement
of the elimination process.
THIS paper contains descriptions of a number of methods for solving sets
of linear simultaneous equations and for inverting matrices, but its main
concern is with the theoretical limits of accuracy that may be obtained in
the application of these methods, due to rounding-off errors.
The best known method for the solution of linear equations is Gauss's
elimination method. This is the method almost universally taught in
schools. It has, unfortunately, recently come into disrepute on the ground
that rounding off will give rise to very large errors. It has, for instance,
been argued
by HoteUing (ref. 5) that in solving a set of n equations we
should keep nlog
10
4 extra or 'guarding' figures. Actually, although
examples can be constructed where as many as «log
10
2 extra figures
would be required, these are exceptional. In the present paper the
magnitude of the error is described in terms of quantities not considered
in HoteUing's analysis; from the inequalities proved here it can imme-
diately be seen that in all normal cases the Hotelling estimate is far too
pessimistic.
The belief that the elimination method and other 'direct' methods of
solution lead to large errors has been responsible for a recent search for
other methods which would be free from this weakness. These were
mainly methods of successive approximation and considerably more
laborious than the direct
ones.
There now appears to be no real advantage
in the indirect methods, except in connexion with matrices having special
properties, for example, where the vast majority of the coefficients are
very small, but there is at least one large one in each row.
The writer was prompted to cany out this research largely by the
practical work of L. Fox in applying the elimination method (ref. 2). Fox
at Princeton University Library on September 20, 2011qjmam.oxfordjournals.orgDownloaded from
