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

Question

假设处理器只有符合 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？

Answer 1

你的理由不工作补充：如果a和b已经不准确了0.5 ULP每a接近-b，则相对精度a + b可以可怕，超过150 ULP更糟。事实上，如果没有关于您计算点积的向量的更多信息，就无法保证结果的相对准确性。

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

考虑等式：(a + e _a )(b + e _b ) = ab + ae _b + be _a + e _a e _b。

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

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

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

在他们的结果中，你可以1.0用任何足够低的 P 的幂代替以确保没有溢出，然后点积的绝对误差变为 NMAX * B * P ²。循环不变量分别变为：

@ 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;

Answer 2

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