二分法について

質問

(１)
f(x)=0の解aを内部に含む長さ１の区間から出発して、二分法で解の近似値を計算するとき、誤差が0.01以下になるようにするには、「中点におけるf(x)の値を求め、その符号を調べる」という計算を何回行う必要があるか。

(２)区間[1,2]から出発して、二分法でx^2-2=oの解√2の値を小数点以下第二桁まで正確に得るためには何回の計算が必要か。実際に縮小する区間列を計算によって求めることにより調べよ。

二分法の計算方法はわかるのですが(１)はとりかかり方がわからず、(２)は、縮小する区間列の計算がわかりません。

心優しい方、お助けねがいます。

回答No.1

Mr_Holland · ベストアンサー

(1)　二分法では、調べる区間が (1/2)^n で小さくなっていきますので、これが誤差の限界になります。
　したがって、「誤差が0.01以下になるようにするには」、(1/2)^nが0.01以下になる自然数ｎの最小の値を求めればよいことになります。そのため、次の式が成り立ちます。
　　(1/2)^n　≦　0.01
　⇔-n・log_10(2) ≦ -2
　⇔ｎ≧ 2/log_10(2) ＝ 6.64・・・
　∴ｎ＝７
　したがって、二分法を最低７回は行わないといけないことがわかります。
　ちなみに、検証のため、このときの最大の誤差を求めてみますと、　　(1/2)^7＝0.0078125　＜0.01
　　(1/2)^6＝0.015625　＞0.01
となりますので、６回では足りなく、7回で初めて誤差0.01以下を満足させることが分かります。

(2)　この問題も同様なのですが、今回は解が具体的に√２＝1.41421356 と分かっていて、二分法で求めた結果を小数点以下第三位で四捨五入して「小数点以下第二桁まで正確に得る」ものとして考えると、最大の誤差は、
　　0.005-(1.41421356-1.41)＝0.0007864
でなければなりません。
　そこで、(1)と同様に、最大の誤差がこの範囲に収まるようなｎと求めますと、
　　(1/2)^n ＜ 0.0007864
　　-n・log_10(x) ＜-3.104
　　ｎ ＞ 3.104/log_10(2)＝10.31
　∴ｎ＝１１
となります。
　ここで、実際にｎ＝１１のときの区間列の長さを調べますと、
　　(1/2)^11＝0.00048828125
となります。
　これを√２＝1.4142135623730950488016887242097　に加えますと、
　　√２＋(1/2)^11
　＝1.4142135623730950488016887242097　＋0.00048828125
　＝1.4147018436230950488016887242097
　≒1.41
と「小数点以下第二桁まで正確に得る」ことができています。
　一方、ｎを１つ減らしたｎ＝１０で計算してみますと、
　　(1/2)^10＝0.0009765625
　　√２＋(1/2)^10
　＝1.4142135623730950488016887242097　＋0.0009765625
　＝1.4151901248730950488016887242097
　≒1.42　≠１．４１
となり、「小数点以下第二桁まで正確に得る」ことができなかったことが確認できます。

回答No.2

noname#101087

(1) のほうは f(xo)=0 として、f'(xo) の大きさに依存しそうです。

xo を含む長さ1 の区間における f'(xo) の上限 A が予め判っておれば、
|f(xo)| < e を許容誤差として、
　　A*(1/2^m) < e
を満足させれば充分でしょう。つまり、
　　m > (Log A/e)/(Log 2) = (Log A - Log e)/(Log 2)

e=0.01 の場合なら、(Log : 常用対数)
　　m > (Log A +2)/0.30 = Log A/0.30 + 2/0.30 ≒ Log A/0.30 + 7