Converting approximate error bounds into exact ones

Author:
Abraham Ziv

Journal:
Math. Comp. **64** (1995), 265-277

MSC:
Primary 65G05; Secondary 65D20

MathSciNet review:
1260129

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: In order to produce error bounds quickly and easily, people often apply to error bounds linearized propagation rules. This is done instead of a precise error analysis. The payoff: Estimates so produced are not guaranteed to be true bounds. One can at most hope that they are good approximations of true bounds.

This paper discusses a way to convert such approximate error bounds into true bounds. This is done by dividing the approximate bound by , with a small . Both the approximate bound and are produced by the same linearized error analysis. This method makes it possible both to simplify the error analyses and to sharpen the bounds in an interesting class of numerical algorithms. In particular it seems to be ideal for the derivation of tight, true error bounds for simple and accurate algorithms, like those used in subroutines for the evaluation of elementary mathematical functions (EXP, LOG, SIN, etc.), for instance. The main subject of this paper is forward a priori error analysis. However, the method may be fitted to other types of error analysis too. In fact the outlines of a forward a posteriori error analysis theory and of running error analysis are given also. In the course of proofs a new methodology is applied for the representation of propagated error bounds. This methodology promotes easy derivation of sharp, helpful inequalities. Several examples of forward a priori error analysis and one of a posteriori error analysis and running error analysis are included.

**[1]**F. L. Bauer,*Computational graphs and rounding error*, SIAM J. Numer. Anal.**11**(1974), 87–96. MR**0356482****[2]**F. W. J. Olver,*A new approach to error arithmetic*, SIAM J. Numer. Anal.**15**(1978), no. 2, 368–393. MR**0483379****[3]**F. W. J. Olver,*Further developments of rp and ap error analysis*, IMA J. Numer. Anal.**2**(1982), no. 3, 249–274. MR**678016**, 10.1093/imanum/2.3.249**[4]**F. W. J. Olver,*Error analysis of complex arithmetic*, Computational aspects of complex analysis (Braunlage, 1982) NATO Adv. Sci. Inst. Ser. C: Math. Phys. Sci., vol. 102, Reidel, Dordrecht-Boston, Mass., 1983, pp. 279–292. MR**712900****[5]**F. W. J. Olver,*Error bounds for polynomial evaluation and complex arithmetic*, IMA J. Numer. Anal.**6**(1986), no. 3, 373–379. MR**967677**, 10.1093/imanum/6.3.373**[6]**F. W. J. Olver,*Error bounds for linear recurrence relations*, Math. Comp.**50**(1988), no. 182, 481–499. MR**929547**, 10.1090/S0025-5718-1988-0929547-9**[7]**F. W. J. Olver and J. H. Wilkinson,*A posteriori error bounds for Gaussian elimination*, IMA J. Numer. Anal.**2**(1982), no. 4, 377–406. MR**692286**, 10.1093/imanum/2.4.377**[8]**J. D. Pryce,*A new measure of relative error for vectors*, SIAM J. Numer. Anal.**21**(1984), no. 1, 202–215. MR**731224**, 10.1137/0721015**[9]**J. D. Pryce,*Multiplicative error analysis of matrix transformation algorithms*, IMA J. Numer. Anal.**5**(1985), no. 4, 437–445. MR**816067**, 10.1093/imanum/5.4.437**[10]**R. Scherer and K. Zeller,*Shorthand notation for rounding errors*, Fundamentals of numerical computation (computer-oriented numerical analysis) (Proc. Conf., Tech. Univ. Berlin, Berlin, 1979) Comput. Suppl., vol. 2, Springer, Vienna, 1980, pp. 165–168. MR**586229****[11]**Pat H. Sterbenz,*Floating-point computation*, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1974. Prentice-Hall Series in Automatic Computation. MR**0349062****[12]**J. Stoer and R. Bulirsch,*Introduction to numerical analysis*, 2nd printing, Springer-Verlag, Berlin and New York, 1983.**[13]**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****[14]**J. H. Wilkinson,*Rounding errors in algebraic processes*, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1963. MR**0161456****[15]**Abraham Ziv,*Relative distance—an error measure in round-off error analysis*, Math. Comp.**39**(1982), no. 160, 563–569. MR**669649**, 10.1090/S0025-5718-1982-0669649-2**[16]**Abraham Ziv,*A stable method for the evaluation of a polynomial and of a rational function of one variable*, Numer. Math.**41**(1983), no. 3, 309–319. MR**712115**, 10.1007/BF01418328**[17]**-,*Fast evaluation of elementary mathematical functions with correctly rounded last bit*, ACM Trans. Math. Software**17**(1991), 410-423.**[18]**-,*Converting approximate into true error bounds*, Technical Report 88.326, July 1992, Science and Technology, IBM Israel.

Retrieve articles in *Mathematics of Computation*
with MSC:
65G05,
65D20

Retrieve articles in all journals with MSC: 65G05, 65D20

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1995-1260129-1

Keywords:
Error analysis,
differential error analysis,
relative error,
relative precision,
relative distance,
error measure,
floating point

Article copyright:
© Copyright 1995
American Mathematical Society