点积的最坏情况精度是多少？

2018-06-30 16:32:37

假设处理器只有符合IEEE-754的'fadd'和'fmul'操作（没有'dot'或'fma'指令）。通过点积操作的简单实现将实现最差的准确度。例如，对于长度为3的矢量：

dot(vec_a, vec_b) = vec_a.x*vec_b.x + vec_a.y*vec_b.y + vec_a.z*vec_b.z

这是我的分析，但我不确定它是否正确：对于长度为N的向量，有N次乘法和N-1次加法，导致2N-1次浮点运算。在最坏的情况下，对于这些操作中的每一个，表示对于准确的结果来说都太小，所以中间结果将被舍入。每个舍入加起来为0.5 ULP错误。所以最大误差为（2N-1）* 0.5 = N-1/2 ULP？

与许多FP错误分析一样，错误强烈依赖于输入的最大量值。在这种情况下，粗略和准备好的误差界限是2 * FLT_EPS * dot(abs(vec_a), abs(vec_b)) ，其中abs表示矢量的元素绝对值。

你的推理不适用于增加：如果a和b已经不准确，每个0.5 ULP和a接近-b ，那么a + b的相对准确性可能很差，比1.5 ULP差得多。事实上，如果没有关于计算点积的向量的进一步信息，就不能保证结果的相对准确性。

当只有乘法时，你的推理线是可以的，但它忽略了复杂的错误。

考虑等式：（a + ea）（b + eb）= ab + aeb + bea + eaeb。

如果假设a和b都在1和2之间，那么在两个已经精确到0.5 ULP的结果相乘后的总相对误差只能在粗略的一次近似下估计为1 ULP，并且仍然是忽略误差项eaeb和乘法本身的误差。使浮点乘法的结果的总相对误差为1.5 ULP，这只是一个粗略的平均值，而不是一个声音的最大值。

我的这些同事已经形式化并且证明了双精度浮点积的准确性的概念。将它们的结果翻译成英文是，如果每个向量分量的范围为1.0 ，那么点积的最终结果精确到NMAX * B，其中NMAX是向量的维数，B是取决于NMAX的常量。链接页面上提供了一些值：

NMAX     10            100            1000
B        0x1.1p-50     0x1.02p-47     0x1.004p-44

在他们的结果中，可以用任何两个 P的任意幂代入1.0以确保没有溢出，并且点积的绝对误差变为NMAX * B * P2。循环不变量分别变为：

@ loop invariant abs(exact_scalar_product(x,y,i)) <= i * P * P;
@ loop invariant abs(p - exact_scalar_product(x,y,i)) <= i * B * P * P;

链接地址: http://www.djcxy.com/p/85611.html