スプライン補間

数値解析という数学の分野において、スプライン補間は、補間式がスプラインと呼ばれる特殊な区分多項式である補間形式である。つまり、単一の高次多項式をすべての値に一度に当てはめるのではなく、スプライン補間では、値の小さなサブセットに低次多項式を当てはめ、たとえば、10 点のペアすべてに単一の 9 次多項式を当てはめるのではなく、各 10 点のペアの間に 9 つの 3 次多項式を当てはめる。スプライン補間は、スプラインに低次多項式を使用しても補間誤差を小さくできるため、多項式補間よりも好まれることが多い。 ^{[ 1 ]}スプライン補間では、高次多項式を使用して補間するときに点の間で振動が発生する可能性があるルンゲ現象の問題も回避できる。

導入

8点間の3次スプラインによる補間。造船用の手描きの技術図面は、スプライン補間の歴史的な例です。図面は、あらかじめ定義された点に沿って曲げられる柔軟な定規を使用して作成されました。

スプラインとは、もともと、あらかじめ定義された複数の点、つまり結び目を通過するように曲げられる弾性定規を指す用語でした。図に示すように、 これらは造船や建設の技術図面を手作業で作成するために使用されました。

同様の曲線を、一連の数式を用いてモデル化したいと考えています。から までの結び目の列があると仮定します。各結び目のペアと の間には、と が結びついており、 が となります。つまり、から始まりで終わる多項式が存在することになります。 ${\displaystyle n+1}$ ${\displaystyle (x_{0},y_{0})}$ ${\displaystyle (x_{n},y_{n})}$ ${\displaystyle q_{i}(x)=y}$ ${\displaystyle (x_{i-1},y_{i-1})}$ ${\displaystyle (x_{i},y_{i})}$ ${\displaystyle i=1,2,\dots ,n}$ ${\displaystyle n}$ ${\displaystyle (x_{0},y_{0})}$ ${\displaystyle (x_{n},y_{n})}$

あらゆる曲線の曲率は次のように定義される。 ${\displaystyle y=y(x)}$

${\displaystyle \kappa ={\frac {y''}{(1+y'^{2})^{3/2}}},}$

ここで、およびは の に関する1次および2次導関数である。スプラインが（すべての節点を通過するという制約の下で）曲がりを最小にする形状をとるようにするために、 と が節点を含むあらゆる場所で連続であると定義する。各連続多項式は、対応するデータ点のy値に等しい値、導関数、および節点における2次導関数を持つ必要がある。つまり、 ${\displaystyle y'}$ ${\displaystyle y''}$ ${\displaystyle y(x)}$ ${\displaystyle x}$ ${\displaystyle y'}$ ${\displaystyle y''}$

${\displaystyle {\begin{cases}q_{i}(x_{i})=q_{i+1}(x_{i})=y_{i}\\q'_{i}(x_{i})=q'_{i+1}(x_{i})\\q''_{i}(x_{i})=q''_{i+1}(x_{i})\end{cases}}\qquad 1\leq i\leq n-1.}$

これは、3次以上の多項式（3次多項式）を使用した場合にのみ実現できます。古典的なアプローチは、正確に3次多項式、つまり3次スプラインを使用することです。

上記の 3 つの条件に加えて、自然 3 次スプラインには次の条件があります。 ${\displaystyle q''_{1}(x_{0})=q''_{n}(x_{n})=0}$

上記の 3 つの主な条件に加えて、クランプされた 3 次スプラインには、およびという条件があります。ここで、は補間関数の導関数です。 ${\displaystyle q'_{1}(x_{0})=f'(x_{0})}$ ${\displaystyle q'_{n}(x_{n})=f'(x_{n})}$ ${\displaystyle f'(x)}$

上記の3つの主な条件に加えて、ノットのないスプラインには、およびという条件があります。^{[ 2 ]}${\displaystyle q'''_{1}(x_{1})=q'''_{2}(x_{1})}$ ${\displaystyle q'''_{n-1}(x_{n-1})=q'''_{n}(x_{n-1})}$

補間3次スプラインを求めるアルゴリズム

から までの点が与えられたときに、各多項式を求めたいとします。そのために、曲線 の 1 つの部分、つまり から までを補間するものを考えます。この部分の端点は傾きが で、となります。より正確には、 ${\displaystyle q_{i}(x)}$ ${\displaystyle (x_{0},y_{0})}$ ${\displaystyle (x_{n},y_{n})}$ ${\displaystyle q(x)}$ ${\displaystyle (x_{1},y_{1})}$ ${\displaystyle (x_{2},y_{2})}$ ${\displaystyle k_{1}}$ ${\displaystyle k_{2}}$

${\displaystyle q(x_{1})=y_{1},}$

${\displaystyle q(x_{2})=y_{2},}$

${\displaystyle q'(x_{1})=k_{1},}$

${\displaystyle q'(x_{2})=k_{2}.}$

完全な方程式は対称形で書くことができる ${\displaystyle q(x)}$

${\displaystyle q(x)={\big (}1-t(x){\big )}\,y_{1}+t(x)\,y_{2}+t(x){\big (}1-t(x){\big )}{\Big (}{\big (}1-t(x){\big )}\,a+t(x)\,b{\Big )},}$

1

どこ

${\displaystyle t(x)={\frac {x-x_{1}}{x_{2}-x_{1}}},}$

2

${\displaystyle a=k_{1}(x_{2}-x_{1})-(y_{2}-y_{1}),}$

3

${\displaystyle b=-k_{2}(x_{2}-x_{1})+(y_{2}-y_{1}).}$

4

しかし、ととは何でしょうか？これらの臨界値を導くには、次の点を考慮する必要があります。 ${\displaystyle k_{1}}$ ${\displaystyle k_{2}}$

${\displaystyle q'={\frac {dq}{dx}}={\frac {dq}{dt}}{\frac {dt}{dx}}={\frac {dq}{dt}}{\frac {1}{x_{2}-x_{1}}}.}$

すると、

${\displaystyle q'={\frac {y_{2}-y_{1}}{x_{2}-x_{1}}}+(1-2t){\frac {a(1-t)+bt}{x_{2}-x_{1}}}+t(1-t){\frac {b-a}{x_{2}-x_{1}}},}$

5

${\displaystyle q''=2{\frac {b-2a+(a-b)3t}{{(x_{2}-x_{1})}^{2}}}.}$

6

式（５）と式（６ ）でそれぞれt = 0とt = 1と設定すると、式（２）から、確かに１次導関数q′（x ₁）= k ₁とq′（x ₂）= k ₂が得られ、２次導関数も 得られる。

${\displaystyle q''(x_{1})=2{\frac {b-2a}{{(x_{2}-x_{1})}^{2}}},}$

7

${\displaystyle q''(x_{2})=2{\frac {a-2b}{{(x_{2}-x_{1})}^{2}}}.}$

8

もし今( x _i , y _i ) とすると、i = 0, 1, ..., nはn + 1点であり、

${\displaystyle q_{i}=(1-t)\,y_{i-1}+t\,y_{i}+t(1-t){\big (}(1-t)\,a_{i}+t\,b_{i}{\big )},}$

9

ここで、i = 1, 2, ..., n、およびは、 i = 1, ..., nに対してx _{i −1} ≤ x ≤ x _iの区間でy を補間するn個の 3 次多項式であり、 i = 1, ..., n  − 1に対してq′ _i ( x _i ) = q′ _{i +1} ( x _i )が成立する場合、 n個の多項式は、区間x ₀ ≤ x ≤ x _nで微分可能な関数を定義し、 ${\displaystyle t={\tfrac {x-x_{i-1}}{x_{i}-x_{i-1}}}}$

${\displaystyle a_{i}=k_{i-1}(x_{i}-x_{i-1})-(y_{i}-y_{i-1}),}$

10

${\displaystyle b_{i}=-k_{i}(x_{i}-x_{i-1})+(y_{i}-y_{i-1})}$

11

i = 1, ..., n 、ただし

${\displaystyle k_{0}=q_{1}'(x_{0}),}$

12

${\displaystyle k_{i}=q_{i}'(x_{i})=q_{i+1}'(x_{i}),\qquad i=1,\dots ,n-1,}$

13

${\displaystyle k_{n}=q_{n}'(x_{n}).}$

14

シーケンスk ₀、k ₁、 ...、k _nにおいて、さらにi = 1、 ...、n − 1 に対してq′′ _i ( x _i ) = q′′ _{i +1} ( x _i )が成り立つ 場合、結果の関数は連続した 2 次導関数を持ちます。

（ ７），（８），（１０）および（１１ ）から、これが成り立つのは、

${\displaystyle {\frac {k_{i-1}}{x_{i}-x_{i-1}}}+\left({\frac {1}{x_{i}-x_{i-1}}}+{\frac {1}{x_{i+1}-x_{i}}}\right)2k_{i}+{\frac {k_{i+1}}{x_{i+1}-x_{i}}}=3\left({\frac {y_{i}-y_{i-1}}{{(x_{i}-x_{i-1})}^{2}}}+{\frac {y_{i+1}-y_{i}}{{(x_{i+1}-x_{i})}^{2}}}\right)}$

15

i = 1, ..., n − 1である 。関係式（15）は、n + 1個の値k ₀、k ₁、 ..., k _nに対するn − 1個の線形方程式である。

弾性定規をスプライン補間のモデルとすると、左端の「結び目」の左側と右端の「結び目」の右側では定規は自由に動くため、q′′ = 0となる直線の形をとる。q ′′はxの連続関数となるため、 n − 1個の線形方程式（15） に加えて「自然スプライン」は

${\displaystyle q''_{1}(x_{0})=2{\frac {3(y_{1}-y_{0})-(k_{1}+2k_{0})(x_{1}-x_{0})}{{(x_{1}-x_{0})}^{2}}}=0,}$

${\displaystyle q''_{n}(x_{n})=-2{\frac {3(y_{n}-y_{n-1})-(2k_{n}+k_{n-1})(x_{n}-x_{n-1})}{{(x_{n}-x_{n-1})}^{2}}}=0,}$

つまり

${\displaystyle {\frac {2}{x_{1}-x_{0}}}k_{0}+{\frac {1}{x_{1}-x_{0}}}k_{1}=3{\frac {y_{1}-y_{0}}{(x_{1}-x_{0})^{2}}},}$

16

${\displaystyle {\frac {1}{x_{n}-x_{n-1}}}k_{n-1}+{\frac {2}{x_{n}-x_{n-1}}}k_{n}=3{\frac {y_{n}-y_{n-1}}{(x_{n}-x_{n-1})^{2}}}.}$

17

最終的に、（15 ）は（ 16）および（17）とともに、_{n + 1個のパラメータk0} 、 k1、...、kn_を一意に_定義するn + 1個の線形方程式を構成します。

他にも端点条件として、スプラインの端点における傾きを指定する「クランプスプライン」と、 x ₁点とx _{n −1}点における三次導関数が連続であることを要求する「ノットスプライン」があります。「ノットスプライン」の場合、追加の式は以下のようになります。

${\displaystyle q'''_{1}(x_{1})=q'''_{2}(x_{1})\Rightarrow {\frac {1}{\Delta x_{1}^{2}}}k_{0}+\left({\frac {1}{\Delta x_{1}^{2}}}-{\frac {1}{\Delta x_{2}^{2}}}\right)k_{1}-{\frac {1}{\Delta x_{2}^{2}}}k_{2}=2\left({\frac {\Delta y_{1}}{\Delta x_{1}^{3}}}-{\frac {\Delta y_{2}}{\Delta x_{2}^{3}}}\right),}$

${\displaystyle q'''_{n-1}(x_{n-1})=q'''_{n}(x_{n-1})\Rightarrow {\frac {1}{\Delta x_{n-1}^{2}}}k_{n-2}+\left({\frac {1}{\Delta x_{n-1}^{2}}}-{\frac {1}{\Delta x_{n}^{2}}}\right)k_{n-1}-{\frac {1}{\Delta x_{n}^{2}}}k_{n}=2\left({\frac {\Delta y_{n-1}}{\Delta x_{n-1}^{3}}}-{\frac {\Delta y_{n}}{\Delta x_{n}^{3}}}\right),}$

どこ。 ${\displaystyle \Delta x_{i}=x_{i}-x_{i-1},\ \Delta y_{i}=y_{i}-y_{i-1}}$

例

3点間の3次「自然」スプラインによる補間

3点の場合、の値は三重対角線形方程式を解くことによって求められる。${\displaystyle k_{0},k_{1},k_{2}}$

${\displaystyle {\begin{bmatrix}a_{11}&a_{12}&0\\a_{21}&a_{22}&a_{23}\\0&a_{32}&a_{33}\\\end{bmatrix}}{\begin{bmatrix}k_{0}\\k_{1}\\k_{2}\\\end{bmatrix}}={\begin{bmatrix}b_{1}\\b_{2}\\b_{3}\\\end{bmatrix}}}$

と

${\displaystyle a_{11}={\frac {2}{x_{1}-x_{0}}},}$

${\displaystyle a_{12}={\frac {1}{x_{1}-x_{0}}},}$

${\displaystyle a_{21}={\frac {1}{x_{1}-x_{0}}},}$

${\displaystyle a_{22}=2\left({\frac {1}{x_{1}-x_{0}}}+{\frac {1}{x_{2}-x_{1}}}\right),}$

${\displaystyle a_{23}={\frac {1}{x_{2}-x_{1}}},}$

${\displaystyle a_{32}={\frac {1}{x_{2}-x_{1}}},}$

${\displaystyle a_{33}={\frac {2}{x_{2}-x_{1}}},}$

${\displaystyle b_{1}=3{\frac {y_{1}-y_{0}}{(x_{1}-x_{0})^{2}}},}$

${\displaystyle b_{2}=3\left({\frac {y_{1}-y_{0}}{{(x_{1}-x_{0})}^{2}}}+{\frac {y_{2}-y_{1}}{{(x_{2}-x_{1})}^{2}}}\right),}$

${\displaystyle b_{3}=3{\frac {y_{2}-y_{1}}{(x_{2}-x_{1})^{2}}}.}$

3つのポイント

${\displaystyle (-1,0.5),\ (0,0),\ (3,3),}$

それはわかる

${\displaystyle k_{0}=-0.6875,\ k_{1}=-0.1250,\ k_{2}=1.5625,}$

そして（１０）と（１１） から

${\displaystyle a_{1}=k_{0}(x_{1}-x_{0})-(y_{1}-y_{0})=-0.1875,}$

${\displaystyle b_{1}=-k_{1}(x_{1}-x_{0})+(y_{1}-y_{0})=-0.3750,}$

${\displaystyle a_{2}=k_{1}(x_{2}-x_{1})-(y_{2}-y_{1})=-3.3750,}$

${\displaystyle b_{2}=-k_{2}(x_{2}-x_{1})+(y_{2}-y_{1})=-1.6875.}$

図には、2つの3次多項式から成り、( 9 )で与えられるスプライン関数が表示されている。 ${\displaystyle q_{1}(x)}$ ${\displaystyle q_{2}(x)}$

参照

• アキマスプライン
• 円弧補間
• 3次エルミートスプライン
• 求心性Catmull-Romスプライン
• 離散スプライン補間
• 単調な3次補間
• 非一様有理Bスプライン
• 多変量補間
• 多項式補間
• スムージングスプライン
• スプラインウェーブレット
• 薄板スプライン
• 多調和スプライン

参考文献

1. Hall, Charles A.; Meyer, Weston W. (1976). 「3次スプライン補間の最適誤差境界」 . Journal of approximation Theory . 16 (2): 105– 122. doi : 10.1016/0021-9045(76)90040-X .
2. バーデン、リチャード、フェアーズ、ダグラス (2015).数値解析（第10版）. Cengage Learning. pp.  142– 157. ISBN 9781305253667。

さらに読む

• シェーンベルク, アイザック J. (1946). 「解析関数による等距離データの近似問題への貢献：パートA. 平滑化または段階化の問題について。第一級の解析近似公式」 .応用数学季刊誌. 4 (2): 45–99 . doi : 10.1090/qam/15914 .
• シェーンベルク, アイザック J. (1946). 「解析関数による等距離データの近似問題への貢献：パートB. 接触補間の問題について。第二の解析近似公式」 .応用数学季刊. 4 (2): 112– 141. doi : 10.1090/qam/16705 .

外部リンク

• 3次スプライン補間オンライン計算および可視化ツール（JavaScriptソースコード付き）
• 「スプライン補間」、数学百科事典、EMSプレス、2001 [1994]
• JSXGraph を使用した動的 3 次スプライン
• スプライン補間の理論と実践に関する講義
• 等距離ノットのみを対象に、3 次スプライン補間の実行方法を段階的に説明する論文。
• C言語の数値レシピ、第3章セクション3-3へ
• 3次スプラインに関する注意
• スプライン補間に関する情報（Fortran 77のコードを含む）
• TinySpline:3次スプライン補間を実装するオープンソースのスプライン用Cライブラリ
• SciPy スプライン補間:補間を実装するPythonパッケージ
• 3次補間:3次スプライン補間用のオープンソースC#ライブラリ