スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

[Ruby][アルゴリズム入門]非線形方程式の解法

第二章「数値計算」 目次

総合目次

2-1 乱数
2-2 数値積分
2-3 テイラー展開
2-4 非線形方程式の解法
2-5 補間
2-6 多桁計算
2-7 長いπ
2-8 連立方程式の解法
2-9 線形計画法
2-10 最小2乗法

2分法

方程式f(x)=0の根を二分法により求める。

1次方程式(グラフ上で直線)以外の方程式を非線形方程式と呼ぶ。このような方程式の根(f(x)^2が最小値(=0)になるxの値)を求める方法に二分法がある。
1:根の左右にある2点a,bをlowとhighの初期値とする。
2:lowとhighの中間点xをx=(low + high) / 2で求める。
3:f(x) > 0なら根はxより左にあるからhigh = xとし、上限を半分に狭める。f(x) < 0なら根はxより右にあるからlow = xとし、下限を半分に狭める。
4:f(x)が0か|high - low| / |low| < EPSになったときのxの値を求める根とし、そうでないなら2以後を繰り返す。EPSは収束判定値で、適当な精度を選ぶ。
# encoding: cp932
def f(x)
  return x * x * x - x + 1
end

EPS = 1e-08  # 打ち切り誤差
LIMIT = 50   # 打ち切り回数

low = -2.0
high = 2.0

1.upto(LIMIT) do |k|
  x = (low + high) / 2
  if f(x) > 0
    high = x
  else
    low = x
  end

  if f(x) == 0 or (high - low).abs < low.abs * EPS
    puts "x = #{x}"
    break
  end
  if k == LIMIT
    puts "この試行回数、または誤差設定では収束しない"
  end
end


ニュートン法

方程式f(x)=0の根をニュートン法により求める。

1:根の近くの適当な値x0を初期値とする。
2:y = f(x)のx = x0における接戦を引き、x軸と交わったところをx1とし、以下同様の手順でx2, x3, …, xn-1, xnと求めて行く。
3:ニュートン法の収束判定になったときのxnの値を求める根とし、そうでないなら2以降を繰り返す。EPSは収束判定値で、適当な精度を選ぶ。

xnは、
ニュートン法のxnを求める式
と前の値xn-1を用いて求めることができる。ニュートン法の方が2分法より収束が早い。
# encoding: cp932
def f(x)
  return x * x * x - x + 1
end

def g(x)
  return 3 * x * x - 1
end

EPS = 1e-08  # 打ち切り誤差
LIMIT = 50   # 打ち切り回数

x = -2.0

1.upto(LIMIT) do |k|
  dx = x
  x = x - f(x) / g(x)
  if (x - dx).abs < dx.abs * EPS
    puts "x = #{x}"
    break
  end
  if k == LIMIT
    puts "この試行回数、または誤差設定では収束しない"
  end
end

テーマ : プログラミング - ジャンル : コンピュータ

コメント
コメントの投稿
管理者にだけ表示を許可する

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。