language-agnostic - 多项式的天真评估如何不利于准确性？

Question

在此代码审查答案中:

https://codereview.stackexchange.com/a/59405/11633

我发现了以下内容(前面的嵌套引用!):

Let me quote the wonderful book Numerical Recipes in C++ (but also applicable)

We assume that you know enough never to evaluate a polynomial this way:

p=c[0]+c[1]*x+c[2]*x*x+c[3]*x*x*x+c[4]*x*x*x*x;

or (even worse!),

p=c[0]+c[1]*x+c[2]*pow(x,2.0)+c[3]*pow(x,3.0)+c[4]*pow(x,4.0);

Come the (computer) revolution, all persons found guilty of such criminal behavior will be summarily executed, and their programs won’t be!

(你可以在分析索引中找到你版本中的页面，在条目“双关语，特别糟糕”下。我喜欢这本书。)

不这样做的原因有两个:准确性和性能。计算多项式的正确方法是这样的:

-t * (0.319381530  +  t * (-0.356563782 + t * (1.781477937 + t * (-1.821255978 + 1.330274429 * t))))

我可以看到以任何不鼓励的方式实现它的严重性能损失，但不是准确性损失。 准确性如何不好？

我找到了这本书，但在引用位周围的任何地方都没有找到这些信息。

Answer 1

每个浮点运算只是一个近似值。这种方法使用较少的操作，因此结果更准确。

当您有非常大或非常小的数字时，它还有另一个优势。假设所有系数的数量级相同，则所有项也具有相同的数量级。如果在 x=0.1 处评估系数约为 1 的 5 阶多项式，直接的方法是将 0.1 添加到 10^-5，从而降低精度。

顺便说一下，这叫做Horner's scheme.