Perturbation theory for evaluation algorithms of arithmetic expressions
HTML articles powered by AMS MathViewer
 by F. Stummel PDF
 Math. Comp. 37 (1981), 435473 Request permission
Abstract:
The paper presents the theoretical foundation of a forward error analysis of numerical algorithms under data perturbations, rounding error in arithmetic floatingpoint operations, and approximations in ’builtin’ 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 illconditioning of a problem and an algorithm. The wellknown 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. IFIPCongress 1968, Amsterdam, NorthHolland, Amsterdam, 1969, pp. 1123.
 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, LondonNew YorkSydney, 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 floatingpoint 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 YorkLondonSydney, 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 (computeroriented 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 YorkLondon, 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, PrenticeHall, Inc., Englewood Cliffs, N.J., 1963. MR 0161456
Additional Information
 © Copyright 1981 American Mathematical Society
 Journal: Math. Comp. 37 (1981), 435473
 MSC: Primary 65G99
 DOI: https://doi.org/10.1090/S00255718198106287078
 MathSciNet review: 628707