二分法の収束

$a \lt b$、$f : [a,b] \to \mathbb{R}$ は連続で $f(a) f(b) \lt 0$ とする。$a_0 = a$、$b_0 = b$ とし、$k = 0, 1, 2, \ldots$ について $c_k = (a_k + b_k)/2$ とおいて、$f(a_k) f(c_k) \lt 0$ なら $(a_{k+1}, b_{k+1}) = (a_k, c_k)$、$f(c_k) f(b_k) \lt 0$ なら $(a_{k+1}, b_{k+1}) = (c_k, b_k)$ と定める（$f(c_k) = 0$ なら $c_k$ を解として止める）。止まらないとき、

1. 各 $[a_k, b_k]$ は $f$ の零点を含み、$b_k - a_k = (b-a)/2^k$ である。
2. $(a_k)$ と $(b_k)$ は共通の極限 $x^*$ に収束し、$f(x^*) = 0$ である。
3. すべての $k$ で $|c_k - x^*| \le (b-a)/2^{k+1}$ が成り立つ。