根的分布区间 | 二分搜索法
这只讨论单个非线性方程f(x)=0f(x)=0的求根问题。
方程的根可能是实数根也可能是复（数）根，可能是单根也可能是多重根。关于单根和重根，有如下定义：
定义1：对于方程f(x)=0f(x)=0。如果f(x∗)=0f(x^*)=0，但它的一阶导数f′(x)≠0f'(x)neq 0，则称x∗x^*为方程f(x)=0f(x)=0单根。推而广之，如果f(x∗)=f′(x∗)=f′′(x∗)=⋯=f(k)(x∗)=0f(x^*)=f'(x^*)=f''(x^*)=cdots=f^{(k)}(x^*)=0，而f(k+1)(x∗)≠0f^{(k+1)}(x^*)neq 0，则称x∗x^*为方程f(x)=0f(x)=0的k+1k+1重根。
假设f(x)f(x)有一单根x∗x^*，则f(x)f(x)可写成f(x)=(x−x∗)g(x)f(x)=(x-x^*)g(x)，且有g(x∗)≠0g(x^*)neq 0。对f(x)f(x)求导，得f′(x)=g(x)+(x−x∗)g′(x)f'(x)=g(x)+(x-x^*)g'(x)，故f′(x∗)=g(x∗)≠0f'(x^*)=g(x^*)neq 0。类似地，可以推导出k重根的条件。
对于多项式，其根的个数与方程的次数相同；对于超越方程，其根可能是一个、几个或无穷多个，也可能不存在。因此在解方程时，有必要弄清楚方程根的性质。
1. 根的分布区间
定义2：若函数f(x)f(x)在区间[a,b][a,b]上连续，且f(a)⋅f(b)<0f(a)·f(b)<0，方程f(x)=0f(x)=0在[a,b][a,b]内至少有一个根x∗x^*，则称[a,b][a,b]为方程f(x)=0f(x)=0的根x∗x^*的分布区间；如果在[a,b][a,b]内只有一个根x∗x^*，则称[a,b][a,b]为方程f(x)=0f(x)=0的根x∗x^*的单根分布区间；如果在[a,b][a,b]内只有一个根x∗x^*，并且始终有f′(x)≥0f'(x)geq 0或f′(x)≤0f'(x)leq 0，则称[a,b][a,b]为方程f(x)=0f(x)=0的根x∗x^*的单调分布区间。
2. 二分搜索法
将根的分布区间划分成两个部分，而方程的根必定会落在其中的一个部分或者就在划分点上，再对其中包含方程根的一个部分重复上述划分过程，从而不断缩小根的分布区间，直到根的分布区间的长度达到指定的精度要求为止。此时，根的分布区间内的任何一点，都是方程根的近似值。如果将根的分布区间划分成两个相等的部分，即将区间折半，这种二分法为对分法。
一般情况下，使用二分搜索法求方程的根，为了不漏掉方程的某些根，应该满足下面定理条件。
定理1：对实函数方程f(x)=0f(x)=0，当x∈[a,c]xin[a,c]时，f(x)f(x)在[a,c][a,c]上单调连续，且在两端点处为异号，f(a)⋅f(c)<0f(a)·f(c)<0，则方程在分布区间[a,c][a,c]上只有一个根。
- 用对分法求方程的单根
设方程f(x)=0f(x)=0在区间[a0,c0][a_0,c_0]上满足定理1的条件，且根的精确值为x∗x^*，计算误差为ϵepsilon。用对分法求方程根的过程如下：
1）第一次对分
（1）确定区间中点：将根的初始分布区间[a0,c0][a_0,c_0]折半，得中点b0=a0+c02b_0=frac{a_0+c_0}{2}。
（2）确定含根区间：若f(a0)⋅f(b0)=0f(a_0)·f(b_0)=0，则根x∗=b0x^*=b_0，停止计算；若f(a0)⋅f(b0)<0f(a_0)·f(b_0)<0，则根x∗x^*在b0b_0的左侧，取a1=a0,c1=b0a_1=a_0,c_1=b_0，得到缩小的根的分布区间[a1,c1][a_1,c_1]；若f(a0)⋅f(b0)>0f(a_0)·f(b_0)>0，则根x∗x^*在b0b_0的右侧，取a1=b0,c1=c0a_1=b_0,c_1=c_0，得到缩小的根的分布区间[a1,c1][a_1,c_1]。
（3）确定区间大小：[c1−a1]=[c0−a0]/2[c_1-a_1]=[c_0-a_0]/2。
（4）判断根的误差：取根的近似值为x0=b0=(a0+c0)/2x_0=b_0=(a_0+c_0)/2，与精确值x∗x^*的误差为：
∣e0∣=∣x0−x∗∣≤∣c1−a1∣=∣c0−a0∣/2
|e_0|=|x_0-x^*|leq |c_1-a_1|=|c_0-a_0|/2
若∣e0∣<ϵ|e_0|<epsilon，则停止计算，否则继续对分过程。
2）第二次对分
（1）确定区间中点：将根的初始分布区间[a1,c1][a_1,c_1]折半，得中点b1=a1+c12b_1=frac{a_1+c_1}{2}。
（2）确定含根区间：若f(a1)⋅f(b1)=0f(a_1)·f(b_1)=0，则根x∗=b1x^*=b_1，停止计算；若f(a1)⋅f(b1)<0f(a_1)·f(b_1)<0，则根x∗x^*在b1b_1的左侧，取a2=a1,c2=b1a_2=a_1,c_2=b_1，得到缩小的根的分布区间[a2,c2][a_2,c_2]；若f(a1)⋅f(b1)>0f(a_1)·f(b_1)>0，则根x∗x^*在b1b_1的右侧，取a2=b1,c2=c1a_2=b_1,c_2=c_1，得到缩小的根的分布区间[a2,c2][a_2,c_2]。
（3）确定区间大小：[c2−a2]=[c0−a0]/22[c_2-a_2]=[c_0-a_0]/2^2。
（4）判断根的误差：取根的近似值为x1=b1=(a1+c1)/2x_1=b_1=(a_1+c_1)/2，与精确值x∗x^*的误差为：
∣e1∣=∣x1−x∗∣≤∣c2−a2∣=∣c0−a0∣/22
|e_1|=|x_1-x^*|leq |c_2-a_2|=|c_0-a_0|/2^2
若∣e1∣<ϵ|e_1|<epsilon，则停止计算，否则继续对分过程。
3）继续对分计算
∣en−1∣=∣xn−1−x∗∣≤[cn−an]=[c0−a0]2n(1)
|e_{n-1}|=|x_{n-1}-x^*|leq [c_n-a_n]=frac{[c_0-a_0]}{2^n} tag{1}
直到∣en−1∣<ϵ|e_{n-1}|<epsilon，则停止计算，否则继续对分过程，直到计算误差满足要求为止。
根据（1）式，可以确定满足精度要求的最小对分次数为：
n≥lg(c0−a0)−lgϵlg2
ngeq frac{lg(c_0-a_0)-lgepsilon}{lg2}
- 用二分法搜索方程的单实根
二分搜索法除了可用于求指定区间内(a,c)(a,c)的根以外，还可用于将一个近似根逐步精确化；也可用于求方程f(x)=0f(x)=0在定义区间(a,c)(a,c)内的所有单重实根。其方法如下：
自区间(a,c)(a,c)的一个左端点a开始，并令a0=aa_0=a，且以某一个基本步长h，向右取一个宽度为h的小区间(a0,c0=a0+h)(a_0,c_0=a_0+h)，其中：
（1）若f(a0)⋅f(c0)<0f(a_0)·f(c_0)<0，说明该小区间内存在一个实根，则用对分法找出这个实根，并且以该根为新端点继续往右搜索，依次再找出其他实根。
（2）若f(a0)⋅f(c0)>0f(a_0)·f(c_0)>0，说明该小区间(a0,c0=a0+h)(a_0,c_0=a_0+h)中不存在实根，则继续向右再取一个步长为h的小区间(a0,c0=a0+2h)(a_0,c_0=a_0+2h)，再次搜索。
这样，一个步长，一个步长地向右搜索，直至超过区间右端点cc为止，即可找到方程定义区间(a,c)(a,c)内所有单重实根。
显然，恰当地选择步长h是十分重要的。应使在所选择的一个步长内只有一个根，太大则会丢掉所要找的根，太小则会增加计算量。
二分搜索法除用于求方程的跟之外，实际应用中，常用于查表，即在一组按大小顺序排列的数据中，寻找所需要的那个数。它比用顺序查表发的查表效率大大提高。