2022年度プログラミング演習A・B

第4回レポート課題の解説

演習1

$b-a<0.02$ となるまで、二分法の操作を手動で繰り返し行ってください。「手動で行う」演習ですので、if文、for文、while文を使わないこと。Markdownとして説明を付ける必要はなく、コードのみを書けばよいです。

演習2

二分法のアルゴリズムを実現するコードを書き、関数 $f(x)=x^3-2$ に対して方程式 $f(x)=0$ の区間 $[0,3]$における近似解を求めてください。ただし、許容誤差 $TOL=0.00001$ とします。

(考察)

求めた近似解を厳密解と比較してみると、誤差は確かに許容誤差 $TOL$ よりも小さくなっていることが分かります。

演習3

二分法のアルゴリズムにおける区間の両端の初期値 $a$ と $b$、許容誤差 $TOL$、反復回数 $n$ の関係について考察してください。Markdownのセルに解答を書いてください。

(解答)

二分法のアルゴリズムにおいては一回の反復で区間の幅が半分になるので、$n$ 回反復した後の区間の幅は

$$ \frac{b-a}{2^n} $$

です。反復の終了条件を考えると、

$$ \frac{b-a}{2^n}<2\cdot TOL $$

が成り立つことが分かります。これを $n$ について解くと、

$$ n>\log_2 \frac{b-a}{TOL}-1 $$

が得られます。つまり、 反復回数 $n$ はこの不等式の右辺より大きな最小の自然数になります。

実際に $a=0$、$b=3$、$TOL=0.00001$ の場合には次のコードから $n=18$ になることが分かり、演習2の結果に一致します。

演習4(オプション)

二分法のアルゴリズムにおいて、計算量の観点から関数 $f$ の値の計算回数は最小限に抑えるべきです。$f(a)$ の値を格納する変数 $fa$ と $f(p)$ の値を格納する変数 $fp$ を新たに用いることで、演習2のコードを改良してください。

反復回数を $n$ とするとき、演習2のコードでは関数 $f$ を呼び出す回数は $2n$ 回ですが、演習4のコードでは $(n+1)$ 回に抑えることができています。 関数 $f$ が複雑であればあるほど、コード全体の計算量(実行時間)に差が生じます。