Python - ニュートン補間！

[ プログラミング, 数学 ] [ Python ]

Python 3 でニュートン補間を行う方法についての記録です。

0. 前提条件

  • LMDE 2 (Linux Mint Debian Edition 2; 64bit) での作業を想定。
  • Python 3.6.4 での作業を想定。
  • 当方は他のバージョンとの共存環境であり、 python3.6, pip3.6 で 3.6 系を使用するようにしている。（適宜、置き換えて考えること）

1. アルゴリズムについて

当ブログ過去記事を参照。

2. Python スクリプトの作成

  • 敢えてオブジェクト指向で作成している。
  • Shebang ストリング（1行目）では、フルパスでコマンド指定している。（当方の慣習）
  • 必要であれば、スクリプト内の定数を変更する。
interpolate_newton.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

#! /usr/local/bin/python3.6
"""
Interpolation with Newton method
"""
import sys
import traceback


class InterpolateNewton:
    X = [0.0, 2.0, 3.0, 5.0, 8.0]
    Y = [0.8, 3.2, 2.8, 4.5, 1.9]

    def __init__(self):
        self.n = len(self.X)

    def compute(self):
        """ Computation of interpolation with Newton method """
        try:
            print("      x      y")
            for a in range(int(self.X[-1]) * 2 + 1):
                t = 0.5 * a
                print("{:7.2f}{:7.2f}".format(t, self.__interpolate(t)))
        except Exception as e:
            raise

    def __interpolate(self, t):
        """ Interpoalation with Newton method

        :param float t
        """
        try:
            c = [0 for _ in range(self.n)]
            w = [0 for _ in range(self.n)]
            for i in range(0, self.n):
                w[i] = self.Y[i]
                for j in reversed(range(i)):
                    w[j] = (w[j + 1] - w[j]) / (self.X[i] - self.X[j])
                c[i] = w[0]
            s = c[self.n - 1]
            for i in reversed(range(self.n - 1)):
                s = s * (t - self.X[i]) + c[i]
            return s
        except Exception as e:
            raise


if __name__ == '__main__':
    try:
        obj = InterpolateNewton()
        obj.compute()
    except Exception as e:
        traceback.print_exc()
        sys.exit(1)

3. Python スクリプトの実行

まず、実行権限を付与。

1

$ chmod +x interpolate_newton.py

そして、実行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

$ ./interpolate_newton.py
      x      y
   0.00   0.80
   0.50   2.49
   1.00   3.23
   1.50   3.37
   2.00   3.20
   2.50   2.95
   3.00   2.80
   3.50   2.85
   4.00   3.17
   4.50   3.74
   5.00   4.50
   5.50   5.32
   6.00   6.03
   6.50   6.37
   7.00   6.05
   7.50   4.70
   8.00   1.90

以上