1変数方程式を数値計算で解く(Ruby)
方程式 f(x) = 0 を
ある区間 [a, b] において、f(x) が単調増加、連続、f(a) < 0、f(b) > 0
であるとして、数値計算で解いてみます。具体的には n の平方根を求めてみます。
区間2分法
区間の中点をとってその点での値を評価し、左右の適切な区間を選択して再帰的に追い詰めていきます。
def binary_search(n) a = 0; b = n while (a - b).abs > 0.000000000000001 c = (a + b) / 2.0 if c * c > n b = c else a = c end end a end puts binary_search(2) #=>1.414213562373095
ニュートン法
適当に x = r という近似値で f(x) における接線を求め、接線と x軸が交わる点を x = r1 とし、これを繰り返していきます。f(x) は当然微分可能でなければなりません。
具体的には
なので、
ですから、ここに f(x) = x^2 - n を入れて計算します。
def newton(n) r = 0; r1 = n while (r1 - r).abs > 0.000000000000001 r = r1 r1 = r / 2.0 + n / (2 * r) end r end puts newton(2) #=>1.414213562373095
これらの例では、Ruby の浮動小数点演算の最大桁数まで計算してみました。求めるのに必要な時間は共に似たようなもので、ほぼ 40ms でした。