二分法とは？   アルゴリズム・収束・例題

証明
  区間 $[a, b]$ で連続かつ単調増加する関数 $f(x)$ が を満たすとし、 二分法を適用する。
  二分法では、 計算の第 1 ステップにおいて、 数列の $\{a_{n} \}$ と $\{ b_{n} \}$ の初項を と定義する (二分法の定義を参考)。 このとき、$a_{1} \lt b_{1}$ かつ であるので、 中間値の定理により、 を満たす $x$ が区間 $[a_{1}, b_{1}]$ の間に唯一つ存在する。 ここで「唯一つ」の部分には $f$ の単調増加性を用いた。 このとき、区間の幅 $d_{1}$ は、 である。
  計算の第 2 ステップにおいては、 $a_{1}$ と $b_{1}$ の中点で である場合には、 数列の第2項を とし、反対に である場合には、 とする。
  どちらの場合であっても、、$a_{2} \lt b_{2}$ であり、 が成り立つので、 中間値の定理により、 を満たす $x$ が区間 $[a_{2}, b_{2}]$ の間に唯一つ存在する。 ここで「唯一つ」の部分で $f$ の単調増加性を用いた。 このとき、 区間の幅 $d_{2}$ は、 となり、 $d_{1}$ の半分になる。
  ステップ $2$ 以降は同様の方針に従って数列を更新して行く。 すなわち、 ステップ $n-1$ で得られた $a_{n-1}$ と $b_{n-1}$ の中点において、 である場合には、 とし、 反対に の場合には、 とする。
  どちらの場合であっても、$a_{n} \lt b_{n}$ であり、 が成り立つので、 中間値の定理により、 を満たす $x$ が区間 $[a_{n}, b_{n}]$ の間に唯一つ存在する。 ここで「唯一つ」の部分で $f$ の単調増加性を用いた。 ステップ $n$ での区間の幅 $d_{n}$ は、 となり、 第 1 ステップと比較して $\frac{1}{2^{n-1}}$ の分だけ幅が狭くなる。
  このように連続かつ単調増加な関数 $f$ に対して二分法を適用すると、 各ステップで現れる区間の幅 $d_{n}$ が $1/2$ 倍ずつ小さくなり、なおかつ、 その中に解が唯一つ存在するように計算が反復される。 したがって、 必ずどこかのステップで任意の幅 $\epsilon$ よりも小さな区間の中に 解が唯一つ存在する状態に達する。
  このステップを $N$ とすると、 $N \lt n$ である全ての $n$ に対して、 が成り立つので、 が成り立つ。 この関係は、極限 の定義そのものであり、 数列 $b_{n}$ が解 $x$ に収束することを表している。 同様に、 も成り立つ。
  このように、 連続かつ単調増加する関数に対して二分法を適用すると、 反復計算で現れる数列が真の解に収束することが保証される。