二分法的收敛性与误差界

第一步(不变量)。设 $a_0=a$、$b_0=b$。在第 $n$ 步,我们维持不变量 $f(a_n)f(b_n)<0$,即根被困在 $[a_n,b_n]$ 内某处。由假设,该不变量最初成立。给定 $[a_n,b_n]$,计算中点 $x_n=\dfrac{a_n+b_n}{2}$ 并求出 $f(x_n)$:若其符号与 $f(a_n)$ 相反,则令 $a_{n+1}=a_n,\ b_{n+1}=x_n$,否则令 $a_{n+1}=x_n,\ b_{n+1}=b_n$(若恰好 $f(x_n)=0$,则 $x_n$ 就是根,过程终止)。无论哪种情况都再次有 $f(a_{n+1})f(b_{n+1})<0$,因此该不变量由归纳法得以保持。

第二步(宽度收缩)。按构造,每个新区间恰好是前一个区间的一半,故对一切 $n \ge 0$ 都有 $b_n-a_n = \dfrac{b-a}{2^n}$。由于根 $r$ 在每一步都位于 $[a_n,b_n]$ 内(由第一步),而中点 $x_n$ 也位于 $[a_n,b_n]$ 内,二者都在宽度为 $\dfrac{b-a}{2^n}$ 的同一区间内,故已有 $|x_n - r| \le \dfrac{b-a}{2^n}$ 成立;稍微精细一点地计数(从中点量到某个端点)即得所述的界 $|x_n - r| \le \dfrac{b-a}{2^{n+1}}$。

第三步(收敛)。由于当 $n\to\infty$ 时 $\dfrac{b-a}{2^{n+1}} \to 0$,第二步中的夹逼即迫使 $x_n \to r$。这一部分甚至不需要 $f$ 除初始变号条件之外的连续性——连续性只用于保证一开始 $[a,b]$ 内部确实存在一个根,这正是在第0步应用的介值定理。