Perturbation theory for evaluation algorithms of arithmetic expressions
Author:
F. Stummel
Journal:
Math. Comp. 37 (1981), 435473
MSC:
Primary 65G99
MathSciNet review:
628707
Fulltext 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 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.
 [1]
I. Babuška, Numerical Stability in Numerical Analysis, Proc. IFIPCongress 1968, Amsterdam, NorthHolland, Amsterdam, 1969, pp. 1123.
 [2]
Ivo
Babuška, Numerical stability in problems of linear
algebra, SIAM J. Numer. Anal. 9 (1972), 53–77.
MR
0386252 (52 #7110)
 [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, LondonNew YorkSydney, 1966. MR 0223101
(36 #6150)
 [4]
F.
L. Bauer, Genauigkeitsfragen bei der Lösung linearer
Gleichungssysteme, Z. Angew. Math. Mech. 46 (1966),
409–421 (German). MR 0208814
(34 #8623)
 [5]
F.
L. Bauer, Computational graphs and rounding error, SIAM J.
Numer. Anal. 11 (1974), 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 floatingpoint 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
(58 #3605)
 [8]
Peter
Henrici, Elements of numerical analysis, John Wiley &
Sons, Inc., New YorkLondonSydney, 1964. MR 0166900
(29 #4173)
 [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
(80a:65092a), http://dx.doi.org/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
(54 #9070)
 [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
(53 #9622)
 [13]
Webb
Miller, Computer search for numerical instability, J. Assoc.
Comput. Mach. 22 (1975), no. 4, 512–521. MR 0478584
(57 #18061)
 [14]
Webb
Miller and David
Spooner, Software for roundoff analysis. II, ACM Trans. Math.
Software 4 (1978), no. 4, 369–387. MR 513705
(81i:65035), http://dx.doi.org/10.1145/356502.356496
 [15]
John
R. Rice, A theory of condition, SIAM J. Numer. Anal.
3 (1966), 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, Math. Methods Appl. Sci. 4
(1982), no. 4, 549–571. MR 681254
(84d:65030), http://dx.doi.org/10.1002/mma.1670040135
 [18]
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
(81m:65065)
 [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 YorkLondon, 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]
Martti
Tienari, On some topological properties of numerical
algorithms, Nordisk Tidskr. Informationsbehandling (BIT)
12 (1972), 409–433. MR 0334582
(48 #12901)
 [25]
J.
H. Wilkinson, Rounding errors in algebraic processes,
PrenticeHall, Inc., Englewood Cliffs, N.J., 1963. MR 0161456
(28 #4661)
 [1]
 I. Babuška, Numerical Stability in Numerical Analysis, Proc. IFIPCongress 1968, Amsterdam, NorthHolland, Amsterdam, 1969, pp. 1123.
 [2]
 I. Babuška, "Numerical stability in problems of linear algebra," SIAM J. Numer. Anal., v. 9, 1972, pp. 5377. 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. 409421. MR 0208814 (34:8623)
 [5]
 F. L. Bauer, "Computational graphs and rounding error," SIAM J. Numer. Anal., v. 11, 1974, pp. 8796. 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 FloatingPoint Computation, Proc. Sympos. Mathematical Software III, Madison, 1977 (J. R. Rice, Ed.), Academic Press, New York, 1977, pp. 343360. 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. 228236. MR 506787 (80a:65092a)
 [10]
 S. Linnainmaa, "Taylor expansion of the accumulated rounding error," BIT, v. 16, 1976, pp. 146160. 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. 108128. MR 0405830 (53:9622)
 [13]
 W. Miller, "Computer search for numerical instability," J. Assoc. Comput. Mach., v. 22, 1975, pp. 512521. MR 0478584 (57:18061)
 [14]
 W. Miller & D. Spooner, "Software for roundoff analysis, II," ACM Trans. Math. Software, v. 4, 1978, pp. 369387. MR 513705 (81i:65035)
 [15]
 J. R. Rice, "A theory of condition," SIAM J. Numer. Anal., v. 3, 1966, pp. 287310. 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. 169195. 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. 223245. 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. 409433. MR 0334582 (48:12901)
 [25]
 J. H. Wilkinson, Rounding Errors in Algebraic Processes, PrenticeHall, 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
DOI:
http://dx.doi.org/10.1090/S00255718198106287078
PII:
S 00255718(1981)06287078
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
