Sharp estimates for perturbation errors in summations
Marko Lange, Siegfried M. Rump · Mathematics of Computation · 2018
Standard Wilkinson-type error estimates of floating-point algorithms that are solely based on the first or second standard model typically involve a factor γ k := k u / ( 1 − k u ) \gamma _k:=k\mathbf {u}/(1-k\mathbf {u}) , where u \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 γ k \gamma _k can be replaced by k u k\mathbf {u} , and the restriction on k 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 u / ( 1 + k u ) k\mathbf {u}/(1+k\mathbf {u}) , again without any reference to a floating-point grid. Furthermore, an estimate of type h u h \mathbf {u} is shown for sums and dot products that are evaluated using a binary tree of height h h . Both estimates require a mandatory restriction of size 1 / u 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 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