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.

**[1]**I. Babuška,*Numerical Stability in Numerical Analysis*, Proc. IFIP-Congress 1968, Amsterdam, North-Holland, Amsterdam, 1969, pp. 11-23.**[2]**Ivo Babuška,*Numerical stability in problems of linear algebra*, SIAM J. Numer. Anal.**9**(1972), 53–77. MR**0386252****[3]**Ivo Babuška, Milan Práger, and Emil Vitásek,*Numerical processes in differential equations*, In cooperation with R. Radok. Translated from the Czech by Milada Boruvková, Státní Nakladatelství Technické Literatury, Prague; Interscience Publishers John Wiley & Sons, London-New York-Sydney, 1966. MR**0223101****[4]**F. L. Bauer,*Genauigkeitsfragen bei der Lösung linearer Gleichungssysteme*, Z. Angew. Math. Mech.**46**(1966), 409–421 (German). MR**0208814****[5]**F. L. Bauer,*Computational graphs and rounding error*, SIAM J. Numer. Anal.**11**(1974), 87–96. MR**0356482****[6]**F. L. Bauer et al.,*Moderne Rechenanlagen*, Chap. 3, Teubner, Stuttgart, 1964.**[7]**W. S. Brown,*A realistic model of floating-point computation*, Mathematical software, III (Proc. Sympos., Math. Res. Center, Univ. Wisconsin, Madison, Wis., 1977) Academic Press, New York, 1977, pp. 343–360. Publ. Math. Res. Center, No. 39. MR**0483616****[8]**Peter Henrici,*Elements of numerical analysis*, John Wiley & Sons, Inc., New York-London-Sydney, 1964. MR**0166900****[9]**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**, 10.1145/355791.355794**[10]**Seppo Linnainmaa,*Taylor expansion of the accumulated rounding error*, Nordisk Tidskr. Informationsbehandling (BIT)**16**(1976), no. 2, 146–160. MR**0421065****[11]**D. D. McCracken & W. S. Dorn,*Numerical Methods and Fortran Programming*, Wiley, New York, 1964.**[12]**Webb Miller,*Software for roundoff analysis*, ACM Trans. Math. Software**1**(1975), 108–128. MR**0405830****[13]**Webb Miller,*Computer search for numerical instability*, J. Assoc. Comput. Mach.**22**(1975), no. 4, 512–521. MR**0478584****[14]**Webb Miller and David Spooner,*Software for roundoff analysis. II*, ACM Trans. Math. Software**4**(1978), no. 4, 369–387. MR**513705**, 10.1145/356502.356496**[15]**John R. Rice,*A theory of condition*, SIAM J. Numer. Anal.**3**(1966), 287–310. MR**0211576****[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*, Math. Methods Appl. Sci.**4**(1982), no. 4, 549–571. MR**681254**, 10.1002/mma.1670040135**[18]**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****[19]**F. Stummel, "Rounding error anlaysis of difference and extrapolation schemes." (To appear.)**[20]**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****[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]**Martti Tienari,*On some topological properties of numerical algorithms*, Nordisk Tidskr. Informationsbehandling (BIT)**12**(1972), 409–433. MR**0334582****[25]**J. H. Wilkinson,*Rounding errors in algebraic processes*, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1963. MR**0161456**

Retrieve articles in *Mathematics of Computation*
with MSC:
65G99

Retrieve articles in all journals with MSC: 65G99

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1981-0628707-8

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