非线性方程求根方法总结——（从二分法、试位法到牛顿迭代、弦截法、二次插值等）

$f(x)=0$

1 划界法

函数通常在其根附近改变符号。利用两个初始值，这两个初始值必须位于跟的两侧。利用中值定理，必存在一个根落在区间内。利用这个性质，不断地缩小根的区间范围，直到足够接近结果为止。这类方法称为“划界法”。

1.1 二分法

思路：
若已知$f(a)<0$且$f(b)>0$，根据中值定理，必存在一个根落在区间(a, b)内。因此，

1. 取区间(a, b)的中点，计算中点的值$f(x)=f((a+b)/2)$；
2. 若$f((a+b)/2)$与$f(b)<0$同号，则将区间终点b替换成(a+b)/2，此时区间变成了$(a,(a+b)/2)$; 若$f((a+b)/2)$与$f(b)<0$异号，则将区间起点a替换成(a+b)/2，此时区间变成了$((a+b)/2,b)$;
3. 重复上述步骤1、2直到$f(x)$接近为0，结束。

要求：已知两个点a，b的值$f(a)<0$且$f(b)>0$异号

收敛速度：线性收敛

缺点：收敛速度慢

伪代码：

1.1 试位法

实现思路与二分法类似，只不过二分法是直接取区间的中点，试位法利用式（5.7）得到一个x值，然后计算在该值下的$f(x)$，其余步骤2、3与二分法相同。

要求：（同二分法一样）已知两个点a，b的值$f(a)<0$且$f(b)>0$异号

收敛速度：

缺点：在某些情况下收敛很慢，如下图。

1.3 改进试位的法思路

缓和试位法的片面性特征的一种方式是让算法检测一个边界是否固定不变。如果出现这种情况，可以将停滞的边界点处的函数值变为原来的一半。
注意，算法使用计数器来确定一个边界在两次迭代过程中是否保持不变，如果是，停滞的边界点的函数值将变为原来的一半。可以考虑当连续三次以上某一边界值保持不变的时候，就将该值减半。

1.4 划界法的问题

划界法（二分法和试位法等）实际应用时存在一个很大的问题就是，必须直到两个符号相反的初始值，有时候很难去找这样两个初始值。

2 开方法

2.1 定点迭代法

根据当前x的预测下一个x的值，从而不断的接近方程的根。
由 $f(x)=0$ 得： $x=f(x)-x$
一个简单的预测方法就是：$x_{i+1}=f(x_i)-x_i$

收敛条件：令$g(x)=f(x)-x$，当$|g^{{}^{\prime }}(x)|<1$时收敛。

缺点：不一定收敛

2.2 牛顿迭代法（牛顿迭代法也是一种定点迭代法）

上面的定点迭代法预测的效果实在太差。
根据泰勒级数展开可得：$f(x_{i+1})=f(x_i)+f^{{}^{\prime }}(x_i)(x_{i+1}-x_i)+o(x^2)$
因此：$f(x_{i+1})\approx f(x_i)+f^{{}^{\prime }}(x_i)(x_{i+1}-x_i)$
得：
$x_{i+1}=x_i-\frac{f(x_i)}{f^{{}^{\prime }}(x_i)}$

最大的优点：二阶收敛，收敛速度快！！！！

缺点：也有不收敛的情况。此外，需要函数能够准确计算一阶导数。并且，二重根得位置，收敛也很慢。

3 弦截法

3.1 弦截法

也称正割法。
牛顿迭代收敛很快，但是也存在一个问题，就是要能方便计算函数的一阶导数。而有些函数计算导数很困难，于是就想，能不能用近似的导数行不行，于是产生了一个想法，就是用有限差商来逼近导数。如下：

于是就得到了正割法：
$x_{i+1}=x_i-\frac{f(x_i)\ast (x_i-x_{i-1})}{f(x_i)-f(x_{i-1})}$

3.2 弦截法与试位法区别

弦截法和试位法有一些相似之处，都是使用两个初始估计值来计算函数斜率的近似值，并将其投射到 x 轴，取得根的一个新估计值。然而，这两个方法的关键不同是新估计值如何取代两个初始值中的一个。在试位法中，根的最新估计值取代的是两个原估计值中函数值符号和$f(x)$相同的一个。因此，这两个估计值总是将根界定在内。所以，对于所有现实情况，这个方法总是收敛的，因为根一直在划界范围内．相反，弦截法按照严格的顺序取代值，用新的$x_{i+1}$的值取代$x_i$，用$x_i$取代$x_{i-1}$因此，这两个值有时处于根的同一边。对于某些情形，这可能导致发散。
因此，用试位法优点在于一定收敛，优势有时也是劣势，试位法必须要已知两个符号相反的初始点；而弦截法不需要两个点的值必须符号相反，但劣势就是可能不收敛。

3.3 改进的弦截法

4 二次插值法

在上面的弦截法中，其实可以看做是用两个点做了一次线性插值，然后用插值出来的直线与x求交得到估计的x的值。因此，弦截法也可以称为线性插值法。
既然有线性插值法，那么就应该有非线性插值法。下面介绍二次插值法。

4.1 二次插值法

假设我们已经有了3个点，那么我们可以通过这3个点确定一个二次函数。
与线性插值法（弦截法）相同，这条抛物线与x轴的交点就表示新的估计值。

但是，由于二次函数不一定与x有交点，这就会导致算法失败。这是二次插值法的劣势。
因此如果与x轴没有交点的话，那就考虑取抛物线的最值点的x值作为替代。

优势：二次插值法有个很大的优势，就是收敛快。是仅次于牛顿迭代法之外的最快的方法之一。并且，对于二重根，收敛也很快。比牛顿迭代快。对于（三重根）多重根，没有测试过。
逆势：有时候会失败。譬如说当三个点的y值相等时，无法拟合成二次曲线。并且，当有抛物线与x轴有两个交点时，取哪一个比较麻烦。还待考虑。

4.2 逆二次插值法

二次插值法有一个问题就是，二次函数不一定与x有交点，并且可能存在三个y值相等。于是就想，要不插值成x关于y的二次函数。

这样，就不会出现与x轴没有交点的问题了。也不会出现三个x值相同的问题。

但是实际使用中发现，逆二次插值法面对二重根的时候，效果不太好。不如二次插值法好。

2022.6.26于上海