Python言語によるプログラミングイントロダクション(３)

Python言語によるプログラミングイントロダクション第２版ーデータサイエンスとアプリケーション（著者：Jhon V. Guttag　監訳：久保幹雄）を読んだ学習を記録していきます。解釈や理解が間違えである場合も多々あるかと思います、、、

第３章　簡単な算術プログラミング

３.１　総当り
　総当りは試行錯誤法の一種である。総当り法は全て列挙するプログラミングになるために、一見して愚かな解法に見えるが、一般的に実装が易しくて理解することも用意であるために、最も実用的な方法とされる。
　ループを書く際は必ず、適切な減少関数について検討するべきである。これは以下の特性を持っている関数を指す。
　・関数はプログラミング内の変数の集合を整数値に写像する。
　・ループに入った際、その値が負ではない。
　・値が０以下の場合、ループが終了する。
　・ループを通るたびに値が現象する。
　ループなどがうまく実行されているかを確認するために、printを挿入して実行動作を確認すると良い。

３.２　forループ

for 変数 in シーケンス:
    コード

　forループは繰返し処理を単純化したものである。変数にシーケンスで指定した値が順番に代入されて処理されていくのがfor文になる。for文は初めに指定したシーケンスで処理されるためにfor文の処理内でシーケンスに影響を与えることは無い。

３.３　近似解と2分法
　総当り法などで、徐々に解に近づけていき解の近似値を導き出す方法がある。より効率的に近似解を導き出すアルゴリズムとして、2分法の考え方がある。2分法では、範囲を二つに分けたときにどちらに解が存在するかを判別して、範囲を絞っていき近似解を見つける方法である。

３.４　浮動小数点数型の利用に関する注意
　コンピュータは２進数で計算を行うために、10進数の0.1などを正確に計算することが難しい。そのため、プログラミングによっては、微小な誤差を丸め込んで評価する必要があることがしばしば出てくる。

３.５　ニュートン・ラフソン法
　ニュートン・ラフソン法は最も一般的に用いられている近似アルゴリズムの一つである。これは、１変数の多項式の解を求める際の近似アルゴリズムとして利用される。式：ax^2+bx+c=0のような式の解を求める際に利用される（実数解をもつ場合）。解の推定値をguessのgとした時、上の式の左辺に代入した式をF(g)=ag^2+bg+cとする。この式の値が0に近づくようにしていく。g'=g-F(g)/F'(g)で求められるg'を次の推定値としていくと解に近似していくことが自明になっておりそれを利用して求める方法がニュートン・ラフソン法になる。

最後に、この章の練習問題に１つ挑戦してみる、、、

問題：根を見つけるための反復数を追跡し続けるよう、ニュートン・ラフソン法の実装コードにコードを追加せよ。また、このコードを用いて、ニュートン・ラフソン法と2分法の効率を比較せよ。

# ニュートン・ラフソン法の実装コード
epsilon = 0.01
k = 24.0
guess = k/2.0
while abs(guess*guess - k) >= epsilon:
   guess = guess - (((guess**2) - k)/(2*guess))
print('Square root of', k, 'is about', guess)

x = 24
epsilon = 0.01
k = 24.0
guess = k/2.0
counting = 0
low = 0.0
high = max(1.0, x)
ans = (high + low)/2.0
# ニュートン・ラフソン法
while abs(guess*guess - k) >= epsilon:
    guess = guess - (((guess**2) - k)/(2*guess))
    counting += 1
print('Square root of', k, 'is about', guess)
print('Number of iterations is ', counting)

# 2分法
while abs(ans**2 - x) >= epsilon:
   print('low =', low, 'high =', high, 'ans =', ans)
   counting += 1
   if ans**2 < x:
       low = ans
   else:
       high = ans
   ans = (high + low)/2.0
print('Number of iterations is ', counting)
print(ans, 'is close to square root of', x)

# 実行結果
Square root of 24.0 is about 4.8989887432139305
Number of iterations is  4
Number of iterations is  13
4.8984375 is close to square root of 24 

重要語句
減少関数、試行錯誤法、2分法、ニュートン・ラフソン法