Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Perturbation theory for evaluation algorithms of arithmetic expressions

Author: F. Stummel
Journal: Math. Comp. 37 (1981), 435-473
MSC: Primary 65G99
MathSciNet review: 628707
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: The paper presents the theoretical foundation of a forward error analysis of numerical algorithms under data perturbations, rounding error in arithmetic floating-point operations, and approximations in 'built-in' functions. The error analysis is based on the linearization method that has been proposed by many authors in various forms. Fundamental tools of the forward error analysis are systems of linear absolute and relative a priori and a posteriori error equations and associated condition numbers constituting optimal bounds of possible accumulated or total errors. Derivations, representations, and properties of these condition numbers are studied in detail. The condition numbers enable simple general, quantitative definitions of numerical stability, backward analysis, well- and ill-conditioning of a problem and an algorithm. The well-known illustration of algorithms and their linear error equations by graphs is extended to a method of deriving condition numbers and associated bounds. For many algorithms the associated condition numbers can be determined analytically a priori and be computed numerically a posteriori. The theoretical results of the paper have been applied to a series of concrete algorithms, including Gaussian elimination, and have proved to be very effective means of both a priori and a posteriori error analysis.

References [Enhancements On Off] (What's this?)

  • [1] I. Babuška, Numerical Stability in Numerical Analysis, Proc. IFIP-Congress 1968, Amsterdam, North-Holland, Amsterdam, 1969, pp. 11-23.
  • [2] I. Babuška, "Numerical stability in problems of linear algebra," SIAM J. Numer. Anal., v. 9, 1972, pp. 53-77. MR 0386252 (52:7110)
  • [3] I. Babuška, M. Prager & E. Vitasek, Numerical Processes in Differential Equations, Wiley, New York, 1966. MR 0223101 (36:6150)
  • [4] F. L. Bauer, "Genauigkeitsfragen bei der Lösung linearer Gleichungssysteme," Z. Angew. Math. Mech., v. 46, 1966, pp. 409-421. MR 0208814 (34:8623)
  • [5] F. L. Bauer, "Computational graphs and rounding error," SIAM J. Numer. Anal., v. 11, 1974, pp. 87-96. MR 0356482 (50:8952)
  • [6] F. L. Bauer et al., Moderne Rechenanlagen, Chap. 3, Teubner, Stuttgart, 1964.
  • [7] W. S. Brown, A Realistic Model of Floating-Point Computation, Proc. Sympos. Mathematical Software III, Madison, 1977 (J. R. Rice, Ed.), Academic Press, New York, 1977, pp. 343-360. MR 0483616 (58:3605)
  • [8] P. Henrici, Elements of Numerical Analysis, Chap. 16, Wiley, New York, 1964. MR 0166900 (29:4173)
  • [9] J. Larson & A. Sameh, "Efficient calculation of the effects of roundoff errors," ACM Trans. Math. Software, v. 4, 1978, pp. 228-236. MR 506787 (80a:65092a)
  • [10] S. Linnainmaa, "Taylor expansion of the accumulated rounding error," BIT, v. 16, 1976, pp. 146-160. MR 0421065 (54:9070)
  • [11] D. D. McCracken & W. S. Dorn, Numerical Methods and Fortran Programming, Wiley, New York, 1964.
  • [12] W. Miller, "Software for roundoff analysis," ACM Trans. Math. Software, v. 1, 1975, pp. 108-128. MR 0405830 (53:9622)
  • [13] W. Miller, "Computer search for numerical instability," J. Assoc. Comput. Mach., v. 22, 1975, pp. 512-521. MR 0478584 (57:18061)
  • [14] W. Miller & D. Spooner, "Software for roundoff analysis, II," ACM Trans. Math. Software, v. 4, 1978, pp. 369-387. MR 513705 (81i:65035)
  • [15] J. R. Rice, "A theory of condition," SIAM J. Numer. Anal., v. 3, 1966, pp. 287-310. MR 0211576 (35:2454)
  • [16] F. Stummel, Fehleranalyse numerischer Algorithmen, Lecture Notes, Univ. of Frankfurt, 1978.
  • [17] F. Stummel, "Rounding errors in numerical solutions of two linear equations in two unknowns," Preprint, 1980. MR 681254 (84d:65030)
  • [18] F. Stummel, Rounding Error Analysis of Elementary Numerical Algorithms, Proc. Conf. Fundamentals of Numerical Computation, Berlin 1979 (G. Alefeld & R. D. Grigorieff, Eds.), Computing, Suppl. 2, 1980, pp. 169-195. MR 586230 (81m:65065)
  • [19] F. Stummel, "Rounding error anlaysis of difference and extrapolation schemes." (To appear.)
  • [20] F. Stummel, Rounding Error in Gaussian Elimination of Tridiagonal Linear Systems, Survey of Results, Proc. Internat. Sympos. 'Interval Mathematics 1980', Freiburg (K. Nickel, Ed.), Academic Press, New York, 1980, pp. 223-245. MR 651366 (83c:65055)
  • [21] F. Stummel, "Rounding error in Gaussian elimination of tridiagonal linear systems. I," SIAM J. Numer. Anal. (Submitted.)
  • [22] F. Stummel, "Rounding error in Gaussian elimination of tridiagonal linear systems. II," Linear Algebra Appl. (Submitted.)
  • [23] F. Stummel, "Forward error analysis of Gaussian elimination." (To appear.)
  • [24] M. Tienari, "On some topological properties of numerical algorithms," BIT, v. 12, 1972, pp. 409-433. MR 0334582 (48:12901)
  • [25] J. H. Wilkinson, Rounding Errors in Algebraic Processes, Prentice-Hall, Englewood Cliffs, N.J., 1963. MR 0161456 (28:4661)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65G99

Retrieve articles in all journals with MSC: 65G99

Additional Information

Keywords: Rounding error analysis, evaluation algorithms, a priori and a posteriori error estimates, condition numbers, linear error equations, graphs
Article copyright: © Copyright 1981 American Mathematical Society

American Mathematical Society