何組かの x, y データが与えられ、これらの点全てを通る補間多項式を求める方法に「ニュートン補間」というものがあります。
先日は「ラグランジュ補間」について紹介しました。
以下、一部 で記載。
アルゴリズムとしては、係数(差分商)を求め、求まった多項式から補間点を算出していく形になる。
以下、C++ によるサンプルソースです。
0. 前提条件
- Linux Mint 14 Nadia (64bit) での作業を想定。
- g++ (Ubuntu/Linaro 4.7.2-2ubuntu1) 4.7.2
- ニュートン補間そのものについての詳細は割愛。
1. C++ ソース作成
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 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 |
|
2. C++ ソースコンパイル
1
|
|
何も出力されなければ成功です。
3. 実行
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
あらかじめ与えられた点以外の点も計算されているのが分かる。
また、「ラグランジュ補間」と同じ結果になっているのも分かる。(C++ - ラグランジュ補間!)
4. グラフ
参考までに、 R でグラフを作成してみた。
数学はおもしろいけど、コンピュータで実証するというのもおもしろいです。
※ちなみに最近の当方の C++ アルゴリズムについての記事は、古い C によるアルゴリズムに関する書物を参考に C++ に移植した形態となっています。
以上。