二分法

Bisection Method

初級

公開日: 2026-03-20

1. 原理

二分法は中間値の定理に基づく根の探索法である。

中間値の定理

$f$ が $[a,b]$ 上で連続かつ $f(a)\cdot f(b) < 0$ ならば、$f(c) = 0$ を満たす $c \in (a,b)$ が少なくとも1つ存在する。

この定理を反復的に適用し、区間を半分に分割しながら根を挟み撃ちにする。

2. アルゴリズム

二分法

  1. $f$ が連続で $f(a)\cdot f(b) < 0$ を満たす初期区間 $[a,b]$ を選ぶ。
  2. 中点 $c = (a+b)/2$ を計算する。
  3. $f(c) = 0$ ならば $c$ が根であり終了。
  4. $f(a)\cdot f(c) < 0$ ならば $b \leftarrow c$、そうでなければ $a \leftarrow c$ とする。
  5. 停止条件を満たすまで 2--4 を繰り返す。
二分法の反復過程。f(x) = sin(x) の根 π を区間 [2.5, 3.5] で求める例 $x$ $y$ $f(x) = \sin x$ $x^* = \pi$ $f(a_0) > 0$ $f(b_0) < 0$ $a_0$ $b_0$ $c_0$ $a_1$ $b_1$ $c_1$ $a_2$ $b_2$ $c_2$ $a_3$ $b_3$ $c_3$ $a_4$ $b_4$ $c_4$ $a_5$ $b_5$ ↑ 根に収束
図1. 二分法の反復過程（$f(x) = \sin x$, 根 $x^* = \pi$）。$f(a_0) > 0$, $f(b_0) < 0$ から出発し、中点 $c_n$ での符号判定により、左右交互に区間を半分に縮小していく。

3. 収束性

$n$ 回の反復後、根を含む区間の幅は

$$|b_n - a_n| = \frac{b_0 - a_0}{2^n}$$

であり、中点 $c_n$ の誤差は

$$|c_n - x^*| \leq \frac{b_0 - a_0}{2^{n+1}}$$

で上から抑えられる。これは線形収束であり、1回の反復で約1ビットの精度が得られる。$k$ 桁の精度を得るには約 $k \times \log_2 10 \approx 3.32k$ 回の反復が必要である。

二分法・ニュートン法・割線法の収束速度の比較グラフ
図2. 各手法の収束速度の比較（$f(x) = e^x - 3$, 根 $x^* = \ln 3$, 初期区間 $[0, 3]$ での実測値）。ニュートン法は2次収束（7反復で機械精度に到達）、割線法は超線形収束（9反復）を示す。二分法は振動しながらも線形収束し、25反復かかる。

4. 停止条件

以下のいずれかを満たしたとき反復を停止する。ここで $\varepsilon$, $\delta$ はユーザーが指定する許容誤差（例: $10^{-8}$）、$N_{\max}$ は最大反復回数（無限ループ防止用）である。

  • 区間幅: $|b_n - a_n| < \varepsilon$（根の位置が精度 $\varepsilon$ 以内に確定）
  • 関数値: $|f(c_n)| < \delta$（$c_n$ が根に十分近い）
  • 反復回数: $n \geq N_{\max}$（計算時間の上限）

区間幅による停止条件が最も信頼性が高い。必要な反復回数は $n \geq \lceil\log_2((b_0-a_0)/\varepsilon)\rceil - 1$ で事前に計算できる。

5. 利点と欠点

利点欠点
連続関数なら収束が確実に保証される収束速度が遅い（線形）
導関数 $f'(x)$ が不要初期区間両端で関数値が異符号であることが必要
実装が極めて簡単重根を見つけにくい（符号が変化しないため）
反復回数が事前に予測可能多次元への拡張が困難

導関数が不要であることは実用上大きな利点である。ニュートン法は2次収束と高速だが、各反復で $f'(x)$ を計算する必要がある。$f'(x)$ の解析的な式が得られない場合や、$f$ 自体が数値シミュレーションの出力である場合には、ニュートン法は適用しにくい。割線法は導関数不要だが、初期値の選び方次第で発散する可能性がある。二分法は「遅いが確実」であり、他の手法の初期値を求めるための前処理としても有用である。

多次元への拡張が困難な理由は、二分法の本質が「符号の異なる2点で根を挟み撃ちにする」ことにあるためである。二分法が使えるかどうかは、定義域の次元ではなく値域の次元で決まる。

  • 値域がスカラー（$f: \mathbb{R}^n \to \mathbb{R}$）— 二分法は適用可能。$n$ 次元空間内の2点 $\mathbf{a}, \mathbf{b}$ を結ぶ直線上で $g(t) = f(\mathbf{a} + t(\mathbf{b} - \mathbf{a}))$ とパラメータ化すれば、$g: [0,1] \to \mathbb{R}$ に対する通常の二分法がそのまま使える。
  • 値域がベクトル（$\mathbf{f}: \mathbb{R}^n \to \mathbb{R}^n$）— 二分法は適用できない。出力がベクトルであるため「正負」の概念がなく、どちら側に根があるか判定できない。

6. 計算例

$f(x) = x^2 - 2$ の根 $x^* = \sqrt{2} \approx 1.4142$ を区間 $[1, 2]$ で求める。$f(1)=-1 < 0$, $f(2)=2 > 0$。

$n$$a_n$$b_n$$c_n$$f(c_n)$選択
01.00002.00001.5000$+0.2500$左半分
11.00001.50001.2500$-0.4375$右半分
21.25001.50001.3750$-0.1094$右半分
31.37501.50001.4375$+0.0664$左半分
41.37501.43751.4063$-0.0225$右半分
51.40631.43751.4219$+0.0217$左半分

$f(c_n)$ の符号が $+, -, -, +, -, +$ と交互に入れ替わりながら、区間幅は $1.0 \to 0.5 \to 0.25 \to \cdots$ と半分ずつ縮小し、根 $x^* = \sqrt{2}$ に収束する。

計算例の各反復での中点 c_n を曲線上にプロットし、区間の縮小を示した図 $x$ $y$ $f(x) = x^2 - 2$ $x^* = \sqrt{2}$ $a_0$ $b_0$ $c_0$ $a_1$ $b_1$ $c_1$ $a_2$ $b_2$ $c_2$ $a_3$ $b_3$ $c_3$ $a_4$ $b_4$ $c_4$ $a_5$ $b_5$ ↑ 根に収束
図3. 計算例の各中点 $c_n$ の位置（$f(x) = x^2 - 2$）。各 $a_n$, $b_n$ から曲線への破線で $f$ の正負がわかる。左右交互に区間が選択され、根 $x^* = \sqrt{2}$ に収束していく。

7. よくある質問

Q1. 二分法とは何ですか？

連続関数 $f$ に対して $f(a)f(b)<0$ を満たす区間を半分に分割し、根を含む側の区間を繰り返し選択するアルゴリズムである。中間値の定理により収束が保証される。

Q2. 二分法の収束速度は？

線形収束（1次収束）であり、1回の反復で区間幅が半分になる。$k$ 桁の精度を得るには約 $3.32k$ 回の反復が必要である。

Q3. 二分法の欠点は何ですか？

収束速度が遅いこと、初期区間で $f$ の符号変化が必要なこと、多次元への拡張が困難なことが主な欠点である。

8. 参考資料

  • Wikipedia「二分法」（日本語版）
  • Wikipedia「Bisection method」（英語版）
  • R. L. Burden & J. D. Faires, Numerical Analysis, 10th ed., Cengage, 2016.
  • W. H. Press et al., Numerical Recipes, 3rd ed., Cambridge, 2007.