floating-point - 如何衡量计算误差

Question

考虑以下示例。有一个图像，用户可以在其中选择矩形区域（其中的一部分）。图像以一定比例显示。然后我们改变比例，我们需要重新计算新的选择坐标。让我们取宽度，

newSelectionWidth = round(oldSelectionWidth / oldScale * newScale)

其中oldScale = oldDisplayImageWidth / realImageWidth, newScale = newDisplayImageWidth / realImageWidth, 除尺度外的所有值都是整数。

问题是如何证明newSelectionWidth = newDisplayImageWidth给定oldSelectionWidth = oldDisplayImageWidth的任何值oldDisplayImageWidth, newDisplayImageWidth, realImageWidth? 或者在什么条件下不成立？

我也在考虑答案，这就是我想出的，可能不准确和/或不完整。

JavaScript 中的所有数字都是双精度数字。通常，这给我们带来的最大误差约为 10 ^-16 ( machine epsilon )。这意味着为了获得 0.5 或更大的误差，(1)我们需要执行 0.5 / 10 ^-16 = 5·10 ¹⁵次操作。另一个错误来源是计算太大 (|value| > 1.7976931348623157·10 ³⁰⁸ ) 或太低的数字 (|value| < 2.2250738585072014·10 ^-308 ) (链接)。这意味着（2）如果在计算过程中的某个地方我们得到太大或太低的数字，例如因为 oldDisplayImageWidth / realImageWidth > 1.7976931348623157·10 ³⁰⁸或类似的，那么误差可能会超过 0.5。当然，我们谈论的是在今天的显示器上显示图像，所有这些情况都极不可能发生。

Answer 1

您混淆了绝对误差和相对误差。假设相对误差为 10^-16，在示例中的 4 次操作之后，您最终得到的最大相对误差为 4 * 10^-16。你想要一个绝对误差 < 0.5，所以你很好，只要newSelectionWidth * 4 * 10^-16 < 0.5.

Answer 2

如果 newDisplayWidth 小于 1125899906842624 并且其他整数为正且不超过 53 位，则newSelectionWidth等于newDisplayWidth。一个证明如下。

符号：

• 我将使用该术语double来命名所使用的浮点类型，即 IEEE-754 64 位二进制。
• 样式中的文本code表示计算值，而纯文本表示数学值。因此 1/3 恰好是三分之一，而 1/3 是1./3.浮点运算中 1 除以 3 的结果。

我假设：

• 宽度是不大于double有效数字（53 位）的正整数。
• 除法oldDisplayImageWidth / realImageWidth和newDisplayImageWidth / realImageWidth以double算术方式执行，操作数转换为double。

对整数的限制确保转换double为准确，并且在此问题中使用的操作期间不会遇到上溢和下溢。

考虑oldScale，这是一double组oldDisplayImageWidth / realImageWidth。在舍入到最近模式下，单个浮点运算的最大误差是 ULP 的一半（因为每个数学数字与可表示数字的距离不超过 ULP 的一半）。因此，oldScale等于 oldDisplayImageWidth / realImageWidth • (1+e ₀ )，其中 e ₀表示相对误差，最多为半个doubleepsilon。（doubleepsilon 是 2 ^-52，所以 |e ₀ | ≤ 2 ^-53。）

同样，newScale是 newDisplayImageWidth / realImageWidth • (1+e ₁ )，其中 e ₁是一些误差，最多为 2 ^-53。

然后oldSelectionWidth / oldScale是 oldSelectionWidth / oldScale• (1+e ₂ )，同样对于某些 e ₂ ≤ 2 ^-53，并且oldSelectionWidth / oldScale * newScale是 oldSelectionWidth / oldScale• (1+e ₂ ) • newScale• (1+oldSelectionWidth / oldScale• (1+e ₃ )。注意这是传递给round.

现在将我们的表达式替换为oldScaleand newScale。这产生 oldSelectionWidth / (oldDisplayImageWidth / realImageWidth • (1+e ₀ )) • (1+e ₂ ) • (newDisplayImageWidth / realImageWidth • (1+e ₁ )) • (1+e ₃ )。realImageWidth 项取消，我们可以重新排列其他项以产生 oldSelectionWidth • newDisplayImageWidth / oldDisplayImageWidth • (1+e ₁ ) • (1+e ₂ ) • (1+e ₃ ) / (1+e ₀ )。

给定 oldSelectionWidth 等于 oldDisplayImageWidth，因此它们取消，并且参数round恰好是：newDisplayImageWidth • (1+e ₁ ) • (1+e ₂ ) • (1+e ₃ ) / (1+e ₀ )。

考虑组合误差项减一（这是最终值中的相对误差）： (1+e ₁ ) • (1+e ₂ ) • (1+e ₃ ) / (1+e ₀ ) – 1。当 e ₀为 –2 ^-53并且其他为 +2 ^-53时，表达式的幅度最大。然后它略大于 2 ULP（最多 324518553658426753804753784799233 / 730750818665451377972204001751459814038961127424）。如果 newDisplayImageWidth 小于 1125899906842624，则 newDisplayImageWidth 乘以这个相对误差小于 ½。因此，newDisplayImageWidth • (1+e ₁ ) • (1+e ₂ ) • (1+e ₃ ) / (1+e ₀) 将在 newDisplayImageWidth 的 ½ 以内。

由于 newDisplayImageWidth 是一个整数，如果 to 的参数round在 newDisplayWidth 的 ½ 范围内，则结果为 newDisplayWidth。

因此，如果 newDisplayWidth 小于 1125899906842624，则newSelectionWidth等于newDisplayWidth.

（以上证明1125899906842624是一个足够的限制，但可能没有必要。更复杂的分析可能能够证明某些错误组合是不可能的，因此最大组合错误小于上面使用的。这将放宽限制，允许更大的 newDisplayWidth 值。）