昔、夏と冬の間の秋という季節の存在が中間値の定理によって保証されていた。

　秋という季節はなくなり、日本は四季が一つつゆと消え、寒暖の差は瀑布のごとくになった。秋麗(あきうらら) は雀の涙ほど僅少となって、昔日に羨望を抱かざるを得ない。

　それと同時に食欲の秋、スポーツの秋などという秋の文化は次第に人々からなくなってしまうのではないかと憂慮する。

　嘆いていてもしかたがない。なぜならこれから数学の話をするのだから。

　数学において、解がどれくらいの値かを予測することは重要である。数値計算が数学の証明上必要になる場面なぞいくらでもあるだろう。しかし、ここで残念なお知らせがある。

　それは、一般の関数では二次方程式のように解の公式があるとは限らないということだ。そこで、実数の近似解を求めるための手続きを人類は編み出してきた。

　このように、与えられた方程式から真の答え、すなわち解に十分に近い答えを求める手続き、もっと詳(つまび) らかに言えば、その手続きを繰り返していくことで、解にいくらでも近づける手続き、のことを求根アルゴリズムという。

求根アルゴリズムには様々なものがあるが、今回はおそらく最も単純である二分法と呼ばれる方法を紹介し、その原理を証明する。

　 $f(x)=0$ という方程式を解くことを考える。 $f(x)=x^3-x-1$ としても、 $f(x)=x-\cos x$ としても良い。また、閉区間 $[x_0,y_0]$ では $f$ は連続かつ単調増加であり、 $f(x_0)\leq0,f(y_0)\ge0$ が成り立つとする。

　このとき、実数列 $x_n,y_n$ を次のように定める。

解数列の構成

$f\bigg(\dfrac{x_n+y_n}{2}\bigg)\leq 0$ であれば $x_{n+1}=\dfrac{x_n+y_n}{2}$ と定め、そうでなければ $x_{n+1}=x_n$ と定める。

$f\bigg(\dfrac{x_n+y_n}{2}\bigg)\ge 0$ であれば $y_{n+1}=\dfrac{x_n+y_n}{2}$ と定め、そうでなければ $y_{n+1}=y_n$ と定める。

　定義が分かりにくいので、定められた実数列を可視化する。

　定義で定めた実数列において、次のような定理が成り立つ。

二分法の原理

$y_{n+1}-x_{n+1}\leq\dfrac{y_n-x_n}{2}$ が成立し、 $\displaystyle \lim_{n\to\infty}x_n=\lim_{n\to\infty} y_n=c$ となって $f(c)=0$

　解の精度の保証をつけてくれるのが一番上で述べられている不等式である。これによれば、解が含まれる区間は繰り返すごとに $\dfrac{1}{2}$ の長さとなる。

　早速証明をつけよう。必要な道具は単純なアルゴリズムから推定できるように、非常に簡単なものである。

$Proof$

　まず初めに、証明を楽に進めるための補題を示す。

区間は空ではない

$y_n\ge x_n$ が成立する

$Proof$

　数学的帰納法により証明する。定義より $n=0$ のときは良い。 $x_n\leq y_n$ を仮定して、 $x_{n+1}\leq y_{n+1}$ を示す。 $f\bigg(\dfrac{x_n+y_n}{2}\bigg)$ の符号によって場合わけする。

　 $f\bigg(\dfrac{x_n+y_n}{2}\bigg)>0$ を仮定する。この時、 $x_{n+1}=x_n$ と $y_{n+1}=\dfrac{x_n+y_n}{2}$ が定義により成立するので、 $y_{n+1}-x_{n+1}=$ $\dfrac{y_n-x_n}{2}\ge0$ が導かれる。

　 $f\bigg(\dfrac{x_n+y_n}{2}\bigg)<0$ を仮定する。この時、 $x_{n+1}=\dfrac{x_n+y_n}{2}$ と $y_{n+1}=y_n$ が成り立つので、 $y_{n+1}-x_{n+1}=$ $\dfrac{y_n-x_n}{2}\ge0$ が成り立つ。

　 $f\bigg(\dfrac{x_n+y_n}{2}\bigg)=0$ を仮定する。このとき、 $x_{n+1}=\dfrac{x_n+y_n}{2}$ と $y_{n+1}=\dfrac{x_n+y_n}{2}$ が定義より導かれて、 $y_{n+1}-x_{n+1}=0$ が成り立つため不等式はこのときも成り立っている。 $◽︎$

　これと似たような場合わけをすることで、定理の最初に掲げられた不等式が示せる。

精度の評価

$y_{n+1}-x_{n+1}\leq\dfrac{y_n-x_n}{2}$ が成立する

$Proof$

　定義に則って示そう。 $y_{n+1}-x_{n+1}$ を場合わけして漸化式で変形する。 $f\bigg(\dfrac{x_n+y_n}{2}\bigg)>0$ とする。このとき、

$y_{n+1}-x_{n+1}=$ $\dfrac{x_n+y_n}{2}-x_n=$ $\dfrac{y_n-x_n}{2}$

が成立する。

$f\bigg(\dfrac{x_n+y_n}{2}\bigg)<0$ とする。このとき、

$y_{n+1}-x_{n+1}=$ $y_n-\dfrac{x_n+y_n}{2}=$ $\dfrac{y_n-x_n}{2}$

が成立する。

　最後に $f\bigg(\dfrac{x_n+y_n}{2}\bigg)=0$ とする。

　このとき、 $y_{n+1}-x_{n+1}=0$ が成り立つ。先ほど示した補題によって $y_n-x_n\ge 0$ であるので $y_{n+1}-x_{n+1}\leq$ $\dfrac{y_n-x_n}{2}$ が成り立っている $◽︎$

　 $x_n\leq x_{n+1}\leq y_0$ と $x_0\leq y_{n+1}\leq y_n$ を示す。これを示すことで単調収束定理によって

　 $\displaystyle\lim_{n\to\infty}x_n=x^{\star}$ と $\displaystyle\lim_{n\to\infty}y_n=y^{\star}$ が示せる。

　一番初めは $x_n\leq x_{n+1}$ と $y_{n+1}\leq y_n$ を示すのが筋が良いだろう。

　 $f\bigg(\dfrac{x_n+y_n}{2}\bigg)\leq 0$ であれば $x_{n+1}=\dfrac{x_n+y_n}{2}$ と定義され、 $x_n\leq x_{n+1}$ は $x_n\leq y_n$ という不等式によって正しい。

　 $f\bigg(\dfrac{x_n+y_n}{2}\bigg)\leq 0$ でなければ、 $x_{n+1}=x_n$ が成り立ち不等式は自動的に満たされる。

　 $y_n$ についても同様の議論が成り立つ。 $f\bigg(\dfrac{x_n+y_n}{2}\bigg)\ge 0$ であれば $y_{n+1}=\dfrac{x_n+y_n}{2}$ と定義され、 $y_{n+1}\leq y_n$ は $x_n\leq y_n$ という不等式によって正しい。

　 $f\bigg(\dfrac{x_n+y_n}{2}\bigg)\ge 0$ でなければ、 $y_{n+1}=y_n$ が成り立つ。

　さて、この単調性の証明により $x_0\leq x_n$ と $y_n\leq y_0$ という不等式が成り立つことも同時に示される。これと $x_n\leq y_n$ を合わせると、 $x_n\leq x_{n+1}\leq y_0$ と $x_0\leq y_{n+1}\leq y_n$ が示された。

　そして最初に示した不等式 $y_{n+1}-x_{n+1}\leq\dfrac{y_n-x_n}{2}$ を帰納的に用いることで、 $y_n-x_n\leq\dfrac{y_0-x_0}{2^n}$ が示せる。これによって $\displaystyle\lim_{n\to\infty}(y_n-x_n)=0$ が成り立つ。よって $x^{\star}=y^{\star}$ 、つまり二つの数列の極限値が等しくなることが導かれた。

　ここで $c=x^{\star}$ と置き直す。 $x_n,$ $y_n$ の定義によって $f(x_n)\leq 0\leq f(y_n)$ である。 $f$ の連続性によって $\displaystyle \lim_{n\to\infty}f(x_n)=$ $\displaystyle \lim_{n\to\infty}f(y_n)=$ $f(c)$ が成り立つことが分かる。極限をとっても順序は保たれるので、 $f(c)\leq0\leq f(c)$ が成り立って、これにより $f(c)=0$ が結論される $◽︎$

　ちょっと厳密性を要求すると途端に証明が長くなってしまったが、これにて証明は完了した。またこの二分法から次のような系が従う。

中間値の定理

$f$ を $[a,b]$ 上単調で連続な関数として、 $f(a)\leq0\leq f(b)$ を仮定すると、 $f(c)=0$ となる $a\leq c\leq b$ が存在する

　さらに証明から分かることとして、次のような定理が成り立つ。

要求精度までの繰返し回数

$f(x_n),f(y_n)\neq 0$ が成り立つとき、 $y_n-x_n<\epsilon$ をみたす $n$ は $\dfrac{y_0-x_0}{\epsilon}<2^n$ を満たしている

　例えば二点 $0,1$ をとったとして、区間が $0.01$ の範囲までに減少するのにかかる繰り返しの回数は $\dfrac{1-0}{0.01}<2^n$ をみたす最小の自然数 $n$ である。それは $n=7$ であるので $7$ 回二分法の手続きを行うことで解の不確かさが $0.01$ まで確実に減らせるということである。