算術計算法の基礎 with Python

基本的な算術アルゴリズムのまとめ。

1.力まかせ探索

力まかせ探索（ちからまかせたんさく、英: Brute-force search）またはしらみつぶし探索（英: Exhaustive search）は、単純だが非常に汎用的な計算機科学の問題解決法であり、全ての可能性のある解の候補を体系的に数えあげ、それぞれの解候補が問題の解となるかをチェックする方法である。(wikipedia)

以下は入力された数字が立方根かどうかを判定するプログラムです。

x = int(raw_input('整数を入力してください: '))
number = 0
while number** 3 < abs(x):
	number = number + 1
if number**3 != abs(x):
	print x, 'は立方根ではありません'
else:
	if x < 0:
		number = -number
	print  '立方根は', x, 'です。' number

とりあえず、一番小さい数字から手当たり次第に調べよう！みたいな感じですね。昔のパソコンだと場合によっては時間がかなりかかってたらしいのですが、今のパソコンなら全く問題なく、最も実用的らしいです。

まず、入力した値と自然数の三乗を小さい順に比較していき、自然数の三乗の値が入力値より大きくなった時点で評価する。
ただし、入力値がゼロの場合は除外。

大きくなった時点で評価しているので、1を引く。

2. 近似解と力まかせ探索

負でない数の平方根をだすプログラム。以下は力まかせ探索を用いた平方根近似の例。対象とする数字は25。

x = 25
gosa = 0.01
step = gosa**2
y = 0
ans = 0.0
while abs(answer**2 - x) >= gosa and answer <= x:
	answer += step
	y += 1
print 'y =', y
if abs(ans ** 2 - x) >= gosa:
	print  x,'は失敗'
else:
	print answer, 'が、', x,'の近似解に一番近い'

25は完全平方数であるが、こちらのプログラムを使用すると、5は答えとしてはでてこず、それに一番近い近似解、4.999がでてくる。しかし、このプラグラムだと、かなりおおきな数を調べると適切な数を見落としてしまう。これを解消するために、あるプログラムを考える。

xの近似平方根を探す違うアプローチのプログラム。
まず、0からmaxの間に解が存在すると仮定し、数字は規則ただしいという事実をうまく利用する。すなわち、異なった数のペア(n1, n2)がn1n2であることを利用する。つまり、xの平方根を下の線上のどこかにあると仮定する。

正しい答えでない場合、正しい答えより大きいか小さいかを判断する。もし正しい答えより大きい場合、答えが左にならなければいけないことは既知である。小さい場合、答えは右になければならない。そしてさらに小さい間隔でこの処理を繰り返す。

x = 25
gosa = 0.01
y = 0
low = 0.0
high = max(1.0,x)
answer = (high + low)/2.0
while abs(answer**2-x) >= gosa:
	print 'low=', low, 'high=', high, 'answer=',answer
	y += 1
	if answer**2 < x:
		low = answer
	else:
		high = answer
	answer = (high + low)/2.0
print 'y = ', y
print answer, 'が', x,'の近似解に一番近い'

探索される空間サイズが半分にカットされている。探索空間をこのように半分にしているこの方法をは2分法と呼ばれる。

ニュートンーラフソン法

数値解析の分野において、ニュートン法（ニュートンほう、Newton's method）またはニュートン・ラフソン法（Newton-Raphson method）は、方程式系を数値計算によって解くための反復法による求根アルゴリズムの1つである。対象とする方程式系に対する条件は、領域における微分可能性と2次微分に関する符号だけであり、線型性などは特に要求しない。収束の速さも2次収束なので古くから数値計算で使用されていた。名称はアイザック・ニュートンとジョゼフ・ラフソン（英語版）に由来する。(wikipedia)

ニュートンは、ある値(以降xとよぶ)が多項式(p)の根の近似解である場合、

は、よりよい近似解であるという定理を証明した。任意の定数kと係数cに対しての一次導関数は2cxである。またの一次導関数は2xである。ゆえに現在の現在の予測値(y)にもとずき、次の予測値としてを選ぶことで改良できる。これを逐次近似とよぶ。
以下はニュートンーラフソン法の例。

gosa = 0.01
k = 24.0
y = k/2.0
while abs(y**2 - k) >= gosa:
	y = y - (((y**2) - k)/(2*y))
print k,'の平方根は', y

こうゆうのもっと勉強していきたいですよね！

参考文献

Amazon.co.jp： Python言語によるプログラミングイントロダクション: 世界標準MIT教科書: ジョン・V. グッターグ, John V. Guttag, 久保幹雄: 本