Converting approximate error bounds into exact ones
HTML articles powered by AMS MathViewer
- by Abraham Ziv PDF
- Math. Comp. 64 (1995), 265-277 Request permission
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 $1 - \delta$, with a small $\delta$. Both the approximate bound and $\delta$ 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.References
- F. L. Bauer, Computational graphs and rounding error, SIAM J. Numer. Anal. 11 (1974), 87–96. MR 356482, DOI 10.1137/0711010
- F. W. J. Olver, A new approach to error arithmetic, SIAM J. Numer. Anal. 15 (1978), no. 2, 368–393. MR 483379, DOI 10.1137/0715024
- F. W. J. Olver, Further developments of rp and ap error analysis, IMA J. Numer. Anal. 2 (1982), no. 3, 249–274. MR 678016, DOI 10.1093/imanum/2.3.249
- 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
- F. W. J. Olver, Error bounds for polynomial evaluation and complex arithmetic, IMA J. Numer. Anal. 6 (1986), no. 3, 373–379. MR 967677, DOI 10.1093/imanum/6.3.373
- F. W. J. Olver, Error bounds for linear recurrence relations, Math. Comp. 50 (1988), no. 182, 481–499. MR 929547, DOI 10.1090/S0025-5718-1988-0929547-9
- 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, DOI 10.1093/imanum/2.4.377
- J. D. Pryce, A new measure of relative error for vectors, SIAM J. Numer. Anal. 21 (1984), no. 1, 202–215. MR 731224, DOI 10.1137/0721015
- J. D. Pryce, Multiplicative error analysis of matrix transformation algorithms, IMA J. Numer. Anal. 5 (1985), no. 4, 437–445. MR 816067, DOI 10.1093/imanum/5.4.437
- 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
- Pat H. Sterbenz, Floating-point computation, Prentice-Hall Series in Automatic Computation, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1974. MR 0349062 J. Stoer and R. Bulirsch, Introduction to numerical analysis, 2nd printing, Springer-Verlag, Berlin and New York, 1983.
- 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
- J. H. Wilkinson, Rounding errors in algebraic processes, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1963. MR 0161456
- Abraham Ziv, Relative distance—an error measure in round-off error analysis, Math. Comp. 39 (1982), no. 160, 563–569. MR 669649, DOI 10.1090/S0025-5718-1982-0669649-2
- 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, DOI 10.1007/BF01418328 —, Fast evaluation of elementary mathematical functions with correctly rounded last bit, ACM Trans. Math. Software 17 (1991), 410-423. —, Converting approximate into true error bounds, Technical Report 88.326, July 1992, Science and Technology, IBM Israel.
Additional Information
- © Copyright 1995 American Mathematical Society
- Journal: Math. Comp. 64 (1995), 265-277
- MSC: Primary 65G05; Secondary 65D20
- DOI: https://doi.org/10.1090/S0025-5718-1995-1260129-1
- MathSciNet review: 1260129