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

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.