## Sharp estimates for perturbation errors in summations

HTML articles powered by AMS MathViewer

- by
Marko Lange and Siegfried M. Rump
**HTML**| PDF - Math. Comp.
**88**(2019), 349-368

## Abstract:

Standard Wilkinson-type error estimates of floating-point algorithms that are solely based on the first or second standard model typically involve a factor $\gamma _k:=k\mathbf {u}/(1-k\mathbf {u})$, where $\mathbf {u}$ denotes the relative rounding error unit of a floating-point number system. Using specific properties of floating-point grids it was shown that often $\gamma _k$ can be replaced by $k\mathbf {u}$, and the restriction on $k$ can be removed. That is true for standard algorithms such as summation, dot product, matrix multiplication, and LU- or Cholesky decomposition.

Recently it was shown that, at least for summation and dot product, such results derive without any reference to a floating-point grid. In the current paper we further sharpen the error estimate for summation into $k\mathbf {u}/(1+k\mathbf {u})$, again without any reference to a floating-point grid. Furthermore, an estimate of type $h \mathbf {u}$ is shown for sums and dot products that are evaluated using a binary tree of height $h$. Both estimates require a mandatory restriction of size $1/\mathbf {u}$ on the number of summands and the height, respectively.

Finally, a different kind of error estimate is shown for recursive summation. The discussed bound is sharp, holds true for any number of summands, and is uniformly bounded by $1$.

The novelty of our approach is twofold. First, rather than using a rounding function, the discussed estimates are based on almost arbitrary perturbations of real operations without any reference to a floating-point grid. As a consequence, the corresponding floating-point error bounds in some base $\beta$ for rounding to nearest, and partly also for directed roundings, follow as corollaries. Second, in regard to our weak assumptions, the new estimates are sharp. Our main result is sharp for actual realizations of grids floating-point arithmetics are based on. To be more specific, for any feasible problem size, for IEEE $754$ binary$32$ as well as binary$64$ format, there are examples satisfying the given bound with equality.

## References

- 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 - 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 - Donald E. Knuth,
*The art of computer programming. Vol. 1*, Addison-Wesley, Reading, MA, 1997. Fundamental algorithms; Third edition [of MR0286317]. MR**3077152** - Marko Lange and Siegfried M. Rump,
*Error estimates for the summation of real numbers with application to floating-point summation*, BIT**57**(2017), no. 3, 927–941. MR**3702927**, DOI 10.1007/s10543-017-0658-9 - Walter F. Mascarenhas,
*Floating point numbers are real numbers*, 2016. - Siegfried M. Rump, Florian Bünger, and Claude-Pierre Jeannerod,
*Improved error bounds for floating-point products and Horner’s scheme*, BIT**56**(2016), no. 1, 293–307. MR**3486462**, DOI 10.1007/s10543-015-0555-z - 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

## Additional Information

**Marko Lange**- Affiliation: Waseda University, Faculty of Science and Engineering, 3–4–1 Okubo, Shinjuku-ku, Tokyo 169–8555, Japan
- MR Author ID: 1082372
- Email: m.lange@aoni.waseda.jp
**Siegfried M. Rump**- Affiliation: Institute for Reliable Computing, Hamburg University of Technology, Am Schwarzenberg-Campus 1, Hamburg 21071, Germany; and Visiting Professor at Waseda University, Faculty of Science and Engineering, 3–4–1 Okubo, Shinjuku-ku, Tokyo 169–8555, Japan
- MR Author ID: 151815
- Email: rump@tuhh.de
- Received by editor(s): August 30, 2017
- Published electronically: March 19, 2018
- Additional Notes: This research was partially supported by CREST, Japan Science and Technology Agency (JST)
- © Copyright 2018 Marko Lange and Siegfried M. Rump
- Journal: Math. Comp.
**88**(2019), 349-368 - MSC (2010): Primary 65G50, 65F05
- DOI: https://doi.org/10.1090/mcom/3355
- MathSciNet review: 3854061