Converting approximate error bounds into exact ones
Author:
Abraham Ziv
Journal:
Math. Comp. 64 (1995), 265277
MSC:
Primary 65G05; Secondary 65D20
MathSciNet review:
1260129
Fulltext 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
(50 #8952)
 [2]
F.
W. J. Olver, A new approach to error arithmetic, SIAM J.
Numer. Anal. 15 (1978), no. 2, 368–393. MR 0483379
(58 #3385)
 [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
(84c:65073), http://dx.doi.org/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,
DordrechtBoston, Mass., 1983, pp. 279–292. MR 712900
(84k:65047)
 [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 (89h:65066), http://dx.doi.org/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
(89e:65146), http://dx.doi.org/10.1090/S00255718198809295479
 [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
(84m:65044), http://dx.doi.org/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
(85i:65061), http://dx.doi.org/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 (87f:65056), http://dx.doi.org/10.1093/imanum/5.4.437
 [10]
R.
Scherer and K.
Zeller, Shorthand notation for rounding errors, Fundamentals
of numerical computation (computeroriented numerical analysis) (Proc.
Conf., Tech. Univ. Berlin, Berlin, 1979) Comput. Suppl., vol. 2,
Springer, Vienna, 1980, pp. 165–168. MR 586229
(81m:65064)
 [11]
Pat
H. Sterbenz, Floatingpoint computation, PrenticeHall, Inc.,
Englewood Cliffs, N.J., 1974. PrenticeHall Series in Automatic
Computation. MR
0349062 (50 #1556)
 [12]
J. Stoer and R. Bulirsch, Introduction to numerical analysis, 2nd printing, SpringerVerlag, Berlin and New York, 1983.
 [13]
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)
 [14]
J.
H. Wilkinson, Rounding errors in algebraic processes,
PrenticeHall, Inc., Englewood Cliffs, N.J., 1963. MR 0161456
(28 #4661)
 [15]
Abraham
Ziv, Relative distance—an error
measure in roundoff error analysis, Math.
Comp. 39 (1982), no. 160, 563–569. MR 669649
(83k:65035), http://dx.doi.org/10.1090/S00255718198206696492
 [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
(85h:65060), http://dx.doi.org/10.1007/BF01418328
 [17]
, Fast evaluation of elementary mathematical functions with correctly rounded last bit, ACM Trans. Math. Software 17 (1991), 410423.
 [18]
, Converting approximate into true error bounds, Technical Report 88.326, July 1992, Science and Technology, IBM Israel.
 [1]
 F. L. Bauer, Computational graphs and rounding error, SIAM J. Numer. Anal. 11 (1974), 8796. MR 0356482 (50:8952)
 [2]
 F. W. J. Olver, A new approach to error arithmetic, SIAM J. Numer. Anal. 15 (1978), 368393. MR 0483379 (58:3385)
 [3]
 , Further developments of Rp and Ap error analysis, IMA J. Numer. Anal. 2 (1982), 249274. MR 678016 (84c:65073)
 [4]
 , Error analysis of complex arithmetic, Computational Aspects of Complex Analysis (H. Werner et al., eds.), Reidel, Dordrecht, 1983, pp. 279292. MR 712900 (84k:65047)
 [5]
 , Error bounds for polynomial evaluation and complex arithmetic, IMA J. Numer. Anal. 6 (1986), 373379. MR 967677 (89h:65066)
 [6]
 , Error bounds for linear recurrence relations, Math. Comp. 50 (1988), 481499. MR 929547 (89e:65146)
 [7]
 F. W. J. Olver and J. H. Wilkinson, A posteriori error bounds for Gaussian elimination, IMA J. Numer. Anal. 2 (1982), 377406. MR 692286 (84m:65044)
 [8]
 J. D. Pryce, A new measure of relative error for vectors, SIAM J. Numer. Anal. 21 (1984), 202215. MR 731224 (85i:65061)
 [9]
 , Multiplicative error analysis of matrix transformation algorithms, IMA J. Numer. Anal. 5 (1985), 437445. MR 816067 (87f:65056)
 [10]
 R. Scherer and K. Zeller, Shorthand notation for rounding errors, Computing, Suppl. 2 (G. Alefeld et al., eds.), SpringerVerlag, New York, 1980, pp. 165168. MR 586229 (81m:65064)
 [11]
 Pat H. Sterbenz, Floatingpoint computation, PrenticeHall, Englewood Cliffs, NJ, 1974. MR 0349062 (50:1556)
 [12]
 J. Stoer and R. Bulirsch, Introduction to numerical analysis, 2nd printing, SpringerVerlag, Berlin and New York, 1983.
 [13]
 F. Stummel, Rounding error analysis of elementary numerical algorithms, Computing, Suppl. 2 (G. Alefeld et al., eds.), SpringerVerlag, New York, 1980, pp. 169195. MR 586230 (81m:65065)
 [14]
 J. H. Wilkinson, Rounding errors in algebraic processes, PrenticeHall, Englewood Cliffs, NJ, 1963. MR 0161456 (28:4661)
 [15]
 A. Ziv, Relative distancean error measure in roundoff error analysis, Math. Comp. 39 (1982), 563569. MR 669649 (83k:65035)
 [16]
 , A stable method for the evaluation of a polynomial and of a rational function of one variable, Numer. Math. 41 (1983), 309319. MR 712115 (85h:65060)
 [17]
 , Fast evaluation of elementary mathematical functions with correctly rounded last bit, ACM Trans. Math. Software 17 (1991), 410423.
 [18]
 , Converting approximate into true error bounds, Technical Report 88.326, July 1992, Science and Technology, IBM Israel.
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
65G05,
65D20
Retrieve articles in all journals
with MSC:
65G05,
65D20
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718199512601291
PII:
S 00255718(1995)12601291
Keywords:
Error analysis,
differential error analysis,
relative error,
relative precision,
relative distance,
error measure,
floating point
Article copyright:
© Copyright 1995
American Mathematical Society
