Computable Error Bounds for Direct Solution of Linear Equations

ABSTRACT

An error analysis of direct methods (i.e., Gaussian elimination or triangular factorization) of solving simultaneous linear algebraic equations is performed in the backward mode, in which the computational errors are expressed as perturbations on the data. Bounds are found for perturbations on the coefficients of the equations, leaving the right-hand sides unchanged. These bounds can be evaluated concurrently with the computation itself, with only a small increase in computing effort. Because they use information obtained during the solution process, these bounds avoid exaggerating the magnitude of the error, and so are also useful as error estimates.

REFERENCES

• 1: J. H. Wilkinson, The algebraic eigenvalue problem, Oxford University Press, Inc., New York, NY, 1988
• 2: James H. Wilkinson, Rounding Errors in Algebraic Processes, Dover Publications, Incorporated, 1994
• 3: J. H. Wilkinson, Error Analysis of Direct Methods of Matrix Inversion, Journal of the ACM (JACM), v.8 n.3, p.281-330, July 1961 [doi>10.1145/321075.321076]
• 4: ----. Rounding errors in algebraic processes. Informalion Processing, UNESCO, Paris, 1960, pp. 44-53.
• 5: GEUDER, J .C . Error analysis of a direct method of solution of simultaneous linear equation systems. M.Sc. thesis, Div. Appl. Math., Brown U., July 1965.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Linear systems (direct and iterative methods)

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Error analysis

General Terms:
Measurement, Performance, Reliability, Theory