Python调用二分法和牛顿法求方程的根

二分法

二分法是最简单的求根算法。

对于方程$f(x)=0$，如果$f(a)\cdot f(b)<0$，则说明$a,b$之间必有根，如果按照某个步长对其进行搜索，那么最终一定能够不断缩小根的取值范围，不断精确化。

二分法就是基于这种思想的一种算法，其实质是对区间进行快速选取。如果已知$f(a)\cdot f(b)<0$，则快速选取$c=\frac{a+b}{2}$，如果$f(a)\cdot f(c)<0$，则说明根在$(a,c)$之间，否则即说明根在$(a,b)$之间，然后不断迭代下去。

scipy提供了二分求根算法bisect，测试如下

from scipy.optimize import bisect

def func(x):
    return x*x - 2

bisect(func, 0, 2)
# 1.4142135623715149

其中，func为待求函数，0,2为下限和上限。

牛顿法

如果$f(x)$=0可以写成$x=\phi (x)$的形式，则可以将这个方程的根理解为$y=\phi (x)$与$y=x$的交点。现给定一个初值$x_0$，将其代入$\phi (x)$中，则$\phi (x_0)$对应一个新的$x$，记为$x_1$。

如果数列 { x n } \{x_n\} {xn​}收敛，那么必有$x={\lim }_{k\to \infty }{x}_k$即为方程的根。所以，问题的关键在构造合适的$\phi (x)$使得数列能够快速收敛。

其最简单的形式莫过于$x_{k+1}=x_k+f(x_k)$，不过这种迭代公式看起来十分危险，如果$f(x_k)是一个大于0的单调递增函数，那么结果就爆炸了。

所以，最好为$f(x_k)$乘以一个系数，当$f(x_k)$增加时使之变小，当其递减时使之变大。所以一个比较好的形式为

$$x_{k+1}=x_k-\frac{f(x_k)}{f^{\prime }(x_k)}$$

此即Newton公式。

除了迭代形式，Newton公式也可以作为二分法的一个升级版本，$x_k-\frac{f(x_k)}{f^{\prime }(x_k)}$可以表示过$(x_k,f(x_k))$做切线与$x$轴的交点，通过切线选取新的$x$值取代了二分法的盲动性，示例如下

from scipy.optimize import newton

newton(func, 0)
# 1.4142135623715149

函数定义

二分法和牛顿法的参数定义如下

bisect(f, a, b, args=(), xtol=2e-12, rtol=8.881784197001252e-16, maxiter=100, full_output=False, disp=True)
newton(func, x0, fprime=None, args=(), tol=1.48e-08, maxiter=50, fprime2=None, x1=None, rtol=0.0, full_output=False, disp=True)

其中，f, a, b以及func, x0已经在演示的时候调用了，分别是求根函数和初值；args为待求根函数中可能包含的其他参数；maxiter为最大迭代步长。