二分法の収束と誤差限界

ステップ1(不変量)。$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$ となるので、不変量は帰納法により保たれる。

ステップ2(幅の縮小)。構成により新しい各区間は前の区間のちょうど半分なので、すべての $n \ge 0$ について $b_n-a_n = \dfrac{b-a}{2^n}$ が成り立つ。根 $r$ は各ステップで $[a_n,b_n]$ の中にあり(ステップ1より)、中点 $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}}$ が得られる。

ステップ3(収束)。$n\to\infty$ のとき $\dfrac{b-a}{2^{n+1}} \to 0$ なので、ステップ2による挟み込みにより $x_n \to r$ が強制される。この部分では、最初の符号条件を超える $f$ の連続性すら不要である——それが必要なのは、そもそも $[a,b]$ の内部に根が存在することを保証するため、すなわちステップ0で適用される中間値の定理のためだけである。