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
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