二分法

定理 13.1   [中間値の定理] $y = f(x)$ が $[a,b]$ で連続, $f(a)<0$, $f(b)>0$ なら ある $c \in (a,b)$ が存在して $f(c)=0$.

証明を思い出せば次のアルゴリズムを得る:

アルゴリズム 13.1   [二分法]

$\epsilon$ : 許容誤差

$A \leftarrow a$

$B \leftarrow b$


while ($\vert A-B\vert > \epsilon$) 


do 

		 $C \leftarrow (A+B)/2$


if ( $f(C) = 0$ ) break


else if ( $f(C) < 0$ ) $A = C$


else $B = C$


end do


return $C$

do ループの $n$ 回目の実行における $A$, $B$ を $A_n$, $B_n$ と書くと $\vert A_n-B_n\vert = 1/2^n \vert a-b\vert$ で $f(A_n) < 0$, $f(B_n) > 0$ より $f(C) = 0$ なる $C$ が $(A_n,B_n)$ 内に存在する. よって $n$ を十分大にとれば $f(C) = 0$ なる $C$ が誤差 $\epsilon$ 以内で求まる.

二分法は安定だが, 二進法でいえば一桁ずつしか求まらない.