Let and be distinct floating point numbers. How small can the relative difference between and be? For IEEE double precision arithmetic the answer is , which is called the unit roundoff.
What if we now let and be vectors and define the relative difference as , where the infinity norm is ? It does not seem to be well known that can be much less than . I have observed this phenomenon numerous times over the years but had not previously stopped to wonder how it could happen. An example is
Notice that the largest element(s) in magnitude of agrees with the corresponding element(s) of . This is, in fact, the only way that is possible.
Theorem (Dingle & Higham, 2013).
Let and be -vectors of normalized floating point numbers.
If then for all such that .
This result, and the scalar case mentioned above, are proved in
Nicholas J. Higham and Nicholas J. Dingle, Reducing the Influence of Tiny Normwise Relative Errors on Performance Profiles, MIMS EPrint 2011.90; to appear in ACM Trans. Math. Soft.
Performance profiles, introduced by Dolan and Moré in 2002, are a popular way to compare competing algorithms according to particular measures of performance, such as relative error or execution time. We show in the paper above that tiny relative errors can result in misleading performance profiles and show how a simple transformation of the data can lead to much more useful profiles. For more, see the paper or the talk Numerical Issues in Testing Linear Algebra Algorithms that I gave at the SIAM Conference on Computational Science and Engineering in Boston last week.