1変数方程式を数値計算で解く（Ruby）

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 でした。