c - 布伦特寻根算法的流行实现中的“e”变量是什么？

Question

我正在阅读布伦特根查找算法的标准（数字食谱和GSL C 版本相同）实现 ，并且无法理解变量“e”的含义。用法表明“e”应该是括号之间的先前距离。但是，当我们使用二分法时，为什么它设置为“xm”（距离的一半）？

Answer 1

我不熟悉算法。但是，我可以比较算法的 C 源代码和Wikipedia 描述。该算法看起来很简单（如果您熟悉查找根的方法），但 C 实现看起来像是 fortran 的直接端口，因此很难阅读。

我最好的猜测是这e与循环条件有关。

维基百科说（算法的第 8 行）： repeat until f(b or s) = 0 or |b − a| is small enough (convergence)

C 源代码说： e = b - a，然后是if (fabs(e) <= tol ...。

我希望书中能清楚地描述变量的目的，但显然不是:)

---

好的，给你。我在这里找到了原始实现（在 algol 60 中）。除了对算法的一个很好的描述外，它还说（从第 50 页开始）：

让是最后一步之前的一步e的值。p/q如果|e|< δ 或|p/q|≥1/2|e|则进行二等分，否则我们进行二等分或插值，就像在 Dekker 算法中一样。因此|e|，每第二步至少减少两倍，并且当|e|< δ 时，必须进行二等分。（在二等分之后，我们e = m进行下一步。）

所以增加的e是布伦特对德克尔算法的“主要修改”。

Answer 2

E 是“epsilon”变量，它基本上是衡量足够接近的程度。您的特定应用程序可能不需要 20 位精度，因此 epsilon 可以让您平衡它需要多少次迭代（即运行多长时间）与您需要的精度。

对于浮点数，您可能无法准确，因此 epsilon 应该是一些小的非零数。实际值取决于您的应用程序......它基本上是最大的可接受错误。

Answer 3

在二等分步骤中，间隔正好减半。因此，保持区间当前宽度的 e 也减半。