二分法

区間の両端で符号が変わる連続関数 $f$ に二分法を適用し、指定した回数後の区間や中点 $c = \frac{a + b}{2}$ を求められる。区間の幅が $\frac{b - a}{2 ^{n}}$ になることから、必要な反復回数も求められる

前提

関数の連続性と中間値の定理（数学III 極限）

この技能までの道筋（13 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

四則の混じった計算の順序（算数計算と数のきまり）
等間隔にならんだ数の和（算数計算と数のきまり）
分数のたし算・ひき算（算数計算と数のきまり）
小数の四則計算（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
分数のかけ算・わり算（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
等差・等比数列の和と Σ （数学B 数列）
数列の極限（数学III 極限）
関数の極限（数学III 極限）
関数の連続性と中間値の定理（数学III 極限）

説明

二分法は、方程式 $f (x) = 0$ の解を含む区間を、反復のたびに半分に狭めて解を近似する方法です。区間の両端で $f$ の符号が異なる連続関数であれば、確実に使えます。解を式で求められない方程式（たとえば $x^{3} - x - 1 = 0$ ）の数値解を求めるときの、最も基本的で失敗しにくい方法です。反復するごとに区間の幅がちょうど半分になるので、望む精度に必要な反復回数を前もって計算できます。

なぜそうしてよいのか

$f$ が閉区間 $[a, b]$ で連続で、 $f (a) f (b) < 0$ （両端で符号が異なる）とします。中間値の定理により、 $(a, b)$ の中に $f (α) = 0$ となる $α$ が少なくとも 1 つあります。そこで中点 $c = \frac{a + b}{2}$ での値 $f (c)$ を調べます。 $f (c) = 0$ なら解が見つかったので終わりです。そうでなければ $f (c)$ は $f (a)$ か $f (b)$ のどちらか一方と必ず符号が異なります。符号が異なる側の半分の区間 $[a, c]$ または $[c, b]$ を選べば、その区間でもまた中間値の定理が使え、解が含まれることが保証されます。

これを繰り返して得られる区間を $[a_{n}, b_{n}]$ （ $a_{0} = a, b_{0} = b$ ）とすると、毎回幅が半分になるので $b_{n} - a_{n} = \frac{b - a}{2 ^{n}}$ です。また $a_{0} \leq a_{1} \leq a_{2} \leq \dots$ は上に有界な単調増加数列、 $b_{0} \geq b_{1} \geq \dots$ は下に有界な単調減少数列なので、どちらも収束し、幅が $0$ に近づくので極限は同じ値 $α$ になります。各段階で $f (a_{n}) f (b_{n}) < 0$ が成り立つので、 $f$ の連続性から $n \to \infty$ として $f (α)^{2} \leq 0$ 、つまり $f (α) = 0$ です。こうして区間はある解 $α$ に向かって確実に縮んでいきます。

解 $α$ は常に $[a_{n}, b_{n}]$ の中にあるので、この区間のどの点を近似値にしても誤差は幅 $\frac{b - a}{2 ^{n}}$ 以下です。したがって誤差を $ε$ 以下にしたければ、 $\frac{b - a}{2 ^{n}} \leq ε$ を満たす最小の正の整数 $n$ を選べばよいことになります（中点を近似値にすれば誤差はさらにその半分 $\frac{b - a}{2 ^{n + 1}}$ 以下です）。

手順

$f$ が $[a, b]$ で連続であることと、 $f (a) f (b) < 0$ であることを確かめる。 $a_{0} = a, b_{0} = b$ とおく。
中点 $c = \frac{a _{n} + b _{n}}{2}$ を計算し、 $f (c)$ の符号を調べる。 $f (c) = 0$ なら $c$ が解なので終了する。
$f (a_{n}) f (c) < 0$ なら $a_{n + 1} = a_{n}, b_{n + 1} = c$ とし、そうでなければ（ $f (c) f (b_{n}) < 0$ なので） $a_{n + 1} = c, b_{n + 1} = b_{n}$ とする。
指定された回数になるまで手順 2・3 を繰り返す。 $n$ 回後の区間の幅は $b_{n} - a_{n} = \frac{b - a}{2 ^{n}}$ になっている。
必要な反復回数を求めるときは、 $\frac{b - a}{2 ^{n}} \leq ε$ 、すなわち $2^{n} \geq \frac{b - a}{ε}$ を満たす最小の正の整数 $n$ を求める。

例題

$f (x) = x^{2} - 2$ に区間 $[1, 2]$ から二分法を適用する。3 回反復した後の区間を $[a_{3}, b_{3}]$ とするとき、 $a_{3}, b_{3}$ を順に求めよ。

例題の解答

手順 1: $f$ は多項式なので $[1, 2]$ で連続であり、 $f (1) = - 1 < 0, f (2) = 2 > 0$ なので $f (1) f (2) < 0$ である。 $a_{0} = 1, b_{0} = 2$ とおく。

1 回目（手順 2・3）: $c = \frac{1 + 2}{2} = \frac{3}{2}$ 、 $f (\frac{3}{2}) = \frac{9}{4} - 2 = \frac{1}{4} > 0$ 。 $f (a_{0}) < 0$ と符号が異なるので $a_{1} = 1, b_{1} = \frac{3}{2}$ 。

2 回目: $c = \frac{1 + \frac{3}{2}}{2} = \frac{5}{4}$ 、 $f (\frac{5}{4}) = \frac{25}{16} - 2 = - \frac{7}{16} < 0$ 。 $f (a_{1})$ と同符号なので、解は右半分にあり $a_{2} = \frac{5}{4}, b_{2} = \frac{3}{2}$ 。

3 回目: $c = \frac{\frac{5}{4} + \frac{3}{2}}{2} = \frac{11}{8}$ 、 $f (\frac{11}{8}) = \frac{121}{64} - \frac{128}{64} = - \frac{7}{64} < 0$ 。 $f (a_{2})$ と同符号なので $a_{3} = \frac{11}{8}, b_{3} = \frac{3}{2}$ 。

手順 4 で確認: 幅は $\frac{3}{2} - \frac{11}{8} = \frac{1}{8} = \frac{2 - 1}{2 ^{3}}$ で正しい。実際 $2 \approx 1.414$ は $[\frac{11}{8}, \frac{3}{2}] = [1.375, 1.5]$ に入っている。

よって $a_{3} = \frac{11}{8}, b_{3} = \frac{3}{2}$ 。

答え: $(\frac{11}{8}, \frac{3}{2})$

よくある誤り

$f (c)$ の符号だけを見て「 $f (c) > 0$ なら右半分」のように機械的に選んでしまう誤り。正しくは端点との符号の比較で決める。上の例で $f (\frac{3}{2}) > 0$ のとき、残すのは $f (1) < 0$ と符号の異なる $[1, \frac{3}{2}]$ （左半分）である。
区間の幅を $\frac{b - a}{2 ^{n - 1}}$ や $\frac{b - a}{2 n}$ としてしまう誤り。正しくは 1 回ごとに半分になるので、 $n$ 回後の幅は $\frac{b - a}{2 ^{n}}$ （ $[1, 2]$ で 3 回なら $\frac{1}{8}$ ）。
必要な反復回数で、 $\frac{1}{2 ^{n}} \leq 1 0^{- 3}$ から $n \geq lo g_{2} 1000 \approx 9.97$ を切り捨てて $n = 9$ としてしまう誤り。 $2^{9} = 512 < 1000$ なので不足であり、正しくは切り上げて $n = 10$ （ $2^{10} = 1024 \geq 1000$ ）。
連続性を確かめずに符号変化だけで適用してしまう誤り。たとえば $f (x) = \frac{1}{x}$ は $f (- 1) f (1) < 0$ だが $x = 0$ で定義されず連続でないので、 $[- 1, 1]$ に解はない。正しくは $[a, b]$ での連続性と $f (a) f (b) < 0$ の両方を確認してから使う。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

この技能を使う問題

難易度 2（教科書の演習問題レベル）
実数 $x$ の関数 $f (x) = x^{3} - 2 x - 2$ を考える。 $f (1) < 0 < f (2)$ であり、 $[1, 2]$ において $f^{'} (x) = 3 x^{2} - 2 > 0$ であるから、方程式 $f (x) = 0$ は区間 $[1, 2]$ にただ 1 つの実数解 $α$ をもつ。
まず、 $a_{0} = 1, b_{0} = 2$ として二分法を次のように行う。 $k = 0, 1, 2, \dots$ に対し $c_{k} = \frac{a _{k} + b _{k}}{2}$ とおき、 $f (a_{k}) f (c_{k}) < 0$ ならば $a_{k + 1} = a_{k}, b_{k + 1} = c_{k}$ 、そうでなければ $a_{k + 1} = c_{k}, b_{k + 1} = b_{k}$ とする。
次に、二分法を 3 回行って得られた $a_{3}$ を初期値 $x_{0} = a_{3}$ として、ニュートン法
$x_{n + 1} = x_{n} - \frac{f ( x _{n} )}{f ^{'} ( x _{n} )}$
を 1 回だけ適用した値を $x_{1}$ とする。
また、 $b_{N} - a_{N} ≦ 1 0^{- 3}$ を満たす最小の正の整数 $N$ を考える。
$x_{1}$ と $N$ を、この順に組 $(x_{1}, N)$ で答えよ。ただし $x_{1}$ は既約分数で答えよ。