帮助理解 Brent 的求根方法

计算科学 寻根
2021-12-13 15:39:48

帮助我理解 Brent 的求根算法的一部分。在一个典型的迭代中,我们有样本 (a,fa), (b,fb), (c,fc) 都是实数的 (a<b<c) 或 (c<b<a) 。此外,在我对 (1< fa/fb) 和 (fc/fb <= -1) 感兴趣的情况下。在这种情况下(使用 Mathematica 语法),该算法尝试按如下方式进行逆二次插值:

xm=(c-b)/2;
s=fb/fa;
q=fa/fc;
r=fb/fc;
p=s*(2*xm*q*(q-r)-(b-a)(r-1));
q=(q-1)(r-1)(s-1);
If[0<p,q=-q];
p=Abs[p];
If[2*p-Min[Abs[e*q],3*xm*q-Abs[tol*q]]<0,
  "Accept Inverse Quadratic Interpolation",(* else *)"Take a Bisection Step"
]

认为

Abs[e*q] > 3*xm*q-Abs[tol*q]

还假设 (tol) 大约为零。那么 If 条件是有效的:

2*p-3*xm*q<0

请解释为什么在条件中使用它,并提供满足上述不等式的 (a,fa),(b,fb),(c,fc) 的值并使我们处于接受逆二次的边缘插值。

1个回答

我在考虑下面的蓝色和橙色曲线等情况。对于蓝色曲线 (a,fa)=(0,2.5); (b,fb)=(2.2,0.5); (c,fc)=(5,-0.5)。对于黄橙色曲线 (a,c,fa,fb,fc) 相同且 (b=1.2)。在每种情况下,逆二次插值都会给出类似于使用割线步长的近似根,并且从 b 到新近似根的距离小于 0.5(cb)。 图1

Brent 方法中使用的 If 条件边缘的一个示例是下面的蓝色曲线,其中 (a,fa)=(0,2.5); (b,fb)=(0.5,4.4444444444444455); (c,fc)=(5,-0.5)。布伦特方法拒绝逆二次插值的一个例子是下面的橙黄色曲线,其中 (a,b,c,fb,fc) 与蓝色曲线相同,但 (fa=1.3)。下面的蓝色曲线在 x=c=5 处变得尽可能正确。蓝色曲线与 x 轴相交的点将是 x=b+(cb)*3/4 处的下一个近似根。该值正好在接受插值的边缘。 图2