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

第二章「数値計算」　目次

総合目次

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

ラグランジュ補間

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

(x0, y0), (x1, y1), …, (xn-1, yn-1)というn個の点が与えられたとき、これらの点を全て通る関数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データが与えられているとき、これらの点を通る補間多項式をニュートン補間により求め、データ点以外の点を求める。

ニュートンの補間公式
ｆｊ（ｘ）を，ｆｊ（ｘｉ）＝ｙｉ，ｉ＝０，・・・，ｊ
を満たす高々ｊ次の多項式とすると，
ｆｊ＋１（ｘｉ）＝ｙｉ，ｉ＝０，・・・，ｊ，ｊ＋１
を満たす高々ｊ＋１次の多項式ｆｊ＋１（ｘｉ）は適当な定数ｃｊ＋１に対して次の式で与えられる。

ｆｊ＋１（ｘ）＝ｆｊ（ｘ）＋ｃｊ＋１（ｘ－ｘ０）（ｘ－ｘ１）・・・（ｘ－ｘｊ）

ニュートンの補間公式

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