Some a Posteriori Error Bounds in Floating-Point Computations

ABSTRACT

Efficiently computable a posteriori error bounds are attained by using a posteriori models for bounding roundoff errors in the basic floating-point operations. Forward error bounds are found for inner product and polynomial evaluations. An analysis of the Crout algorithm in solving systems of linear algebraic equations leads to sharper backward a posteriori bounds. The results in the analysis of the iterative refinement give bounds useful in estimating the rate of convergence. Some numerical experiments are included.

REFERENCES

• 1: WILKINSON, J.H. Rounding errors in algebraic processes. Information Processing, UNESCO, Paris, 1960, pp. 44-53.
• 2: WILKINSON, J. H. Error analysis of floating-point computations. Numer. Math. 2 (1960), 319-340.
• 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: James H. Wilkinson, Rounding Errors in Algebraic Processes, Dover Publications, Incorporated, 1994
• 5: J. H. Wilkinson, The algebraic eigenvalue problem, Oxford University Press, Inc., New York, NY, 1988
• 6: FORSYTR% G. E., ANn MOLER, C.B. Computer Solution of Linear Algebraic Systems. Prentice- Hall, Englewood Cliffs, N. J., 1967.
• 7: Tsao, N. K. Computable error bou'tids for inner product evaluation. Aerospace Research Laboratories Tech. Rep. ARL72-0130, 1972.
• 8: Ts~o, N.K. A posteriori analysis of the Crout method in solving linear algebraic systems. Aerospace Research Laboratories Tech. Rep. ARL72-0131, 1972.
• 9: WsAo, N.K. On iterative refinement procedure in solving linear algebraic systems. Aerospace Research Laboratories Tech. Rep. ARL72-0144, 1972.
• 10: Cleve B. Moler, Iterative Refinement in Floating Point, Journal of the ACM (JACM), v.14 n.2, p.316-321, April 1967 [doi>10.1145/321386.321394]
• 11: Duane A. Adams, A stopping criterion for polynomial root finding, Communications of the ACM, v.10 n.10, p.655-658, Oct. 1967 [doi>10.1145/363717.363775]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Error analysis

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Computer arithmetic

General Terms:
Algorithms, Experimentation, Measurement, Performance, Theory