Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



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.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65G99

Retrieve articles in all journals with MSC: 65G99

Additional Information

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