next up previous
Next: 5.2 Newton $BK!(B Up: 5 $BHs@~7AJ}Dx<0$r7W;;5!$G2r$/(B Previous: $BJ}Dx<0$,6h4V(B $B$K$?$@0l$D$N2r$r;}$D$3$H$N>ZL@(B

5.1 $BFsJ,K!(B (bisection method)

$BHy@QJ,$G4pK\E*$J(B$BCf4VCM$NDjM}(B$B$rI|=,$7$h$&!#(B


\begin{jtheorem}[$BCf4VCM$NDjM}(B]\upshape
$f: [\alpha,\beta] \to \R$ $B$rO

($B$D$^$j(B $f(\alpha)f(\beta)<0$ $B$H$J$k(B $\alpha$, $\beta$ $B$,$"$l$P!"J}Dx(B $B<0(B $f(x)=0$ $B$N2r(B $x=c$ $B$,6h4V(B $(\alpha,\beta)$ $BFb$KB8:_$9$k$H$$$&$3$H!#(B)

$B$3$NDjM}$N>ZL@$N;EJ}$O?'!9$"$k$,!"(B $BBeI=E*$J$b$N$K(B$B6h4V=L>.K!(B$B$r;H$C$?$b$N$,$"$k!#(B $B$=$l$O0J2<$N$h$&$J6Z=q$-$G?J$`!#(B


$B, $\{b_n\}$ $B$rDj$a$k!#(B
(i)
$a_0=\alpha$, $b_0=\beta$ $B$H$9$k!#(B
(ii)
$BBh(B $n$ $B9`(B $a_n$, $b_n$ $B$^$GDj$^$C$?$H$7$F!"(B $c_n=(a_n+b_n)/2$ $B$H$*$-!"(B $f(a_n)f(c_n)<0$ $B$J$i(B $a_{n+1}=a_n$, $b_{n+1}=c_n$, $B$=$&$G$J$$$J$i(B $a_{n+1}=c_n$, $b_{n+1}=b_n$ $B$H$9$k!#(B

$B$9$k$H!"(B

\begin{displaymath}
a_0 \le a_1 \le a_2 \le \cdots \le a_n \le a_{n+1} \le \cdo...
...\cdots \le b_{n+1} \le b_n \le \cdots \le b_2 \le b_1 \le b_0
\end{displaymath}


\begin{displaymath}
a_n < b_n \le b_0 \quad\hbox{($n\in\N$)}\quad
\hbox{$B$5$i$K(B} \quad a_0\le a_n < b_n \quad\hbox{($n\in \N$)},
\end{displaymath}


\begin{displaymath}
b_n-a_n=(\beta-\alpha)/2^n \to 0 \quad \hbox{(as $n\to \infty$)},
\end{displaymath}


\begin{displaymath}
f(a_n)f(b_n)\le 0 \quad\hbox{($n\in\N$)}.
\end{displaymath}

$B$3$l$+$i(B

\begin{displaymath}
\lim_{n\to+\infty}a_n=\lim_{n\to+\infty}b_n=c, \quad \alpha < c < \beta
\end{displaymath}

$B$H<}B+$7$F(B

\begin{displaymath}
f(c)=0
\end{displaymath}

$B$,@.$jN)$D$3$H$,J,$+$k!#(B

$B0J>e$N>ZL@$N $f(\alpha)f(\beta)<0$ $B$H$J$k(B $\alpha$, $\beta$ $B$,J,$+$C$F$$$k>l9g$K!"(B $BJ}Dx<0(B $f(x)=0$ $B$N6a;w2r$r5a$a$k%"%k%4%j%:%`$,F@$i$l$k(B ($B0J2<$G$O(B $\leftarrow $ $B$OJQ?t$X$NBeF~$rI=$9(B)$B!#(B

$BFsJ,K!$N%"%k%4%j%:%`(B
(1)
$BL\I8$H$9$k8m:9(B $\varepsilon$ $B$r7h$a$k!#(B
(2)
$a \leftarrow \alpha$, $b \leftarrow \beta$ $B$H$9$k!#(B
(3)
$c \leftarrow (b + a) / 2$ $B$H$7$F(B $f(a)f(c)<0$ $B$J$i$P(B $b \leftarrow c$$B!"$=$&(B $B$G$J$1$l$P(B $a \leftarrow c$ $B$H$9$k(B
(4)
$\vert b-a\vert \ge \varepsilon$ $B$J$i$P(B (1) $B$KLa$k!#$=$&$G$J$1$l$P(B $c$ $B$r(B $B2r$H$7$F=PNO$9$k!#(B


\begin{jremark}[$BH?I|$NDd;_$N$?$a$N(B $\eps$]\upshape
$BL\I8$H$9$k8m:9$H$7$F$O!,$B%r(B ($B!"%&!"%[%=t$rI=$9$N$K!"C(B $B8@8l$G$O(B \lq\lq {\tt1.0e-15}'' $B$H=q$/(B)$B!#(B \end{jremark}"> 11 12


next up previous
Next: 5.2 Newton $BK!(B Up: 5 $BHs@~7AJ}Dx<0$r7W;;5!$G2r$/(B Previous: $BJ}Dx<0$,6h4V(B $B$K$?$@0l$D$N2r$r;}$D$3$H$N>ZL@(B
Masashi Katsurada
$BJ?@.(B20$BG/(B10$B7n(B18$BF|(B