二分法とは
二分法は、連続関数 \(f(x)\) の根（\(f(x) = 0\) となる \(x\) の値）を求める手法のうち、最も古くから使われ、かつ確実性の高い方法のひとつです。まず関数の符号が変化する区間 \([a, b]\) を用意し、その区間を半分に分けて、根を含む側（符号変化が残っている側）を選び続けます。各ステップで符号の変化が保たれるため、\(f\) が連続で、\(f(a)\) と \(f(b)\) の符号が逆であれば必ず収束することが保証されます。この計算では、無次元の実関数を任意に扱え、三角関数の角度はラジアンで計算します。
使い方
f(x) の欄に、変数 \(x\) を用いて関数を入力します（例：x-cos(x)、x^2-2、exp(x)-3 など）。区間の下端 a と上端 b は、その間に根が来るように設定してください。すなわち \(f(a)\cdot f(b)\) の積が 0 以下になる必要があります。最大反復回数 n と、表示する桁数を指定します。計算結果として、近似的な根、その点での関数値（ほぼ 0 になるはずです）、そして実際に必要だった反復回数が表示されます。
計算式
各ステップでの推定値は区間の中点 \(x_n = (a_n + b_n) / 2\) です。\(|f(x_n)|\) が許容誤差を下回れば \(x_n\) を解として採用します。そうでなければ、符号変化が残っている側の半区間を選びます。\(f(a_n)\cdot f(x_n) > 0\) なら根は右側にあるので \(a = x_n\) とし、そうでなければ左側にあるので \(b = x_n\) とします。$$ c = \frac{a + b}{2} \\[1.5em] \text{where}\quad \left\{ \begin{aligned} &\text{if } f(a)\cdot f(c) < 0 \Rightarrow b \leftarrow c \\ &\text{else} \Rightarrow a \leftarrow c \\ &\text{repeat up to } n \text{ times} \end{aligned} \right. $$ 区間の幅は \((b-a)/2^n\) で縮小していくため、収束は線形であり、おおむね 1 ステップごとに正しい 2 進数の桁が 1 桁ずつ増えていきます。
計算例
\(f(x) = x - \cos(x)\) を区間 \([-10, 10]\) で考えます。\(f(-10) \approx -10.84\)（負）、\(f(10) \approx 10.84\)（正）なので、根がこの区間に挟まれています。区間を繰り返し半分にしていくと \(x \approx 0.7390851332151607\) に収束します。これは \(x = \cos x\) を満たす有名な「ドッティ数（Dottie number）」で、このとき \(f(x)\) は実質的に 0 になります。
二分法を手作業で行う方法
二分法は、根を含むことが知られている区間を繰り返し二等分することにより、\(f(x)=0\) の根を見つけます。これは中間値の定理に依存しています：\(f\) が \([a,b]\) で連続であり、\(f(a)\) と \(f(b)\) が反対の符号を持つ場合、根はその間にあります。
- 括弧を確認します。 \(f(a)\cdot f(b)<0\) であることを確認します。積が正の場合、区間は根を含むことが保証されていません — 異なる \([a,b]\) を選択します。
- 中点を計算します。 \(m=\dfrac{a+b}{2}\)。
- 関数を評価します。 \(f(m)\) を求めます。\(f(m)=0\)（または許容範囲内）の場合、\(m\) は根であり、停止します。
- 符号で終点を置き換えます。 \(f(a)\cdot f(m)<0\) の場合、根は \([a,m]\) にあるため、\(b\leftarrow m\) に設定します。そうでない場合、根は \([m,b]\) にあるため、\(a\leftarrow m\) に設定します。
- 繰り返します \(|b-a|<\text{許容値}\) または \(|f(m)|<\text{許容値}\) まで、またはステップ 2～4 を最大反復回数に達するまで繰り返します。
例： \(f(x)=x^{3}-x-2\) を \([1,2]\) で計算します。確認：\(f(1)=-2\)、\(f(2)=4\)、積 \(<0\) — 括弧は有効です。
| 反復 | a | b | m=(a+b)/2 | f(m) | 新しい区間 |
|---|---|---|---|---|---|
| 1 | 1.0000 | 2.0000 | 1.5000 | −0.125 | [1.5, 2] |
| 2 | 1.5000 | 2.0000 | 1.7500 | 1.6094 | [1.5, 1.75] |
| 3 | 1.5000 | 1.7500 | 1.6250 | 0.6660 | [1.5, 1.625] |
| 4 | 1.5000 | 1.6250 | 1.5625 | 0.2522 | [1.5, 1.5625] |
| 5 | 1.5000 | 1.5625 | 1.5313 | 0.0591 | [1.5, 1.5313] |
| 6 | 1.5000 | 1.5313 | 1.5156 | −0.0340 | [1.5156, 1.5313] |
さらに反復した後、区間は真の根 1.521380 に閉じます。これは3次方程式 \(x^{3}-x-2=0\) の唯一の実根でもあり、1.521380 直接ソルバーで見つかります。
反復と許容値および括弧の幅
各二分ステップは区間を二等分するため、\(n\) 回の反復後、括弧の幅は \((b-a)/2^{\,n}\) になります。根の位置の許容値 \(\text{許容値}\) に達するために、約
$$n \approx \log_2\!\left(\frac{b-a}{\text{許容値}}\right).$$の反復が必要です。回数は精度の対数によってのみ増加するため、非常に厳しい許容値でも比較的少ない手順が必要です。表は、複数の組み合わせのための四捨五入された反復カウントを示しています。
| 初期幅 \(b-a\) | 目標許容値 | \(\log_2((b-a)/\text{許容値})\) | 必要な反復 |
|---|---|---|---|
| 1 | \(10^{-3}\) | 9.97 | 10 |
| 1 | \(10^{-6}\) | 19.93 | 20 |
| 1 | \(10^{-10}\) | 33.22 | 34 |
| 10 | \(10^{-6}\) | 23.25 | 24 |
| 20 | \(10^{-6}\) | 24.25 | 25 |
| 100 | \(10^{-8}\) | 33.22 | 34 |
| 0.5 | \(10^{-12}\) | 38.86 | 39 |
例えば、幅20の括弧を \(10^{-6}\) に絞ったものは \(\lceil\log_2(20/10^{-6})\rceil=\lceil 24.25\rceil=\) 25 回の反復が必要であり、幅1の括弧を \(10^{-10}\) に絞ったものは \(\lceil 33.22\rceil=\) 34 回が必要です。開始幅を半分にするとちょうど1回の反復が節約されます。精度を2乗する（小数点以下1桁追加）には約3.3回の反復がかかります。
主な用語
- 根。 関数がゼロである値 \(x^{*}\)、つまり \(f(x^{*})=0\)。ゼロまたは方程式の解とも呼ばれます。
- 括弧/区間 \([a,b]\)。 根を囲むと考えられるエンドポイントのペア。二分法では、符号変化条件を満たす必要があります。
- 符号変化。 条件 \(f(a)\cdot f(b)<0\)。つまり、\(f\) がエンドポイントで反対の符号を取ることを意味します。連続 \(f\) の場合、これは間に少なくとも1つの根があることを保証します（中間値の定理）。
- 中点。 現在の区間の中心、\(m=(a+b)/2\)。各ステップがこのポイントをテストし、根を含むことができない半分を破棄します。
- 許容値。 反復を停止する精度目標。区間幅 \(|b-a|\) または残差 \(|f(m)|\) に適用されます。
- 収束（線形）。 二分法は線形に収束します：誤差は各ステップで約半分になります（誤差 \(\le (b-a)/2^{n}\)）。定常的ですが加速しない進捗を提供します — 反復ごとにおよそ1つの追加の正しい二進数字。
- 反復。 中点の計算、関数の評価、およびエンドポイントの更新の1つの完全なサイクル。反復カウントは最大反復設定によって制限されます。
よくある質問
「符号変化がない」というエラーが出るのはなぜ？ 二分法では \(f(a)\) と \(f(b)\) の符号が逆である必要があります。\(a\) と \(b\) が根を挟むように値を調整してください。
複数の根を求められますか？ いいえ。指定した区間内の根を 1 つだけ返します。また、曲線が軸に接するだけで交差しないタイプの根は検出できません。
ニュートン法より遅いのはなぜ？ 二分法は線形収束で、1 ステップごとに 2 進数で約 1 桁ずつ精度が上がります。一方ニュートン法は 2 次収束です。二分法は、安全な初期値を得るためにまず使い、その後により高速な手法で精度を高める、といった使い方がよくされます。
