スポンサーサイト

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

[Ruby][アルゴリズム入門]補間

第二章「数値計算」 目次

総合目次

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

ラグランジュ補間

何組かのx, yデータが与えられているとき、これらの点を通る補間多項式をラグランジュ補間により求め、データ点以外の点を求める。

(x0, y0), (x1, y1), …, (xn-1, yn-1)というn個の点が与えられたとき、これらの点を全て通る関数f(x)は次のように求められる。
ラグランジュ補間のf(x)を求める式
def lagrange(x, y, n, t)
  s = 0.0
  n.times do |i|
    p = y[i]
    n.times do |j|
      p = p * (t - x[j]) / (x[i] - x[j]) unless i == j
    end
    s = s + p
  end
  return s
end

x = [0.0, 1.0, 3.0, 6.0, 7.0]
y = [0.8, 3.1, 4.5, 3.9, 2.8]

puts "      x       y"
(0.0).step(7.0, 0.5) do |t|
  printf "%7.2f%7.2f\n"%[t, lagrange(x, y, 5, t)]
end


ニュートン補間

何組かのx, yデータが与えられているとき、これらの点を通る補間多項式をニュートン補間により求め、データ点以外の点を求める。

ニュートンの補間公式
fj(x)を,fj(xi)=yi,i=0,・・・,j
を満たす高々j次の多項式とすると,
fj+1(xi)=yi,i=0,・・・,j,j+1
を満たす高々j+1次の多項式fj+1(xi)は適当な定数cj+1に対して次の式で与えられる。

fj+1(x)=fj(x)+cj+1(x-x0)(x-x1)・・・(x-xj)

ニュートンの補間公式
def newton(x, y, n, t)
  flag = true
  a = Array.new(100) # 係数配列
  w = Array.new(100) # 作業用
  if flag
    n.times do |i|
      w[i] = y[i]
      (i - 1).downto(0) do |j|
        w[j] = (w[j + 1] - w[j]) / (x[i] - x[j])
      end
      a[i] = w[0]
    end
    flag = false
  end
  s = a[n - 1]
  (n - 2).downto(0) do |i|
    s = s * (t - x[i]) + a[i]
  end
  return s
end

x = [0.0, 1.0, 3.0, 6.0, 7.0]
y = [0.8, 3.1, 4.5, 3.9, 2.8]

puts "      x       y"
(0.0).step(7.0, 0.5) do |t|
  printf "%7.2f%7.2f\n"%[t, newton(x, y, 5, t)]
end

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

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

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