B 函数图像与变化关系 · 20

用二分法求方程近似解

当方程 $f(x)=0$ 难以求出精确解时,可以先找到一个确定含有零点的区间,再反复把区间长度缩小一半。二分法的关键是每次都保留一个仍能保证零点存在的小区间。顺着区间的更新过程,可以说明近似值怎样得到、误差怎样控制。

开始条件

什么时候可以开始二分

先选定初始闭区间 $[a_0,b_0]$。要在这个区间内开始二分,必须先确认零点存在。

若函数 $f$ 在 $[a_0,b_0]$ 上连续,并且两端的函数值异号,即

$$f(a_0)f(b_0)<0,$$

那么零点存在定理保证开区间 $(a_0,b_0)$ 内至少有一个零点。

二分法将逐步逼近其中一个由异号区间锁定的零点,但不负责找出区间内的所有零点。

更新区间

每一次如何更新区间

有了连续且端点异号的区间,接下来要判断保留哪一半。把当前区间记为 $[a,b]$,先取中点

$$m=\frac{a+b}{2}.$$

若 $f(m)=0$,就已经找到精确零点,可以停止。若 $f(m)\ne0$,它必定与两个异号端点中的一个同号、与另一个异号。因此,按下面的规则保留端点异号的一半:

$$[a,b]\leftarrow\begin{cases}[a,m],&f(a)f(m)<0,\\\left[m,b\right],&f(m)f(b)<0.\end{cases}$$

函数在新区间上仍连续,两端的函数值仍异号,所以其中仍至少有一个零点。每次更新都保留了这个保证,同时把区间长度减半。

经过 $n$ 次更新,区间长度变为

$$b_n-a_n=\frac{b_0-a_0}{2^n}.$$

分母中的 $2^n$ 来自连续 $n$ 次减半。因此,只要继续二分,含零点区间就会按可控的速度缩小。

误差控制

精度怎样由区间长度控制

区间缩小到什么程度,决定了近似值能有多精确。设保留区间 $[a_n,b_n]$ 中的某个零点为 $x^*$,取区间中点作为近似值:

$$\widetilde{x}=\frac{a_n+b_n}{2}.$$

零点位于两个端点之间,中点到任一端点的距离都是区间长度的一半。因此,中点与零点的距离不会超过这个长度:

$$\left|\widetilde{x}-x^*\right|\le\frac{b_n-a_n}{2}.$$

若采用更保守的停止标准 $b_n-a_n<\varepsilon$,则从区间中取任意一个数作为近似值,它与该零点的误差都小于 $\varepsilon$。

最后要用近似符号“$\approx$”表达结果,不能把近似值写成与零点精确相等。

完整例子

完整看一次区间缩小

用方程 $2x^3+3x-3=0$ 看一次完整计算。记 $f(x)=2x^3+3x-3$,它是多项式函数,在 $[0,1]$ 上连续。代入两个端点,得到

$$f(0)=-3<0,\qquad f(1)=2>0.$$

所以初始区间 $[0,1]$ 内有零点。依次取中点,再根据函数值的符号保留异号的一半。表中每一行的“保留区间”就是下一次二分的起点。

从初始区间 [0, 1] 开始的七次二分
次数中点 $m$$f(m)$ 的符号保留区间
10.5−[0.5, 1]
20.75+[0.5, 0.75]
30.625−[0.625, 0.75]
40.6875−[0.6875, 0.75]
50.71875−[0.71875, 0.75]
60.734375−[0.734375, 0.75]
70.7421875+[0.734375, 0.7421875]

最后两个端点处的函数值分别为

$$f(0.734375)\approx-0.004768<0,$$
$$f(0.7421875)\approx0.044219>0.$$

两端仍异号,说明保留区间仍含有零点。此时区间长度为

$$0.7421875-0.734375=0.0078125<0.01.$$

取中点 $0.73828125$,再按小数形式表示,可写出近似解 $x\approx0.74$。由于 $0.74$ 本身也在最终区间内,这个表示仍满足误差小于 $0.01$。

方法边界

二分法能与不能保证的事

回到整个过程,二分法的保证始终来自两个条件:函数连续,区间两端的函数值异号。在这两个条件下,含零点区间会不断缩小,从而得到满足指定误差的近似值。

它不能单独证明零点唯一,也不能找到所有零点。如果函数在零点处只接触 $x$ 轴而不变号,标准二分法也无法依靠端点异号来定位这个零点。

每次保留异号的一半,用区间长度控制误差;中点函数值恰好为零时,就已找到精确零点。