lib(ic)的精确解决方案



使用ECLiPSe-Prolog的lib(ic),我偶然发现了David H.Bailey的以下问题,"解决科学计算中的数值异常"。Unum的书中提到了这一问题。实际上,它只是其中的一部分。首先,让我用(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页的引文,我认为这意味着数字是精确表示的(现在通过笔画)。

使用{3,5}环境,该环境可以模拟IEEE单个精度。输入值是可精确表示的
{-1,2}

这就完成了任务,用不到所用位的一半来计算精确答案。。。

否则,声明页面184保持:

0.80143857x+1.65707065y=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)

几个问题共同造成了混乱:

  1. 除了声称的以外,示例中的三个常数donot具有作为双浮点的精确表示。

  2. 最初的例子没有四舍五入,这是不对的。

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

  4. 给出的最接近的双浮点表示的精确结果常数实际上不是零而是2.2204460492503131e-16。

  5. 区间算术只能在输入是准确的,但这里的情况并非如此。常数必须是加宽为包括所需小数部分的间隔。

  6. 关系算术,就像lib(ic)提供的那样,本质上是这样的不能保证特定的评估顺序。因此,四舍五入错误可能与功能评估过程中遇到的错误不同。然而,相对于给定的常数,结果将是准确的。

下面将详细介绍。正如我将展示的点使用ECLiPSe查询,一个关于语法的快速单词:

  • 用双下划线分隔的两个浮点,例如0.99__1.01在这种情况下,用下界和上界表示区间常数一个在1附近的数字。

  • 由一个下划线分隔的两个整数,例如3_4用分子和分母表示有理常数,在这里case四分之三

若要演示点(1),请转换0.80143857变为有理数。这给出了精确的分数3609358445212343/45035949627370496,其接近但不相同,至预期的小数部分80143857/10000000。浮点因此,表示不是精确:

?- 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)

现在两个结果都包含零,并且很明显结果的准确性取决于评估顺序。

相关内容

  • 没有找到相关文章

最新更新