我想减少以下计算中的数值浮点错误。
我有以下形式的等式:
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”。
最佳答案
您的计算看起来类似于 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]) 似乎您会得到想要的结果,但我没有试过了。
关于c++ - 嵌套积的精确求和,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10989521/