On relative errors of floating-point operations: Optimal bounds and applications

Jeannerod, Claude-Pierre; Rump, Siegfried M.

doi:10.1090/mcom/3234

On relative errors of floating-point operations: Optimal bounds and applications
HTML articles powered by AMS MathViewer

by Claude-Pierre Jeannerod and Siegfried M. Rump;

Math. Comp. 87 (2018), 803-819

DOI: https://doi.org/10.1090/mcom/3234

Published electronically: July 7, 2017

PDF | Request permission

Abstract:

Rounding error analyses of numerical algorithms are most often carried out via repeated applications of the so-called standard models of floating-point arithmetic. Given a round-to-nearest function $\mathrm {fl}$ and barring underflow and overflow, such models bound the relative errors $E_1(t) = |t-\mathrm {fl}(t)|/|t|$ and $E_2(t) = |t-\mathrm {fl}(t)|/|\mathrm {fl}(t)|$ by the unit roundoff $u$. This paper investigates the possibility and the usefulness of refining these bounds, both in the case of an arbitrary real $t$ and in the case where $t$ is the exact result of an arithmetic operation on some floating-point numbers. We show that $E_1(t)$ and $E_2(t)$ are optimally bounded by $u/(1+u)$ and $u$, respectively, when $t$ is real or, under mild assumptions on the base and the precision, when $t = x \pm y$ or $t = xy$ with $x,y$ two floating-point numbers. We prove that while this remains true for division in base $\beta > 2$, smaller, attainable bounds can be derived for both division in base $\beta =2$ and square root. This set of optimal bounds is then applied to the rounding error analysis of various numerical algorithms: in all cases, we obtain significantly shorter proofs of the best-known error bounds for such algorithms, and/or improvements on these bounds themselves.

References

Richard Brent, Colin Percival, and Paul Zimmermann, Error bounds on complex floating-point multiplication, Math. Comp. 76 (2007), no. 259, 1469–1481. MR 2299783, DOI 10.1090/S0025-5718-07-01931-X
T. J. Dekker, A floating-point technique for extending the available precision, Numer. Math. 18 (1971/72), 224–242. MR 299007, DOI 10.1007/BF01397083
Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete mathematics, 2nd ed., Addison-Wesley Publishing Company, Reading, MA, 1994. A foundation for computer science. MR 1397498
G. H. Hardy, J. E. Littlewood, and G. Pólya, Inequalities, Cambridge, at the University Press, 1952. 2d ed. MR 46395
Nicholas J. Higham, Accuracy and stability of numerical algorithms, 2nd ed., Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2002. MR 1927606, DOI 10.1137/1.9780898718027
J. E. Holm, Floating-Point Arithmetic and Program Correctness Proofs, Ph.D. thesis, Cornell University, Ithaca, NY, August 1980, pp. vii+133.
T. E. Hull, T. F. Fairgrieve, and P. T. P. Tang, Implementing complex elementary functions using exception handling, ACM Trans. Math. Software 20 (1994), no. 2, 215–244.
Claude-Pierre Jeannerod, Peter Kornerup, Nicolas Louvet, and Jean-Michel Muller, Error bounds on complex floating-point multiplication with an FMA, Math. Comp. 86 (2017), no. 304, 881–898. MR 3584553, DOI 10.1090/mcom/3123
Claude-Pierre Jeannerod, Nicolas Louvet, Jean-Michel Muller, and Adrien Panhaleux, Midpoints and exact points of some algebraic functions in floating-point arithmetic, IEEE Trans. Comput. 60 (2011), no. 2, 228–241. MR 2815427, DOI 10.1109/TC.2010.144
Claude-Pierre Jeannerod and Siegfried M. Rump, Improved error bounds for inner products in floating-point arithmetic, SIAM J. Matrix Anal. Appl. 34 (2013), no. 2, 338–344. MR 3038111, DOI 10.1137/120894488
W. Keller, Prime factors $k \cdot 2^n + 1$ of Fermat numbers ${F}_m$ and complete factoring status, August 2016, web page available at http://www.prothsearch.net/fermat.html.
Donald E. Knuth, The art of computer programming. Vol. 2, Addison-Wesley, Reading, MA, 1998. Seminumerical algorithms; Third edition [of MR0286318]. MR 3077153
P. W. Markstein, Computation of elementary functions on the IBM RISC System/6000 processor, IBM J. Res. Develop. 34 (1990), no. 1, 111–119. MR 1057659, DOI 10.1147/rd.341.0111
Takeshi Ogita, Siegfried M. Rump, and Shin’ichi Oishi, Accurate sum and dot product, SIAM J. Sci. Comput. 26 (2005), no. 6, 1955–1988. MR 2196584, DOI 10.1137/030601818
Siegfried M. Rump and Claude-Pierre Jeannerod, Improved backward error bounds for LU and Cholesky factorizations, SIAM J. Matrix Anal. Appl. 35 (2014), no. 2, 684–698. MR 3211033, DOI 10.1137/130927231
Siegfried Rump, Takeshi Ogita, and Shin’ichi Oishi, Accurate floating-point summation. I. Faithful rounding, SIAM J. Sci. Comput. 31 (2008), no. 1, 189–224. MR 2460776, DOI 10.1137/050645671
N. J. A. Sloane and D. W. Wilson, Sequence A019434, The On-Line Encyclopedia of Integer Sequences, published electronically at http://oeis.org.
Pat H. Sterbenz, Floating-point computation, Prentice-Hall Series in Automatic Computation, Prentice-Hall, Inc., Englewood Cliffs, NJ, 1974. MR 349062
J. H. Wilkinson, Error analysis of floating-point computation, Numer. Math. 2 (1960), 319–340. MR 116477, DOI 10.1007/BF01386233