c - 布伦特根查找算法的流行实现中的 "e"变量是什么？

Question

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

Answer 1

我不熟悉算法。但是，我可以比较 C 源代码和 Wikipedia description的算法。该算法看起来很简单(如果您熟悉求根的方法)，但 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 中)here .除了对算法的很好描述外，它还说(从第 50 页开始):

let e be the value of p/q at the step before the last one. If |e|< δ or|p/q| ≥ 1/2|e| then do a bisection, otherwise we do either a bisection or interpolation just as in Dekker's algorithm. Thus |e| decreases by at least a factor of two on every second step, and when |e|< δ a bisection must be done. (After a bisection we take e = m for the next step.)

所以增加e是 Brent 对 Dekker 算法的“主要修改”。