c++ - 嵌套积的精确求和

Question

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

我有以下形式的等式:

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

其中变量 w 表示 [0,1] 范围内的某个 float ，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 求和算法(Kahan 1965)，或者 Higham 1993 或 McNamee 2004 中的其他几种方法之一来限制误差的大小。如果我在做在线重复产品，我可以使用某种转换技术将问题简化为求和。

实际上，我不确定如何解决这个特定问题。有没有人有想法(以及与之相关的引文)？

谢谢!

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

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

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

Answer 1

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

有补偿 Horner 方案的算法，我认为您可以根据自己的目的进行调整。例如，参见以下论文中的定理 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]) 似乎您会得到想要的结果，但我没有试过了。