3

使用 ECLiPSe Prolog,lib(ic)我偶然发现了David H. Bailey 提出的以下问题,“解决科学计算中的数值异常”。Unum book提到了我。实际上,这只是其中的一部分。首先,让我根据 来制定方程(is)/2另外,请注意,所有这些十进制数字都以基数 2 浮点数(包括 IEEE)精确表示

ECLiPSe Constraint Logic Programming System [kernel]
...
Version 6.2development #21 (x86_64_linux), Wed May 27 20:58 2015
[eclipse 1]: lib(ic).
...
Yes (0.36s cpu)
[eclipse 2]: X= -1, Y = 2, Null is 0.80143857*X+1.65707065*Y-2.51270273.

X = -1
Y = 2
Null = 0.0
Yes (0.00s cpu)

所以这确实是0.0(根本没有四舍五入)。但现在与$=代替is

[eclipse 3]: X= -1, Y = 2, Null $= 0.80143857*X+1.65707065*Y-2.51270273.

X = -1
Y = 2
Null = 2.2204460492503131e-16__2.2204460492503131e-16
Yes (0.00s cpu)

此区间不包含 0.0。我知道区间算术通常有点过于近似,如下所示:

[eclipse 4]: 1 $= sqrt(1).

Delayed goals:
    0 $= -1.1102230246251565e-16__2.2204460492503131e-16
Yes (0.00s cpu)

但至少等式成立!但是,在第一种情况下,不再包括零。显然我没有理解一些东西。我也尝试过eval/1,但无济于事。

[eclipse 5]: X= -1, Y = 2, Null $= eval(0.80143857*X+1.65707065*Y-2.51270273).

X = -1
Y = 2
Null = 2.2204460492503131e-16__2.2204460492503131e-16
Yes (0.00s cpu)

Null不包括的原因是什么0.0


(在@jschimpf 出人意料的回答之后编辑)

这是书中第 187 页的引文,我将其解释为数字被精确表示(现在划线)。

使用可以模拟 IEEE精度的 {3,5} 环境。输入值是完全可表示的。...
{-1, 2}
...完成了
这项工作,用不到...

否则,第 184 页的声明成立:

...

0.80143857 x + 1.65707065 y = 2.51270273

这些方程式当然看起来很无辜。假设精确的十进制输入,该
系统由x = -1 和y = 2 精确求解。

这是用 SICStus 重新检查的library(clpq)

| ?- {X= -1,Y=2,
     A = 80143857/100000000,
     B = 165707065/100000000,
     C = 251270273/100000000,
     Null = A*X+B*Y-C}.
X =  -1,
Y = 2,
A = 80143857/100000000,
B = 33141413/20000000,
C = 251270273/100000000,
Null = 0 ? 
yes

所以 -1, 2 是确切的解决方案。


精确的配方

这是一个在输入系数中没有舍入问题的重新表述,但解决方案仍然只是 -∞...+∞。因此,微不足道的正确,但不可用。

[eclipse 2]: A = 25510582, B = 52746197, U = 79981812, 
C = 80143857, D = 165707065, V = 251270273,
A*X+B*Y$=U,C*X+D*Y$=V.

A = 25510582
B = 52746197
U = 79981812
C = 80143857
D = 165707065
V = 251270273
X = X{-1.0Inf .. 1.0Inf}
Y = Y{-1.0Inf .. 1.0Inf}


Delayed goals:
    52746197 * Y{-1.0Inf .. 1.0Inf} + 25510582 * X{-1.0Inf .. 1.0Inf} $= 79981812
    80143857 * X{-1.0Inf .. 1.0Inf} + 165707065 * Y{-1.0Inf .. 1.0Inf} $= 251270273
Yes (0.00s cpu)
4

1 回答 1

6

这里有几个问题共同造成混乱:

  1. 除了声明之外,示例中的三个常量没有精确的表示为双浮点数。

  2. 最初的例子不涉及四舍五入是不正确的。

  3. 第一个示例中看似正确的结果实际上是由于幸运的舍入误差。其他计算顺序给出不同的结果。

  4. 给定常数的最接近的双浮点表示,确切的结果确实不是零,而是 2.2204460492503131e-16。

  5. 区间算术只有在输入准确时才能给出准确的结果,但这里并非如此。必须将常数扩大到包含所需小数部分的区间。

  6. 像 lib(ic) 提供的关系算术本质上不能保证特定的评估顺序。因此,舍入误差可能与功能评估期间遇到的误差不同。然而,对于给定的常数,结果将是准确的。

下面会更详细一点。正如我将使用 ECLiPSe 查询演示的一些要点,提前简要介绍一下语法:

  • 由双下划线分隔的两个浮点数,例如0.99__1.01 表示具有下限和上限的区间常数,在本例中为 1 附近的数字。

  • 由单个下划线分隔的两个整数,例如3_4 用分子和分母表示有理常数,在本例中为四分之三

为了演示第 (1) 点,将 0.80143857 的浮点表示转换为有理数。这给出了精确的分数 3609358445212343/4503599627370496,它与预期的十进制分数 80143857/100000000 接近但不相同。因此,浮点表示准确:

?- F is rational(0.80143857), F =\= 80143857_100000000.
F = 3609358445212343_4503599627370496
Yes (0.00s cpu)

下面显示了结果如何依赖于评估顺序(上面的第 3 点;请注意,我通过去掉不相关的乘法来简化了原始示例):

?- Null is -0.80143857 + 3.3141413 - 2.51270273.
Null = 0.0
Yes (0.00s cpu)

?- Null is -2.51270273 + 3.3141413 - 0.80143857.
Null = 2.2204460492503131e-16
Yes (0.00s cpu)

顺序相关性证明会发生舍入误差(第 2 点)。对于那些熟悉浮点运算的人来说,实际上很容易看出,当添加 时, 在调整操作数的指数时会丢失-0.80143857 + 3.3141413两位精度。0.80143857事实上,正是这个幸运的舍入错误为 OP 提供了看似正确的结果!

实际上,关于常量的浮点表示,第二个结果更准确。我们可以通过使用精确的有理算术重复计算来证明这一点:

?- Null is rational(-0.80143857) + rational(3.3141413) - rational(2.51270273).
Null = 1_4503599627370496
Yes (0.00s cpu)

?- Null is rational(-2.51270273) + rational(3.3141413) - rational(0.80143857).
Null = 1_4503599627370496
Yes (0.00s cpu)

由于加法是通过精确的有理数完成的,因此结果现在与顺序无关,并且因为1_4503599627370496 =:= 2.2204460492503131e-16,这证实了上面获得的非零浮点结果(第 4 点)。

区间算术在这里有什么帮助?它通过计算包含真实值的间隔来工作,这样结果就输入而言始终是准确的。因此,具有包含所需真实值的输入间隔(ECLiPSe 术语中的有界实数)至关重要。这些可以通过明确地写下来获得,例如0.80143856__0.80143858;通过从一个精确的数字转换,例如一个有理数使用 breal(80143857_100000000);或者通过指示解析器自动将所有浮点数扩展为有界实数区间,如下所示:

?- set_flag(syntax_option, read_floats_as_breals).
Yes (0.00s cpu)

?- Null is -0.80143857 + 3.3141413 - 2.51270273.
Null = -8.8817841970012523e-16__1.3322676295501878e-15
Yes (0.00s cpu)

?- Null is -2.51270273 + 3.3141413 - 0.80143857.
Null = -7.7715611723760958e-16__1.2212453270876722e-15
Yes (0.00s cpu)

两个结果现在都包含零,并且结果的精度如何取决于评估顺序变得很明显。

于 2015-06-27T00:18:23.623 回答