布伦特方法(Brent‘s method)

布伦特方法(Brent‘s method)

基础介绍：

给定给定区间，函数连续且，那么根据介值定理，函数必然在区间内有根。

1. 二分法：将区间不断二分，使端点不断逼近零点。下一次迭代的区间为或，其中。
2. 割线法（线性插值）：基本思想是用弦的斜率近似代替目标函数的切线斜率，并用割线与横轴交点的横坐标作为方程式的根的近似。即给定两个点,。其割线方程为，那么令，x的值即为下一次迭代的结果。
3. 逆二次插值法：为割线法的进化版本。使用三个点确定一个二次函数，二次函数与横轴交错的点即为下次迭代的值。但是，其二次函数可能不会和横轴相交，因此做出一点改变，以y值作为自变量。给定三个点,则通过这三个点确定的二次函数为，令y=0，求得

布伦特方法：

初始化区间使得。其中是上次迭代中的根估计值。如果,那么赋值互换（我们认为对应函数值的绝对值较小的点更接近真正的根值）。

每次迭代包含四个点：

1. ：为当前迭代的根估算值；
2. ：对位点，即满足且的值。
3. ：上一次迭代的根估算值，第一次迭代设置为
4. ：上上此迭代的根估算值（不用初始化，在首次迭代过程中，不会用到他来进行判断，结尾进行赋值）。

有以下四个不等式：

  ①

  ②

  ③

 ④

上次迭代为二分法且①为假；上次迭代为二分法且③为假；上次迭代为插值法且②为假；上次迭代为插值法且④为假；以插值法计算的临时值不在和 中间，以上五个条件满足一个，那么本次迭代的值采用二分法，否则采用插值法。

而插值法的选择如下：如果三点各不同，则用二次插值；否则用线性插值。

本次迭代的临时值s作为区间的一个端点，另一个端点在和中选择，二者作为，且满足,。