Page 20 - 《软件学报》2020年第12期

3686 Journal of Software 软件学报 Vol.31, No.12, December 2020

它收敛于 6.然而,“它在任何系统任何精度下均出错(and yet, on any system with any precision, the sequence
[2]
will seem to go to 100 )”.即它总是趋向 100,而不是正确答案 6.比如,图 1 中的程序在一个机器(基于 Pentium 4
的工作站 ,Linux 系统 ,Gcc) 上的几个输出结果为 u 17 =7.2356654170119432,u 20 =98.350416551346285, u 30 =
99.999999999998948.它表明:从 u 17 开始,程序的输出结果中不再含有正确有效数字,并且从 u 20 开始,结果就开始
[2]
非常接近于 100 .

#include 〈stdio.h〉
int main(void)
{
double u, v, w;
int i, max;

printf(“n=”);
scanf(“%d”,&max);
printf(“u1=”);
scanf(“%lf”,&u);
printf(“u2=”);
scanf(“%lf”,&v);
printf(“Computation from 3 to n:\n”);

for (i=3; i<=max; i++)
{
w=111.−1130./v+3000./(v*u);
u=v;
v=w;
printf(“u%d=%1.17g\n”,i,v);
}
return θ;
}
Fig.1 A C program that is supposed to compute sequence u n using double-precision arithmetic
图 1 一个 C 程序,它使用双精度计算 u n 的值

15 年后(即 2004 年),被称为“浮点之父”的图灵奖获得者 Kahan 又给出了迭代的一个变形:
⎧
⎪ =
⎪ ⎪ y 1 4
⎨ y 2 = 4.25 (2)
⎪ 815 1500
⎪y n = 108 − +
y
⎪ ⎩ y n − 1 y n − 1 n − 2
对于该变形,同样,若直接编程,则任何机器均得不到正确结果 5.比如,若在 Intel 302(i386/387 IBM PC 的一种仿
[3]
造机)上使用 FORTRAN 语言编程计算,则扩展精度下,从 y 32 开始,结果均为 100 .
虽然上述案例均是学者们构造的,但是谁能保证类似错误计算的循环迭代模型不会在实践中(特别是攸关
安全的领域)出现呢?更为可怕的是,这种错误很难被发现.首先,程序没有逻辑、语法等静态错误;其次,程序在运
行中也没有越界、溢出等动态错误;最后,即使使用高精度计算,也往往得不到正确结果.因此,该类错误计算仅得
到个别学者的关注:他们均通过变换公式将循环迭代表示成关于 n 的函数,然后利用该函数分析迭代出错的原
因 [3,4] .有鉴于此,研究循环迭代程序正确的、可信的计算算法是迫切的、必要的.
接下来,第 1 节阐明迭代的错误计算原因.然后,其余部分研究下列循环迭代的可信计算算法:

⎧ y = 1 f 1 ( ), X X = ( , ,...,x x 2 x m )
1
⎨ (3)
i
⎩ y = f i (,y y 2 ,..., y i− 1 ), if 2≤≤ n
1
i
即,讨论如何获得 y n 误差可控的结果.
1 错误计算原因
造成上述错误迭代计算的原因是,对应函数的错数 [5,6] 大于 0.下面简介错数的概念以及计算方法.
已知 f(x)为一单变元函数.任给一个自变量的取值 x 0 ,其二进制表示可能导致自变量的实际取值中包含错误