这只讨论单个非线性方程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重根的条件。
对于多项式,其根的个数与方程的次数相同;对于超越方程,其根可能是一个、几个或无穷多个,也可能不存在。因此在解方程时,有必要弄清楚方程根的性质。
定义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^*的单调分布区间。
将根的分布区间划分成两个部分,而方程的根必定会落在其中的一个部分或者就在划分点上,再对其中包含方程根的一个部分重复上述划分过程,从而不断缩小根的分布区间,直到根的分布区间的长度达到指定的精度要求为止。此时,根的分布区间内的任何一点,都是方程根的近似值。如果将根的分布区间划分成两个相等的部分,即将区间折半,这种二分法为对分法。
一般情况下,使用二分搜索法求方程的根,为了不漏掉方程的某些根,应该满足下面定理条件。
定理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是十分重要的。应使在所选择的一个步长内只有一个根,太大则会丢掉所要找的根,太小则会增加计算量。
二分搜索法除用于求方程的跟之外,实际应用中,常用于查表,即在一组按大小顺序排列的数据中,寻找所需要的那个数。它比用顺序查表发的查表效率大大提高。