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

最終更新 2018年 4月29日
二分法とは?
  二分法とは、 関数 $f(x)$ が
を満たすときに、 反復計算によって方程式 $f(x)=0$ の近似解を求めるアルゴリズムの一つである。 計算を繰り返すたびに解の存在する範囲を半分に縮まるので、確実に収束性が担保される。 正確には、以下のような反復計算を繰り返す。

  二分法の定義を述べるにあたって、 関数 $f(x)$ が $a < b$ である $a$ と $b$ に対して、
を満たすと連続関数であると仮定する。 これに対し 数列 $\{ a_{n} \}$ と $\{ b_{n} \}$ を次のように定義しながら、 反復計算を実行する。
ステップ 1
  数列の初項を
とする。 仮定より、
であるので、このステップで解 ($f(x)=0$ を満たす $x$) が求まることはない。
ステップ 2
  ステップ $1$ で得られた $a_{1}$ と $b_{1}$ の中点において、
である場合には、 数列の第2項を
とする。 反対に、
である場合には、
とする。
  どちらの場合であっても、 $a_{2} < b_{2}$ であり、
が成り立つ。 また、 ステップ 2 での数列の差 $b_{2}-a_{2}$ は、 ステップ 1 での差 $b_{1}-a_{1}$ の半分になる。
  一方で運良く
となった場合には、解が
であることが分かったので、計算を終了する。
ステップ $n$
  ステップ $2$ 以降は同様の方針に従って数列を更新して行く。 すなわち、 ステップ $n-1$ で得られた $a_{n-1}$ と $b_{n-1}$ の中点において、
である場合には、
とする。 反対に、
の場合には、
とする。
  どちらの場合であっても、$a_{n} < b_{n}$ であり、
が成り立つ。 また、 ステップ $n$ での数列の差 $b_{n}-a_{n}$ は、 ステップ $n-1$ での差 $b_{n-1}-a_{n-1}$ の半分になる。
  一方で運良く
となった場合には、解が
であることが分かったので、計算を終了する。
  以上の反復計算によって、数列 $\{ a_{n} \}$ と $\{ b_{n} \}$ を更新して行き、 十分な精度が得られた時点で計算を終了する。 計算を終了した時点の数列 $a_{n}$ と $b_{n}$ の間に解があると判断する。 このような数値解法を 二分法 (Bisection method) という。
  計算終了のルールとしては、 次のようなものがある。 すなわち、 一回の反復によって数列の差が半分になって行くことから、 計算を進めてゆくと、 その差が次第に小さくなって行く。 そこで、その差が十分に小さくなったとき、 例えば、正の小さな値 $\epsilon$ に対して、
が満たされたときに計算を終了する。 このとき、 解は $b_{n}$ と $a_{n}$ の間にあり、 計算誤差が $\epsilon$ であると判断する。

二分法を用いた例題
  二分法を用いて
の解を数値的に小数点 2 桁まで求める。

説明
  関数 $f(x)$ を
と定義し、 区間 $[1, 2]$ に対して二分法を適用する。

  数列 $\{ a_{n} \}$ と $\{ b_{n} \}$ の初項を
とする。
  これらの中点において、
であるので、 数列の第2項は
とする。
  これらの中点において、
であるので、 数列の第3項を
とする。
  これらの中点において、
であるので、 数列の第4項を
とする。
  これらの中点において、
であるので、 数列の第5項を
とする。
  これらの中点において、
であるので、 数列の第6項を
とする。
  これらの中点において、
であるので、 数列の第7項を
とする。
  これらの中点において、
であるので、 数列の第8項を \begin{eqnarray} a_{8} &=& 1.7265625 \\ b_{8} &=& 1.734375 \end{eqnarray}
とする。
  この時点で数列の差が
になり、小数点2桁 $(0.01)$ よりも小さくなったので、計算を終了する。 この結果、 真の解が
の範囲にあると判断される。 実際の値が
であるので、およそ 小数点2桁 程度の誤差で近似値が得られている。
  この精度で満足出来ないのであれば、さらに反復計算を進めてゆく。 $f(x)$ は区間 $[1,2]$ において単調増加関数であるので、 反復を繰り返せば繰り返すほど、真の解に近い結果を得られる (単調増加なら収束を参考)。

単調増加関数なら収束
  区間 $[a, b]$ で連続かつ単調増加する関数 $f(x)$ が
を満たすとき、 二分法は
を満たす唯一つの $x$ に収束する。

証明
  区間 $[a, b]$ で連続かつ単調増加する関数 $f(x)$ が
を満たすとし、 二分法を適用する。
  二分法では、 計算の第 1 ステップにおいて、 数列の $\{a_{n} \}$ と $\{ b_{n} \}$ の初項を
と定義する (二分法の定義を参考)。 このとき、$a_{1} < b_{1}$ かつ
であるので、 中間値の定理により、
を満たす $x$ が区間 $[a_{1}, b_{1}]$ の間に唯一つ存在する。 ここで「唯一つ」の部分には $f$ の単調増加性を用いた。 このとき、区間の幅 $d_{1}$ は、
である。

  計算の第 2 ステップにおいては、 $a_{1}$ と $b_{1}$ の中点で
である場合には、 数列の第2項を
とし、反対に
である場合には、
とする。
  どちらの場合であっても、、$a_{2} < b_{2}$ であり、
が成り立つので、 中間値の定理により、
を満たす $x$ が区間 $[a_{2}, b_{2}]$ の間に唯一つ存在する。 ここで「唯一つ」の部分で $f$ の単調増加性を用いた。 このとき、 区間の幅 $d_{2}$ は、
となり、 $d_{1}$ の半分になる。

  ステップ $2$ 以降は同様の方針に従って数列を更新して行く。 すなわち、 ステップ $n-1$ で得られた $a_{n-1}$ と $b_{n-1}$ の中点において、
である場合には、
とし、 反対に
の場合には、
とする。
  どちらの場合であっても、$a_{n} < 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 < n$ である全ての $n$ に対して、
が成り立つので、
が成り立つ。 この関係は、極限
の定義そのものであり、 数列 $b_{n}$ が解 $x$ に収束することを表している。 同様に、
も成り立つ。
  このように、 連続かつ単調増加する関数に対して二分法を適用すると、 反復計算で現れる数列が真の解に収束することが保証される。

単調減少関数に対しても同様である。
二分法の収束速度
  区間 $[a, b]$ に対して二分法を適用したとき、 近似解の範囲が $\epsilon$ より小さくなるためには、
よりも多くの回数の反復計算が必要である。

証明
  定義 から分かるように、 二分法では一回の計算ステップで、近似解の範囲が前のステップの範囲の半分になる。 従って、 $N$ 回反復した後の近似解の範囲は、
である。 これが正の小さな値 $\epsilon$ より小さくなるためには、
が成り立たなくてはならない。 これより、
であるので、 $\epsilon$ より小さい範囲に近似解を絞り込むためには、 最低でも
より多くのステップの反復計算を実行する必要がある。


  区間が $[0,1]$ の二分法で、 近似解の範囲を $10^{-4}$ まで絞り込むためには、
よりの多くの回数 (つまり 14 回) の反復計算を要する。
順序データの探索への応用
  コンピュータ上で小さい順に並べられたデータ
の中から値 $C$ よりも大きな最小のものを求める問題において、 二分法は効果的である。

簡単な解説
  コンピュータ上において、 小さい順に並べられたデータ
の中から値 $C$ よりも大きな最小のものを求めるためには、 単純にはデータの最初から順番に探索して行き、
を満たす $n$ を見つけ、 それを出力するというアルゴリズムが考えられる。 この場合、出力に要する計算ステップ数はデータのサイズ $N$ に比例する。
  一方で同じデータに対して、各データ点を結んだ連続関数
を定義して、 区間 $[1, N]$ に対して 二分法を適用すると、 $\log_{2} N$ に比例する回数で解を絞り込むことできる (二分法の収束速度 を参考) 。
$N$ が大きい場合、$N$ と $\log_{2} N$ では大きな差になるので、 二分法は コンピュータ上での順序データの探索を高速化させる。

特徴
  1. 速くはないが確実に収束
  上の $\sqrt{3}$ を求める例から分かるように、 二分法では、小数点 2 桁の精度を得るために、 $8$ 回程度の計算を要する。 一方で、ニュートン法を用いると、 同じ精度を得るために $1$ 回の計算で済む。 (ニュートン法で $\sqrt{3}$ を求める を参考) 。 これだけを見ると、二分法よりもニュートン法の方が優れているように思えるが、 必ずしもそうではない。
  二分法の長所は、一回の反復で必ず解の範囲が半分になり、 反復計算を進めて行けば行くほど、解の範囲は必ず小さくなることにある。 このことは、 ニュートン法では保証されない。
  したがって、必ず解を収束させたい場面においては、 ニュートン法のような勾配法に頼らず、 二分法を適用した方が効果的なこともある。
 
  2. コンピュータ上での探索では高速
  順序データの探索を参考
 
  3. 単調関数なら真の解に収束
  単調増加関数なら収束を参考
中間値の定理
  区間 $[a,b]$ で連続な関数が
を満たすとき、
を満たす任意の $C$ に対して、
を満たす $c$ が 区間 $[a,b]$ の中に存在する。 これを中間値の定理という。
  二分法に応用する際には、
とし、次のように言い直す。 すなわち、 区間 $[a,b]$ で連続な関数が
を満たすとき、
を満たす $c$ が 区間 $[a,b]$ の中に存在する。