Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society, the Mathematics of Computation (MCOM) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

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

The 2020 MCQ for Mathematics of Computation is 1.98.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Perturbation theory for evaluation algorithms of arithmetic expressions
HTML articles powered by AMS MathViewer

by F. Stummel PDF
Math. Comp. 37 (1981), 435-473 Request permission

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
    I. Babuška, Numerical Stability in Numerical Analysis, Proc. IFIP-Congress 1968, Amsterdam, North-Holland, Amsterdam, 1969, pp. 11-23.
  • Ivo Babuška, Numerical stability in problems of linear algebra, SIAM J. Numer. Anal. 9 (1972), 53–77. MR 386252, DOI 10.1137/0709008
  • Ivo Babuška, Milan Práger, and Emil Vitásek, Numerical processes in differential equations, Státní Nakladatelství Technické Literatury (SNTL), Prague; Interscience Publishers John Wiley & Sons, London-New York-Sydney, 1966. In cooperation with R. Radok; Translated from the Czech by Milada Boruvková. MR 0223101
  • F. L. Bauer, Genauigkeitsfragen bei der Lösung linearer Gleichungssysteme, Z. Angew. Math. Mech. 46 (1966), 409–421 (German). MR 208814, DOI 10.1002/zamm.19660460702
  • F. L. Bauer, Computational graphs and rounding error, SIAM J. Numer. Anal. 11 (1974), 87–96. MR 356482, DOI 10.1137/0711010
  • F. L. Bauer et al., Moderne Rechenanlagen, Chap. 3, Teubner, Stuttgart, 1964.
  • W. S. Brown, A realistic model of floating-point computation, Mathematical software, III (Proc. Sympos., Math. Res. Center, Univ. Wisconsin, Madison, Wis., 1977) Publ. Math. Res. Center, No. 39, Academic Press, New York, 1977, pp. 343–360. MR 0483616
  • Peter Henrici, Elements of numerical analysis, John Wiley & Sons, Inc., New York-London-Sydney, 1964. MR 0166900
  • John Larson and Ahmed Sameh, Efficient calculation of the effects of roundoff errors, ACM Trans. Math. Software 4 (1978), no. 3, 228–236. MR 506787, DOI 10.1145/355791.355794
  • Seppo Linnainmaa, Taylor expansion of the accumulated rounding error, Nordisk Tidskr. Informationsbehandling (BIT) 16 (1976), no. 2, 146–160. MR 421065, DOI 10.1007/bf01931367
  • D. D. McCracken & W. S. Dorn, Numerical Methods and Fortran Programming, Wiley, New York, 1964.
  • Webb Miller, Software for roundoff analysis, ACM Trans. Math. Software 1 (1975), 108–128. MR 405830, DOI 10.1145/355637.355639
  • Webb Miller, Computer search for numerical instability, J. Assoc. Comput. Mach. 22 (1975), no. 4, 512–521. MR 478584, DOI 10.1145/321906.321916
  • Webb Miller and David Spooner, Software for roundoff analysis. II, ACM Trans. Math. Software 4 (1978), no. 4, 369–387. MR 513705, DOI 10.1145/356502.356496
  • John R. Rice, A theory of condition, SIAM J. Numer. Anal. 3 (1966), 287–310. MR 211576, DOI 10.1137/0703023
  • F. Stummel, Fehleranalyse numerischer Algorithmen, Lecture Notes, Univ. of Frankfurt, 1978.
  • F. Stummel, Rounding errors in numerical solutions of two linear equations in two unknowns, Math. Methods Appl. Sci. 4 (1982), no. 4, 549–571. MR 681254, DOI 10.1002/mma.1670040135
  • F. Stummel, Rounding error analysis of elementary numerical algorithms, Fundamentals of numerical computation (computer-oriented numerical analysis) (Proc. Conf., Tech. Univ. Berlin, Berlin, 1979) Comput. Suppl., vol. 2, Springer, Vienna, 1980, pp. 169–195. MR 586230
  • F. Stummel, "Rounding error anlaysis of difference and extrapolation schemes." (To appear.)
  • Friedrich Stummel, Rounding error in Gaussian elimination of tridiagonal linear systems. Survey of results, Interval mathematics, 1980 (Freiburg, 1980) Academic Press, New York-London, 1980, pp. 223–245. MR 651366
  • F. Stummel, "Rounding error in Gaussian elimination of tridiagonal linear systems. I," SIAM J. Numer. Anal. (Submitted.) F. Stummel, "Rounding error in Gaussian elimination of tridiagonal linear systems. II," Linear Algebra Appl. (Submitted.) F. Stummel, "Forward error analysis of Gaussian elimination." (To appear.)
  • Martti Tienari, On some topological properties of numerical algorithms, Nordisk Tidskr. Informationsbehandling (BIT) 12 (1972), 409–433. MR 334582, DOI 10.1007/bf01932311
  • J. H. Wilkinson, Rounding errors in algebraic processes, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1963. MR 0161456
Similar Articles
  • Retrieve articles in Mathematics of Computation with MSC: 65G99
  • Retrieve articles in all journals with MSC: 65G99
Additional Information
  • © Copyright 1981 American Mathematical Society
  • Journal: Math. Comp. 37 (1981), 435-473
  • MSC: Primary 65G99
  • DOI: https://doi.org/10.1090/S0025-5718-1981-0628707-8
  • MathSciNet review: 628707