1

我想减少以下计算中的数值浮点错误。

我有以下形式的方程：

b_3+w_3*(b_2+w_2*(b_1+w_1*(b_0+w_0)))

其中变量w表示范围内的某个浮点数[0,1]，并b表示范围内的浮点常数[1,~1000000]。b随下标单调增加（尽管这可能并不重要）。当然，这可以扩展到任意数量的术语：

b_4+w_4*(c_3+w_3*(b_2+w_2*(b_1+w_1*(b_0+w_0))))

这可以递归定义为：

func(x,n):
   if(n==MAX)
      return x
   else
      return func(b[n]+x*w[n],n+1)

func(1,0)

如果我在进行在线求和，我可以使用 Kahan Summation Algorithm (Kahan 1965)，或其他几种方法之一，如 Higham 1993 或 McNamee 2004，来限制我的错误大小。如果我在做在线重复产品，我可以使用某种转换技术将问题简化为求和。

事实上，我不确定如何解决这个特定问题。有没有人有想法（和引用与他们一起去）？

谢谢！

Higham 1993。“浮点求和的准确性”。SIAM 科学计算杂志。

Kahan 1965。“实践：关于减少截断错误的进一步评论”。CACM。“10.1145/363707.363723”。

McNamee 2004。“准确求和方法的比较”。SIGSAM 公牛。“10.1145/980175.980177”。

4

2 回答 2

3

您的计算看起来类似于霍纳方案，除了不是单个变量 x，而是在每个阶段使用不同的权重 w[i]。

有补偿霍纳方案的算法，我认为您可以根据自己的目的进行调整。例如，请参见以下论文中的定理 3 和算法 2。

P. Langlois，如何使用补偿霍纳算法确保忠实的多项式评估。第 18 届 IEEE 计算机算术研讨会，2007 年 6 月 25 日至 27 日，ARITH '07，第 141-149 页， http: //www.acsel-lab.com/arithmetic/papers/ARITH18/ARITH18_Langlois.pdf

如果在算法 2 中将 TwoProd (s[i+1], x) 替换为 TwoProd (s[i+1], w[i+1]) ，您似乎会得到想要的结果，但我还没有尝试过。

于 2012-06-12T03:29:19.580 回答
0

按照您定义的方式func，它的计算结果为以下表达式：

For MAX = n+1, func(1,0) ==

     n     n
   \---  -----
1 + >     | |  w[j]
   /---   | | 
    i=0  j=n-i

所以，我解决总和的方法是：

double s = 0.0;
double a = 1.0;
for (int i = 1; i <= MAX; ++i) {
    a *= w[MAX-i];
    s += a;
}
return 1.0 + s;

即使我们将x输入值func视为变量，它也只会影响最后一项。但由于它的范围，你应该小心计算它。

double s = 0.0;
double a = 1.0;
double ax = x;
for (int i = 1; i < MAX; ++i) {
    a *= w[MAX-i];
    ax *= w[MAX-i];
    s += a;
}
ax *= w[0];
s += ax;
return 1.0 + s;
于 2012-06-12T02:43:37.720 回答