山本ワールド
Windowsプログラミング
アルゴリズム Vitual C++ 2008/2013によるWin32/Win64 APIレベルのプログラム 基礎 Vitual C++ 2008/2013によるAPIレベルのプログラム(32/64bit) Wix3でインストーラーを作る Visual C++ 2008 Standard Editonによるフォームアプリケーションのプログラム(32/64bit) Vitual C++ 2008 Standard EditonによるAPIレベルのプログラム(32/64bit) Windows 7対応 Visual C++ 2008 ExpressによるAPIレベルのプログラム Visual C++ 2005 ExpressによるAPIレベルのプログラム Visual C++ Versiosn 5 BORLAND C++ Windowsプログラム全般 Excel VBA その他スプライン曲線の計算方法
3次スプライン曲線の作成方法
既知点
下図のように6点の既知点からなる3次スプライン曲線を例に算出方法を説明する。X | Y | ||
---|---|---|---|
0 | 0 | 2041.68 | 1575.59 |
1 | 1 | 2830.84 | 2298.99 |
2 | 2 | 3685.07 | 1900.71 |
3 | 3 | 4191.15 | 1353.67 |
N-1 | 4 | 4889.14 | 1648.74 |
N | 5 | 5403.39 | 2536.84 |
3次スプライン曲線による補間の基本
3次スプライン曲線による補間は、各区間(例えば(x 0,y 0)~ (x 1,y 1)区間など)事に3次方程式の係数 an , bn , cn , dnを算出して描画することである。三次方程式は下式のとおりである。
(xn,yn)~(xn+1),(yn+1)区間 既知点が0からNまでの場合、式はN-1の補間式が作成できる。
今回の6点が既知点の場合
0 (x0,y0)~(x1),(y1)区間
1 (x1,y1)~(x2),(y2)区間
2 (x2,y2)~(x3),(y3)区間
3 (x3,y3)~(x4),(y4)区間
4 (x4,y4)~(x5),(y5)区間
各係数の算定
dnの算定
各区間のスプライン曲線の始終点はすべて既知点を通る。したがって、区間の補間式の両端のxに対するyの値は既知である。各区間の始点側はx=xnなので(x-xn)=0となる。よってbnの算定
隣同士の区間の曲線がスムーズに接続されるには、隣同士の曲線傾きが同一である必要がある。傾きは微分値なので 隣同士の区間の一次導関数、二次導関数の値が同一である必要がある。 とりあえずSn(x)に対する一次・二次導関数を求めるべき乗img alt="f(x)=x^n" class="img2latex">に対する一次導関数は
一次導関数
二次導関数は、一次導関数をさらに微分したものなので、
始点側はx=xnなので(x-xn)=0となる。よって
anの算定
隣同士の二次導関数の値は等しいので、
![S''(x-x_n)=6a_n(x-x_n)+2b_n]()
![\displaystyle a_n=\frac{(S_{n+1}''(x)-2b_n)}{6(x_{n+1}-x_n)}]()
式-3
cnの算定
補間式は、与点を必ず通るので、
![a_n(x-x_n)^3+b_n(x-x_n)^2+c_n(x-x_n)+d_n=y_{n+1}]()
式-1,2,3を代入すると
![\displaystyle \frac{S_{n+1}''(x)-2b_n}{6(x_{n+1}-x_n)}(x_{n+1}-x_n)(x_{n+1}-x_n)^3+\frac{S_n''(x)}{2}(x_{n+1}-x_n)^2+C_n(x_{n+1}-x_n)=Y_n=Y_{n+1}]()
cnについて解くと
![\displaystyle c_n(x_{n+1}-x_n)=Y_{n+1}-Y_n-\frac{S_{n+1}''(x)-S_n''}{6(x_{n+1}-x_n)}(x_{n+1}-x_n)(x_{n+1}-x_n)^3+\frac{S_n''(x)}{2}(x_{n+1}-x_n)^2]()
![\displaystyle c_n=\frac{Y_{n+1}-Y_n-\frac{S_{n+1}''(x)-S_n''}{6(x_{n+1}-x_n)}(x_{n+1}-x_n)(x_{n+1}-x_n)^3+\frac{S_n''(x)}{2}(x_{n+1}-x_n)^2}{x_{n+1}-x_n}]()
![\displaystyle c_n=\frac{Y_{n+1}-Y_n}{x_{n+1}-x_n}-\frac{(S_{n+1}''(x)-S_n''(x))(x_{n+1}-x_n)^2}{6(x_{n+1}-x_n)} -\frac{S_n''(x)(x_{n+1}-x_n)}{2}]()
上記式の一部を整理するために下式の簡略化をする
![\displaystyle -\frac{(S_1-S)(x_1-x)}{6}-\frac{S (x_1-x)}{6}]()
展開すると
![\displaystyle -\frac{S_1x_1}{6}-\frac{S \dot x_1}{3}+\frac{S_1x_1}{6}+\frac{S \cdot x}{3}]()
整理すると
![\displaystyle \frac{-S_1x_1-2S \cdot x_1+2S_1 \cdot x}{6}]()
より
![\displaystyle -\frac{1}{6}(x_1-x)(2S+S_1)]()
整理結果をもとの式に反映させる
![\displaystyle c_n=\frac{Y_{n+1}-Y_n}{X_{n+1}-x_n}-\frac{1}{6}(x_{n+1}-x_n)(2S_n''(x)+2S_{n+1}''(x))]()
二次導関数の算出
隣同士の一次導関数の値は一致する必要があるので
![S_n'(x_{n+1})=S_{n+1}''(x_{n+1})]()
一次導関数は
![S_n'(x-x_{n+1})=3a_n(x-x_n)^2+2b_n(x-x_n)+c_n]()
xn+1の時 x-xnは0となるので、
![3a_n'(x_{n+1}-x_n)^2+2b_n(x_n-x_n)+c_n]()
上記式に an,bn,cnの式を代入する。
![\displaystyle a_n=\frac{S_{n+1}''(x_n)-S_n''(x_n)}{6(x_{n+1}-x_n)}]()
![\displaystyle b_n=\frac{S_n''(x_n)}{2}]()
![\displaystyle c_n=\frac{(y_{n+1}-y_n)}{(x_{n+1}-x_n)}-\frac{1}{6}(x_{n+1}-x_n)(2S_n''(x_n)+S_{n+1}''(x_n))]()
![\displaystyle c_{n+1}=\frac{(y_{n+2}-y_{n+1})}{(x_{n+2}-x_{n+1})}-\frac{1}{6}(x_{n+2}-x_{n+1})(2S_n''(x_{n+1})+S_{n+2}''(x_n))]()
![\displaystyle 3 (\frac{S_{n+1}''(x_n)-S_n''(x_n)}{6(x_{n+1}-x_n)})(x_{n+1}-x_n)^2+2(\frac{S_n''(x_n)}{2})(x_{n+1}-x_n)]()
![\displaystyle +\left\{ \frac{(y_{n+1}-y_n)}{(x_{n+1}-x_n)}-\frac{1}{6}(x_{n+1}-x_n)(2S_n''(x_n)+S_{n+1}''(x_n)) \right\}=]()
![\displaystyle \frac{(y_{n+2}-y_{n+1})}{(x_{n+2}-x_{n+1})}-\frac{1}{6}(x_{n+2}-x_{n+1})(2S_{n+1}''(x_{n+1})+S_{n+2}''(x_n))]()
Sn" Sn+1" Sn+2"を式の左側に移行する。
![\displaystyle \frac{S_{n+1}''(x_n)-S_n''(x_n)}{2}(x_{n+1}-x_n)+S_n''(x_n)(x_{n+1}-x_n)-\frac{1}{6}(x_{n+1}-x_n)(2S_n''(x_n)+S_{n+1}''(x_n))]()
![\displaystyle +\frac{1}{6}(x_{n+2}-x_{n+1})(2S_{n+1}''(x_{n+1}) +S_{n+2}''(X_n))=\frac{(y_{n+2}-y_{n+1})}{(x_{n+2}-x_{n+1})}-\frac{(y_{n+1}-y_n)}{(x_{n+1}-x_n)}]()
式を分解する
![\displaystyle \frac{S_{n+1}''(x_n)}{2}(x_{n+1}-x_n)-S_n''(x_n)(x_{n+1}-x_n)-\frac{1}{3}(x_{n+1}-x_n)S_n''(x_n)]()
![\displaystyle -\frac{1}{6}(x_{n+1}-x_n)S_{n+1}''(x_n)+\frac{1}{3}(x_{n+2}-x_{n+1})S_{n+1}''(x_{n+1})]()
![\displaystyle +\frac{1}{6}(x_{n+2}-x_{n+1})S_{n+2}''(x_n)=\frac{(y_{n+2}-y_{n+1}}{(x_{n+2}-x_{n+1})}-\frac{(y_{n+1}-y_n)}{(x_{n+1}-x_n)}]()
式を整理する
![\displaystyle S_n''(x_n) \left\{ - \frac{(x_{n+1}-x_n) }{2}+(x_{n+1}-x_n)-\frac{1}{3}(x_{n+1}-x_n) \right\}]()
![\displaystyle S_{n+1}''(x_n) \left\{ - \frac{1}{2}(x_{n+1}-x_n)-\frac{1}{6}(x_{n+1}-x_n)-\frac{1}{3}(x_{n+2}-x_{n+1}) \right\}+\frac{1}{6}(x_{n+2}-x_{n+1})S_{n+2}''(x_n)=]()
![\displaystyle \frac{(y_{n+2}-y_{n+1})}{(x_{n+2}-x_{n+1})}-\frac{(y_{n+1}-y_n)}{(x_{n+1}-x_n)}]()
![\displaystyle S_n''(x_n) \frac{(x_{n+1}-x_n)}{6}+S_{n+1}''(x_n) \left\{ \frac{1}{3}(x_{n+2}-x_{n+1}) \right\}]()
![\displaystyle +\frac{1}{6}(x_{n+2}-x_{n+1})S_{n+2}''(x_n)=\frac{(y_{n+2}-y_{n+1})}{x_{n+2}-x_{n+1}}-\frac{(y_{n+1}-y_n)}{(x_{n+1}-x_n)}]()
式を6倍する
![\displaystyle (x_{n+1}-x_n)Sn''(x_n)+2(x_{n+2}-x_{n+1})S_{n+1}''(x_n)+(x_{n+2}-x_{n+1})S_{n+2}''(x_n)=6 \left\{ \frac{(y_{n+2}-y_{n+1})}{(x_{n+2}-x_{n+1})}-\frac{(y_{n+1}-y_n)}{(x_{n+1}-x_n)} \right\}]()
各区間の二次導関数について連立方程式を作成する。
今回の6点が既知点の場. 0 (x0,y0)~(x1),(y1)区間
n=0
![\displaystyle (x_{n+1}-x_n)Sn''(x_n)+2(x_{n+2}-x_{n+1})S_{n+1}''(x_n)+(x_{n+2}-x_{n+1})S_{n+2}''(x_n)=6 \left\{ \frac{(y_{n+2}-y_{n+1})}{(x_{n+2}-x_{n+1})}-\frac{(y_{n+1}-y_n)}{(x_{n+1}-x_n)} \right\}]()
1 (x1,y1)~(x2),(y2)区間
n=1
![\displaystyle (x_{n+1}-x_n)Sn''(x_n)+2(x_{n+2}-x_{n+1})S_{n+1}''(x_n)+(x_{n+2}-x_{n+1})S_{n+2}''(x_n)=6 \left\{ \frac{(y_{n+2}-y_{n+1})}{(x_{n+2}-x_{n+1})}-\frac{(y_{n+1}-y_n)}{(x_{n+1}-x_n)} \right\}]()
2 (x2,y2)~(x3),(y3)区間
n=2
![\displaystyle (x_{n+1}-x_n)Sn''(x_n)+2(x_{n+2}-x_{n+1})S_{n+1}''(x_n)+(x_{n+2}-x_{n+1})S_{n+2}''(x_n)=6 \left\{ \frac{(y_{n+2}-y_{n+1})}{(x_{n+2}-x_{n+1})}-\frac{(y_{n+1}-y_n)}{(x_{n+1}-x_n)} \right\}]()
3 (x3,y3)~(x4),(y4)区間
n=3
![\displaystyle (x_{n+1}-x_n)Sn''(x_n)+2(x_{n+2}-x_{n+1})S_{n+1}''(x_n)+(x_{n+2}-x_{n+1})S_{n+2}''(x_n)=6 \left\{ \frac{(y_{n+2}-y_{n+1})}{(x_{n+2}-x_{n+1})}-\frac{(y_{n+1}-y_n)}{(x_{n+1}-x_n)} \right\}]()
4 (x4,y4)~(x5),(y5)区間
n=4
![\displaystyle (x_{n+1}-x_n)Sn''(x_n)+2(x_{n+2}-x_{n+1})S_{n+1}''(x_n)+(x_{n+2}-x_{n+1})S_{n+2}''(x_n)=6 \left\{ \frac{(y_{n+2}-y_{n+1})}{(x_{n+2}-x_{n+1})}-\frac{(y_{n+1}-y_n)}{(x_{n+1}-x_n)} \right\}]()
一般的に表すと0~Nまでの既知点がある場合
0~N-2について下記式の連立方程式が成り立つ。
![\displaystyle (x_{n+1}-x_n)Sn''(x_n)+2(x_{n+2}-x_{n+1})S_{n+1}''(x_n)+(x_{n+2}-x_{n+1})S_{n+2}''(x_n)=6 \left\{ \frac{(y_{n+2}-y_{n+1})}{(x_{n+2}-x_{n+1})}-\frac{(y_{n+1}-y_n)}{(x_{n+1}-x_n)} \right\}]()
なお、S0"(x)=SN-1"(x)=0とする。(自然スプライン)
式を簡素化するために下式とおく。
![h_n=x_{n+1}-x_n]()
![h_{n+1}-h_n=x_{n+2}-x_{n+1}+x_{n+1}-x_n=x_{n+2}-x_n]()
![\displaystyle k_n=6 \left\{ \frac{y_{n+1}-y_n}{h_n}-\frac{y_n-y_{n-1}}{h_{n-1}} \right\}]()
![2(h_1+h_0)s_1''+h_1S_2''=k_1]()
![h_1S_1''+2(h_2+h_1)S_2''+h_2S_3''=K_2]()
![h_2S_2''+2(h_3+h_2)S_3''=K_2]()
より一般的な表記をすると0~N-2について下記式の連立方程式が成り立つ。
n=0の時 ![2(h_1+h_0)s_1''+h_1S_2''=k_1]()
n=1~N-4 ![h_nS_n''+2(h_{n+1}+h_n)S_{n+1}''+h_{n+1}S_{n+2}''=K_{n+1}]()
n=N-3![h_{N-3}S_{N-3}''+2(h_{N-2}+h_{N-3})S_{N-2}''=K_{N-3}]()
例えば2つ変数がある連立方程式を行列表記すると下式となる。
![3x-4y=-5]()
![2x+y=4]()
![\left[ \begin{matrix} 3 & -4 \\ 2 & 1 \\ \end{matrix} \right] \left[ \begin{matrix} x \\ y \\ \end{matrix} \right]=\left[ \begin{matrix} -5 \\ 4 \\ \end{matrix} \right]]()
解き方はいろいろあるがここではクラメールの公式の例とガウスの消去法を示す。
連立方式を行列で示すと下式のとおりとなる。
![\left[ \begin{matrix} S_1'' \\ S_2'' \\ S_3'' \\ \end{matrix} \right]=\left[ \begin{matrix} k_1 \\ k_2 \\ k_3 \\\end{matrix} \right]]()
クラメール
![\left[ \begin{matrix} a_{11} & a_{12} \\ a_{21} & a_{22} \\ \end{matrix} \right] \left[ \begin{matrix} x \\ y \\\end{matrix} \right]=\left[ \begin{matrix} b_1 \\ b_2 \\\end{matrix} \right]]()
![\displaystyle y=\frac{ \left| \begin{matrix} a_{11} & b_1 \\ a_{21} & b_2 \\ \end{matrix} \right| }{ \left| \begin{matrix} a_{12} & a_{12} \\ a_{22} & a_{22} \\ \end{matrix} \right| }]()
なお、||は絶対値ではなく、行列の値を求めるという意味である。例えば 2次の正方行列の場.、下式で解を求めることができる。
![\displaystyle \left| \begin{matrix} a_{11} & b_1 \\ a_{21} & b_2 \\ \end{matrix} \right|=a_{11}a_{22}-a_{12}a_{21}]()
3次の正方行列の場.サラスの方法により求めることができる。 4次以上については各種方法がある。また、行列の値は、Excelおよびmaximax等で求めることができる。
Excelの場合、MDETERM関数を用いる
![\displaystyle S_1''=\frac{ \left| \begin{matrix} k_1 & h_1 & 0 \\ k_2 & 2(h_2+h_1) & h_2 \\ k_3 & h_2 & 2(h_3+h_2) \\ \end{matrix} \right| }{ \left| \begin{matrix} 2(h_1+h_0) & h_1 & 0 \\ h_1 & 2(h_2+h_1) & h_2 \\ 0 & h_2 & 2(h_3+h_2) \\ \end{matrix} \right| }]()
![\displaystyle S_2''=\frac{ \left| \begin{matrix} 2(h_1+h_0) & k_1 & 0 \\ h_1 & k_2 & h_2 \\ 0 & k_3 & 2(h_3+h_2) \\ \end{matrix} \right| }{ \left| \begin{matrix} 2(h_1+h_0) & h_1 & 0 \\ h_1 & 2(h_2+h_1) & h_2 \\ 0 & h_2 & 2(h_3+h_2) \\ \end{matrix} \right| }]()
![\displaystyle S_3''=\frac{ \left| \begin{matrix} 2(h_1+h_0) & h_1 & k_1 \\ h_1 & 2(h_2+h_1) & k_2 \\ 0 & h_2 & k_3 \\ \end{matrix} \right| }{ \left| \begin{matrix} 2(h_1+h_0) & h_1 & 0 \\ h_1 & 2(h_2+h_1) & h_2 \\ 0 & h_2 & 2(h_3+h_2) \\ \end{matrix} \right| }]()
各hn、knを算定する。
![h_n=x_{n+1}-x_n]()
![\displaystyle k_n=6 \left( \frac{y_{n+1}-y_n}{h_n}-\frac{y_{n+1}-y_n}{h_n} \right)]()
n | x | y | hn | kn |
---|---|---|---|---|
0 | 2041.68 | 1575.59 | 789.16 | |
1 | 2830.84 | 2298.99 | 854.23 | -8.297492068 |
2 | 3685.07 | 1900.71 | 506.08 | -3.688148198 |
3 | 4191.15 | 1353.67 | 697.99 | 9.0220696 |
4 | 4889.14 | 1648.74 | 514.25 | 7.825431565 |
5 | 5403.39 | 2536.84 |
" 計算されたhn,knを代入する
ガウスの消去法
ガウスの前進消去法を用いて上三角行列を作成する。
上記の行列2列目以降に下式を適用する。
ui1=ai1/a11
aji = aji - ui1 * a1j
bi=bi-ui1*b1
式が複雑なので適用結果をaij'と置く
更に3行目2列目以降の行に下式を適用する
ui2'=ai2'/a22'
aij'=aji'-ui2*a2j' bi=bi-ui1*bi
適用結果を整理すると下式となる
以下、行がなくなるまで、順番に行と列を移動しながら適用していく。
上三角行列ができるので、左上から右下方向の対角線上の値を掛けていくと行列の値が算出できる。
a11'*a22'*a33'=a33'-ui2'*a23'
前進消去で行列式を上三角行列に変換する。
1 2 3 kn 1 3286.78 854.23 0 -8.2974921 2 854.23 2720.62 506.08 -3.6881482 3 0 506.08 2408.14 9.0220696ui1=ai1/a11
aji = aji - ui1 * a1j
bi=bi-ui1*b1
1 2 3 ui1 1 3286.78 854.23 0 -8.2974921 2 0 2498.606694 506.08 -1.5316404 0.259898746 3 0 506.08 2408.14 9.0220696 0aij'=aji'-ui2*a2j' bi=bi-ui1*bi
1 2 3 kn ui2'=ai2'/a22' 1 3286.78 854.23 0 -8.2974921 2 0 2498.606694 506.08 -1.5316404 3 0 0 2305.636086 9.33229553 0.202544883後退代入
S1"~S3"の値より an,bn,cn,dnを算定する。
x y Sn" a b c d 0 2041.68 1575.59 0 -4.54516E-07 0 1.199731674 1575.59 1 2830.84 2298.99 -0.002152117 1.4034E-07 -0.0010761 0.350549323 2298.99 2 3685.07 1900.71 -0.001432819 1.80486E-06 -0.0007164 -1.180630528 1900.71 3 4191.15 1353.67 0.004047601 -9.6649E-07 0.0020238 -0.518985955 1353.67 4 4889.14 1648.74 0 0 0 1.72698104 1648.74 5 5403.39 2536.84xを変化させながら、an,bn,cn,dnより補間値yを算出する。
各区間のxを4分割して補間すると下表のとおりとなる。
x y Sn" a b c d 0 2041.68 1575.59 0 -4.54516E-07 0 1.199731674 1575.59 -4.54516E-07 0 1.199731674 1575.59 -4.54516E-07 0 1.199731674 1575.59 1 2830.84 2298.99 -0.002152117 1.4034E-07 -0.0010761 0.350549323 2298.99 1.4034E-07 -0.0010761 0.350549323 2298.99 1.4034E-07 -0.0010761 0.350549323 2298.99 2 3685.07 1900.71 -0.001432819 1.80486E-06 -0.0007164 -1.180630528 1900.71 1.80486E-06 -0.0007164 -1.180630528 1900.71 1.80486E-06 -0.0007164 -1.180630528 1900.71 3 4191.15 1353.67 0.004047601 -9.6649E-07 0.0020238 -0.518985955 1353.67 -9.6649E-07 0.0020238 -0.518985955 1353.67 -9.6649E-07 0.0020238 -0.518985955 1353.67 4 4889.14 1648.74 0 0 0 1.72698104 1648.74 0 0 1.72698104 1648.74 0 0 1.72698104 1648.74 5 5403.39 2536.84
x-xn x x-xn yn 0 2041.68 1575.59 2238.97 197.29 1808.794746 2436.26 394.58 2021.057593 2633.55 591.87 2191.436644 1 789.16 2830.84 2298.99 3044.3975 213.5575 2326.143715 3257.955 427.115 2263.34747 3471.5125 640.6725 2118.80249 2 854.23 3685.07 1900.71 3811.59 126.52 1743.524121 3938.11 253.04 1585.334364 4064.63 379.56 1448.072425 3 506.08 4191.15 1353.67 4365.6475 174.4975 1319.596429 4540.145 348.995 1377.958061 4714.6425 523.4925 1497.943163 4 697.99 4889.14 1648.74 5017.7025 128.5625 1870.765 5146.265 257.125 2092.79 5274.8275 385.6875 2314.815 5 514.25 5403.39 2536.84補間結果をグラフに表した結果が下図のとおりである。
Copyright (C) 2012 山本ワールド All Rights Reserved.