ALBERT

Notes: Abstract Calculation in unnormalized arithmetic provides, as has been described elsewhere, an estimate of the error of each quantity, initial, intermediate, and final, in a calculation. In an acceptable computational algorithm, this error estimate should be close to the true probable error. (The probable error is defined as follows: each computed quantity is defined, in the statement of the problem, explicitly or implicitly as some function of the input data, which are however known only up to errors having some distribution. As the input data vary in their joint distribution, the value of this function varies in a distribution whose variance determines the probable error of the result.) Many computational algorithms fail to achieve this goal, because whenever two numbers are combined arithmetically (+, -, ×, or ÷) in a computer, anycorrelation of the errors of the two numbers is perforce ignored; in consequence, the error estimate of a computed result may be greater than, comparable with, or smaller than the probable error, in which case the algorithm is called “conservative”, “faithful”, or “liberal”, respectively. In this article, a matrix-inversion algorithm based on an assignment strategy is described, which is very close to faithful, as evidenced by extensive numerical tests, which are also described. A test matrix has elements with varying numbers of leading zeros, the remaining bits in a 43-bit pattern are regarded as meaningful; its inverse is computed. A series of perturbed matrices are formed by adding or subtracting a one-bit in the 31st-stage of each input matrix element; this corresponds to amaximum change in the last twelve bits; the statistical aspect is then in the choice of addition-subtraction. By comparing the results of the successive inversions, the magnitude of the probable error (as defined above) resulting from these perturbations can be rather closely determined. (These tests cover the case in which the errors of the input matrix elements are uncorrelated.) If the calculation is regarded as one in which the 30th bit is the last significant one and the remaining 13 bits are guard digits, then, for a faithful algorithm, the observed probable error should appear starting in the 31st place. This is found to be the case quite accurately for the algorithm here proposed, but not for other commonly used algorithms. It should be pointed out that the algorithm here described is optimal also for normalized arithmetic (in which errors are ignored), because the precision on the one hand cannot be increased by retaining insignificant digits and on the other hand is in any case limited by the true probable error, no matter what algorithm is used (unless the input data are infinitely precise). However, the results are likely to be less satisfactory in normalized arithmetic, because explicit use is made of the relative precisions of certain quantities at each pivoting in the matrix inversion, and the machine indication of this relative precision is falsified when numbers are unduly normalized.