計算した温度や電圧が、ある設定では目標より低く、別の設定では高くなる。その間のどこかで目標に合う設定を探したいとき、まず両端の真ん中を試す方法があります。結果に応じて調べる範囲を半分にし、さらにその真ん中へ進むのが二分法です。
簡単にまとめると？
- 区間内で連続な関数の値が両端で正と負に分かれれば、その間に少なくとも一つ解があります。
- 解を含む側を半分ずつ残すので、区間幅から解の位置の誤差を見積もれます。
- 途中に不連続な点がある場合や、関数の符号を正しく判定できない場合には、この保証を使えません。
目標との差を、正と負で読む
探したい設定を x、計算結果と目標との差を f(x) と書くと、目標に合う場所は f(x) = 0 です。この x を方程式の「根」と呼びます。区間の左端 a で f(a) が負、右端 b で f(b) が正なら、連続な曲線は途中でゼロを通ります。これが中間値の定理による保証です。左右の正負が逆でも成り立ちます。[1]
ここでいう連続とは、x を少し動かしたときに f(x) が飛び跳ねないことです。単に両端で違う値が出た、という条件より強い意味があります。また、保証されるのは「少なくとも一つ」です。根が一つしかないことまで、両端の符号だけで決まるわけではありません。
中点 m = (a + b) / 2 で f(m) を計算し、ゼロならそこで終わりです。ゼロでなければ、両端の符号が異なる半区間を残します。たとえば f(a) < 0、f(m) < 0、f(b) > 0 なら、次に調べるのは [m, b] です。関数の傾きを計算せず、値の符号だけで範囲を絞れます。[2]
√3を探すと、残す区間が見えてくる
無次元の計算例として、f(x) = x² − 3 を区間 [1, 2] で考えます。左端では −2、右端では 1 なので、正の根 √3 がこの中にあります。最初の中点 1.5 では −0.75。まだ二乗した値が3に届かないため、左半分を除いて [1.5, 2] を残します。
次の中点 1.75 では 0.0625 となり、今度は大きすぎます。そこで [1.5, 1.75] へ絞ります。図は、この操作を4回繰り返した範囲です。毎回どちらかの端が根へ近づき、青い区間は根を含んだまま短くなります。
初めの区間幅を L とすれば、n 回の絞り込み後の幅は L / 2ⁿ です。残った区間の中点を答えにすると、そこから区間内のどの位置までも、距離は幅の半分以下。したがって、少なくとも一つの根との距離は L / 2ⁿ⁺¹ 以下です。これは丸めのない計算で、根を含む区間を正しく保った場合の評価です。
今回の L = 1 なら、19回の絞り込みで中点の誤差上限は約 9.54 × 10⁻⁷ になります。目標が絶対誤差 10⁻⁶ 以下なら、必要な回数をあらかじめ見積もれるわけです。区間幅を半分にするたびに誤差上限も半分になりますが、表示した小数の各桁が毎回一つずつ確定する意味ではありません。
符号が違っても、解がない場合
f(x) = 1/x を [−1, 1] で調べると、両端の値は −1 と 1 です。しかし、この関数がゼロになる場所はありません。途中の x = 0 で値を定義できず、区間全体では連続でないからです。中点へ進む操作だけをまねると、根ではなく特異点へ近づいてしまいます。式に分母があるときは、区間内で分母がゼロにならないかを先に調べる必要があります。
逆に、両端が同じ符号だからといって根がないとは限りません。f(x) = (x − 1)² は [0, 2] の両端で1ですが、中点の x = 1 ではゼロになります。曲線がゼロに触れて折り返すため、符号が変わりません。このような偶数重根は、符号変化を出発条件とする方法では一般に取りこぼします。たまたま試した点が根と一致する場合とは分けて考えます。[2]
計算を止める前に、何の誤差を小さくしたか
二分法の扱いやすさは、答えの一点だけでなく、根のある区間を残せることにあります。一方、計算機には桁数の限界があり、関数評価にも誤差が入ります。中点が丸めによって端点と同じ値になれば、同じ操作を続けても区間は縮まりません。終了条件には区間幅と反復回数を設け、関数値が有限か、符号の判定に無理がないかも見る必要があります。
また、f(x) が小さいことと x が根に近いことは別の量です。たとえば g(x) = 10⁻¹²(x − 1) では、x = 0 で関数値の絶対値は 10⁻¹² でも、根までの距離は1あります。関数値だけを小さくする判定では、式の倍率によって印象が変わってしまいます。求める設定値の許容差に合わせて区間幅を決めると、計算結果を使う側の条件と結びつきます。
二分法は一度に半分ずつ進むため速さには限界がありますが、連続性と初期区間を確かめられる問題では、解の位置を追いやすい方法です。より速い手法へ進む場合にも、最初に根を挟む範囲を見つけておくことが、結果を確かめる足場になります。[2]
出典
- AMSI・VCAA — The bisection method（2015年の教材。中間値の定理、連続性、区間幅と誤差の説明）。
- GNU Scientific Library 2.8 — One Dimensional Root-Finding（Root Finding Caveats、Root Bracketing Algorithms、Search Stopping Parameters）。