布伦特方法(Brent‘s method)---结合二分法、割线法和逆二次插值法的求根方法

本文主要是介绍布伦特方法(Brent‘s method)---结合二分法、割线法和逆二次插值法的求根方法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

基础介绍：

给定给定区间 $\left [ a,b \right ]$ ，函数连续且 $f(a)\cdot f(b)<0$ ，那么根据介值定理，函数必然在区间内有根。

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

布伦特方法：

初始化区间 $(a_{0},b_{0})$ 使得 $f(a_{0})\cdot f(b_{0})<0$ 。其中 $b_{k}$ 是上次迭代中的根估计值。如果 $\left | f(a_{0}) \right |<\left | f(b_{0}) \right |$ ,那么赋值互换（我们认为对应函数值的绝对值较小的点更接近真正的根值）。

每次迭代包含四个点：

$b_{k}$ ：为当前迭代的根估算值；
$a_{k}$ ：对位点，即满足 $\left | f(a_{k}) \right |<\left | f(b_{k}) \right |$ 且 $f(a_{k})\cdot f(b_{k})<0$ 的值。
$b_{k-1}$ ：上一次迭代的根估算值，第一次迭代设置为 $b_{k-1}=a_{0}$
$b_{k-2}$ ：上上此迭代的根估算值（不用初始化，在首次迭代过程中，不会用到他来进行判断，结尾进行赋值）。