【原】二分法

很多方程难以求出精确解，为此数学上发展出了各种数值解法，以求出方程的近似解，例如前面提到的牛顿迭代法。牛顿迭代法的原理是不动点理论，该方法还涉及函数求导。事实上数学中还有更加初等的方法，例如比较简单且常用的二分法，其基本原理是零点定理。

零点定理

设函数f(x)在闭区间[a，b]上连续，且f(a)与 f(b)异号（即f(a)·f(b)<0），那么在开区间（a，b）内至少有函数f(x)的一个零点，即至少有一点ξ（a<ξ<b）使f(ξ)=0.

二分法求解方程的过程如下图所示。先将方程写成F(x)=0的形式，那么函数F(x)的零点就是方程的解。若F(x)在某一区间[a₁, b₁]上连续且F(a₁)与F(b₁)异号(不妨设F(a₁)>0，F(b₁)<0)，则F(x)在区间(a₁, b₁)存在零点。若能进一步判断F(x)在区间(a₁, b₁)存在唯一零点(可以根据F(x)的单调性判断)，就求出区间(a₁, b₁)中点处的函数值；不妨设其值小于零，记中点为b_2，那么可以再次根据零点定理判断唯一零点在区间(a₁, b₂)上，继续求区间(a₁, b₂)中点处的函数值…如此重复执行将零点所在区间范围逐步减半的操作，区间在二分次数趋于无穷时的极限情形只包含函数零点这一个值，也就是方程的解。

二分法求方程F(x)=0在(a, b)区间的解(图片来自Wikipedia)

​

实际操作中，当区间足够小时就可以以区间上任意点作为方程的近似解。很多方程存在多个解，用二分法求解时，可以先将方程所有解所在的大区间划分成足够小的多个区间，使每个区间最多只有一个解。

​二分法不仅可以用于方程求解，还可以用于快速搜索单调数列中特定元素(或最接近某个指定值的元素)的排序位置。方法与求解方程的过程相似，如下图所示。

二分法搜索数列中特定元素的位置(图片来自Wikipedia)