スプライン補間

同義語:spline interpolationスプライン関数スプラインspline3次スプライン3次スプライン補間cubic spline自然スプラインnatural spline完全スプライン周期スプライン

概要

スプライン補間(spline interpolation)とは、節点の間ごとに低い次数の多項式を置き、節点でなめらかにつないでデータを補間する方法である。標準の 3 次スプラインは、節点での $2$ 階導関数の値を未知数とする三重対角の連立方程式を解いて求める。自然・完全・周期・not-a-knot の端の条件で解はただ 1 つで、自然スプラインは $\int g''^2$ を最小にし、完全スプラインの誤差は $h^4$ の定数倍で抑えられる。高次の多項式補間の振動を避ける道具として、データの補間や曲線の表現に使う。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: Newton補間, 部分積分, LU分解

$f(x)=1/(1+25x^2)$ を $[-1,1]$ の等間隔の $11$ 点で補間する。10 次の補間多項式は区間の端の近くで大きく振動し、最大誤差は約 $1.9$ になる(Runge現象)。点を増やすと悪化する。そこで次数を上げるのをやめ、隣り合う点の間ごとに低い次数の多項式を置いて、なめらかにつなぐ。3 次式を $2$ 階導関数まで連続につないだものが 3 次スプライン で、同じ $11$ 点での最大誤差は約 $0.022$ である。点を増やすと誤差は減り続ける。
スプライン補間の計算は、節点での $2$ 階導関数の値を未知数にとると、三重対角 の連立 1 次方程式に帰着する。方程式は対角成分が大きい形をしているので、解はただ 1 つで、点の個数に比例する手間で解ける。この記事では、公式の導出と解の一意性、自然スプラインの最小性、誤差の評価、端の条件の選び方、例題を扱う。

定義と使える条件

$a=x_0< x_1< \cdots< x_n=b$($n\ge1$)を 節点 とし、$I_i:=[x_{i-1},x_i]$、$h_i:=x_i-x_{i-1}$、$h:=\max_ih_i$ とおく。

スプライン関数

$k\ge1$ とする。関数 $S\colon[a,b]\to\mathbb R$ が節点 $x_0,\dots,x_n$ の 次数 $k$ のスプライン であるとは、各 $I_i$ の上で $S$ が次数 $k$ 以下の多項式に等しく、$S$ が $[a,b]$ で $C^{k-1}$ 級であることをいう。$k=3$ のものを 3 次スプライン という。$y_0,\dots,y_n$ に対し $S(x_i)=y_i$($i=0,\dots,n$)を満たすとき、$S$ はデータを 補間する という。

$k=1$ は節点を結ぶ折れ線である。一般の定義は ESL17 §5.2(p. 144)、3 次スプラインの定義は DB22 Definition 5.3.1 にある。3 次スプラインの自由度は次のように数えられる。

3 次スプラインの空間の次元

節点 $x_0,\dots,x_n$ の 3 次スプラインの全体は $n+3$ 次元のベクトル空間で、$1,x,x^2,x^3$ と $(x-x_i)_+^3$($i=1,\dots,n-1$)が基底である。ここで $t_+:=\max(t,0)$ である。

要点:節点を 1 つ越えるごとに、$C^2$ 級の条件で残る自由度が $x^3$ の跳びの 1 つだけになる。

詳しい証明を開く

挙げた関数はどれも 3 次スプラインである。$S$ を 3 次スプラインとし、$I_1$ での多項式を $q$ とする。$I_2$ での多項式と $q$ の差は、$x_1$ で値・$1$ 階・$2$ 階の導関数が $0$ なので $c_1(x-x_1)^3$ の形である。$S-q-c_1(x-x_1)_+^3$ は $I_1\cup I_2$ で $0$ で、同じ議論を $x_2,\dots,x_{n-1}$ で繰り返すと $S$ は挙げた関数の線形結合になる。線形独立性:線形結合が $0$ なら、$I_1$ で見て多項式の部分の係数が $0$ で、$x_1$ での $3$ 階導関数の跳びから $(x-x_1)_+^3$ の係数が $0$、以下同様である。$\square$

補間の条件は $n+1$ 個なので、条件が 2 つ足りない。この 2 つを端の条件で補う。

名前端の条件使う場面
自然スプライン$S''(a)=S''(b)=0$端の情報がないとき。ただし端で精度が落ちる
完全スプライン$S'(a)=A$、$S'(b)=B$端の傾きが分かるとき
周期スプライン$y_0=y_n$、$S'(a)=S'(b)$、$S''(a)=S''(b)$周期関数
not-a-knot 条件$S'''$ が $x_1$ と $x_{n-1}$ で連続端の情報がなく精度が欲しいとき。$n\ge3$

スプライン補間を使う条件は次のとおりである。

  • (i) 節点は相異なり、昇順に並べる。
  • (ii) 値 $y_i$ のほかに、端の条件を 2 つ決める。周期スプラインでは $y_0=y_n$ が要る。
  • (iii) 誤差の評価 thm-spl-error は、$f$ が $C^4$ 級で端の傾きが正確なことを使う。

公式の表

$M_i:=S''(x_i)$ を モーメント とよび、$\delta_i:=(y_i-y_{i-1})/h_i$ とおく。

区間ごとの式

$x\in I_i$ のとき
$$ S(x)=\frac{M_{i-1}(x_i-x)^3+M_i(x-x_{i-1})^3}{6h_i}+\Bigl(\frac{y_{i-1}}{h_i}-\frac{M_{i-1}h_i}6\Bigr)(x_i-x)+\Bigl(\frac{y_i}{h_i}-\frac{M_ih_i}6\Bigr)(x-x_{i-1}). $$

モーメントの方程式

$i=1,\dots,n-1$ について
$$ h_iM_{i-1}+2(h_i+h_{i+1})M_i+h_{i+1}M_{i+1}=6(\delta_{i+1}-\delta_i). $$

この 2 つの式と端の条件をまとめると次の表になる。

公式使える条件根拠
fml-spl-piece と fml-spl-tri節点が相異なるthm-spl-main
$M_{i-1}+4M_i+M_{i+1}=\dfrac{6(y_{i-1}-2y_i+y_{i+1})}{h^2}$等間隔thm-spl-main
$M_0=M_n=0$自然定義
$2M_0+M_1=\dfrac{6(\delta_1-A)}{h_1}$、$M_{n-1}+2M_n=\dfrac{6(B-\delta_n)}{h_n}$完全thm-spl-main
$h_nM_{n-1}+2(h_n+h_1)M_0+h_1M_1=6(\delta_1-\delta_n)$、$M_n=M_0$周期thm-spl-main
$\dfrac{M_1-M_0}{h_1}=\dfrac{M_2-M_1}{h_2}$、$\dfrac{M_{n-1}-M_{n-2}}{h_{n-1}}=\dfrac{M_n-M_{n-1}}{h_n}$not-a-knotthm-spl-main
$\int_a^bg''^2\ge\int_a^bS''^2$$g$ が同じデータを補間する $C^2$ 級の関数、$S$ は自然thm-spl-minimal
$\lvert f-S\rvert\le\frac7{64}Lh^4$、$L=\max\lvert f''''\rvert$$f\in C^4$、完全スプラインthm-spl-error

主定理と証明

三重対角の方程式と解の一意性

未知数の数と式の数が同じ方程式の解の一意性には、次の評価を使う。

優対角な方程式の解の大きさ

$A=(a_{ij})$ を $N$ 次の実正方行列とし、ある $m>0$ についてすべての $i$ で $\lvert a_{ii}\rvert-\sum_{j\ne i}\lvert a_{ij}\rvert\ge m$ とする。このとき $Au=r$ の解 $u$ は $\max_i\lvert u_i\rvert\le\frac1m\max_i\lvert r_i\rvert$ を満たす。とくに $A$ は正則である。

$\lvert u_p\rvert=\max_i\lvert u_i\rvert$ とする。第 $p$ 行から $\lvert a_{pp}\rvert\lvert u_p\rvert\le\lvert r_p\rvert+\sum_{j\ne p}\lvert a_{pj}\rvert\lvert u_p\rvert$ なので、$m\lvert u_p\rvert\le\lvert r_p\rvert$ である。$r=0$ なら $u=0$ なので $A$ は正則である。$\square$

3 次スプラインの方程式

節点 $x_0,\dots,x_n$ と値 $y_0,\dots,y_n$ を与える。

  1. 実数 $M_0,\dots,M_n$ に対し、次の 2 つは同値である:(a) $S$ はデータを補間する 3 次スプラインで $S''(x_i)=M_i$ である。(b) $S$ は各 $I_i$ で fml-spl-piece で与えられ、$M_i$ は fml-spl-tri を満たす。
  2. 自然スプライン($n\ge1$)、完全スプライン($n\ge1$)、周期スプライン($n\ge2$、$y_0=y_n$)、not-a-knot 条件のスプライン($n\ge3$)は、どれもただ 1 つ存在する。

1 の (a) から (b)。 $S''$ は $I_i$ で 1 次以下なので
$$ S''(x)=\frac{M_{i-1}(x_i-x)+M_i(x-x_{i-1})}{h_i}\qquad(x\in I_i) $$
である。2 回積分すると、$S$ は fml-spl-piece の 3 次の項に $x$ の 1 次式を足したものになる。その 1 次式は $S(x_{i-1})=y_{i-1}$、$S(x_i)=y_i$ で決まり、fml-spl-piece になる。
fml-spl-piece を微分して節点の値を入れると、$I_i$ の右端と $I_{i+1}$ の左端で
$$ S'(x_i^-)=\delta_i+\frac{h_i(M_{i-1}+2M_i)}6,\qquad S'(x_i^+)=\delta_{i+1}-\frac{h_{i+1}(2M_i+M_{i+1})}6 $$
となる。$S'$ が $x_i$ で連続であることは、この 2 つが等しいこと、すなわち fml-spl-tri である。
1 の (b) から (a)。 fml-spl-piece で定めると、$x=x_{i-1}$ で $\frac{M_{i-1}h_i^2}6+y_{i-1}-\frac{M_{i-1}h_i^2}6=y_{i-1}$、$x=x_i$ でも同様に $y_i$ となる。$S''$ は上の式で与えられるので、節点で値 $M_i$ をとり連続である。$S'$ の連続性は上の計算で fml-spl-tri と同値である。
2。 fml-spl-tri を $h_i+h_{i+1}$ で割り、$\mu_i:=\frac{h_i}{h_i+h_{i+1}}$、$\lambda_i:=\frac{h_{i+1}}{h_i+h_{i+1}}$、$d_i:=\frac{6(\delta_{i+1}-\delta_i)}{h_i+h_{i+1}}$ とおくと
$$ \mu_iM_{i-1}+2M_i+\lambda_iM_{i+1}=d_i,\qquad\mu_i+\lambda_i=1 $$
となる。対角成分 $2$ に対し、非対角成分の絶対値の和は $1$ である。1 により、端の条件ごとに、未知数と式の数が同じ方程式が lem-spl-dd の仮定を $m=1$ で満たすことを見ればよい。

  • 自然:$M_0=M_n=0$ を入れると、$M_1,\dots,M_{n-1}$ の方程式になる。
  • 完全:$S'(a)=\delta_1-\frac{h_1(2M_0+M_1)}6$、$S'(b)=\delta_n+\frac{h_n(M_{n-1}+2M_n)}6$ より、$2M_0+M_1=6(\delta_1-A)/h_1$、$M_{n-1}+2M_n=6(B-\delta_n)/h_n$ を得る。対角は $2$、非対角は $1$ である。
  • 周期:$M_n=M_0$ とし、$S'(a)=S'(b)$ は $\frac{h_n}{h_n+h_1}M_{n-1}+2M_0+\frac{h_1}{h_n+h_1}M_1=\frac{6(\delta_1-\delta_n)}{h_n+h_1}$ と同じである。未知数は $M_0,\dots,M_{n-1}$ で、$M_n$ は $M_0$ に読み替える。
  • not-a-knot:$S'''$ は $I_i$ で定数 $(M_i-M_{i-1})/h_i$ なので、条件は $(M_1-M_0)/h_1=(M_2-M_1)/h_2$ とその右端の式である。$r:=h_1/h_2$ とすると 1 つ目は $M_0=(1+r)M_1-rM_2$ で、$i=1$ の式に入れて $\mu_1(1+r)=r$、$\lambda_1-\mu_1r=1-r$ を使うと $(2+r)M_1+(1-r)M_2=d_1$ となる。$(2+r)-\lvert1-r\rvert\ge(2+r)-(1+r)=1$ である。右端も、$s:=h_n/h_{n-1}$ として $(1-s)M_{n-2}+(2+s)M_{n-1}=d_{n-1}$ となる。
    どの場合も解 $M$ がただ 1 つ定まり、1 によりスプラインがただ 1 つ定まる。$\square$

$n=3$ の not-a-knot のスプラインは $x_1,x_2$ で $S'''$ が連続なので、1 つの 3 次式であり、4 点の補間多項式に等しい(ex-spl-four)。

自然スプラインの最小性

$\int_a^bg''^2$ は、グラフの傾きが小さいときの曲線の曲がり具合(曲率(曲線) の 2 乗の積分)の近似である。次の定理は、3 次スプラインがこの量を最小にすることを述べる。

自然スプラインの最小性

$S$ をデータを補間する自然スプラインとし、$g\in C^2([a,b])$ を $g(x_i)=y_i$($i=0,\dots,n$)を満たす関数とする。このとき
$$ \int_a^bg''(x)^2\,dx=\int_a^bS''(x)^2\,dx+\int_a^b\bigl(g''(x)-S''(x)\bigr)^2\,dx $$
である。したがって $\int_a^bg''^2\ge\int_a^bS''^2$ で、等号は $g=S$ のときに限る。$S$ が完全スプラインで $g'(a)=A$、$g'(b)=B$ のときも同じである。

$e:=g-S$ とおく。$e$ は $C^2$ 級で、$e(x_i)=0$ である。$g''=S''+e''$ を 2 乗して積分すると、示すべきことは $\int_a^bS''e''=0$ である。部分積分 により
$$ \int_a^bS''e''\,dx=\bigl[S''e'\bigr]_a^b-\sum_{i=1}^n\int_{I_i}S'''e'\,dx $$
である($S''$ は連続で $I_i$ ごとに $C^1$ 級なので、区間ごとの部分積分を足し合わせた)。$S'''$ は $I_i$ で定数 $c_i$ なので、$\int_{I_i}S'''e'=c_i\bigl(e(x_i)-e(x_{i-1})\bigr)=0$ である。第 1 項は、自然スプラインなら $S''(a)=S''(b)=0$ により、完全スプラインなら $e'(a)=e'(b)=0$ により $0$ である。
等号が成り立つと $e''=0$ なので $e$ は 1 次以下で、$e(a)=e(b)=0$ より $e=0$ である。$\square$

この定理は、$\sum_i(y_i-f(x_i))^2+\lambda\int f''^2$ を最小にする関数が節点 $x_i$ の自然スプラインであること(平滑化スプライン の定理「平滑化スプラインの存在と一意性」。ESL17 §5.4、p. 151 と Ex. 5.7、pp. 183–184)の基礎でもある。

誤差の評価

端の傾きが正確な完全スプラインは、$h$ の $4$ 乗の精度をもつ。証明は、モーメントが $f''$ の値に近いことを、三重対角の方程式から直接示す。

完全スプラインの誤差

$f\in C^4([a,b])$、$L:=\max_{[a,b]}\lvert f''''\rvert$ とし、$S$ を $y_i=f(x_i)$、$A=f'(a)$、$B=f'(b)$ の完全スプラインとする。節点の間隔は等しくなくてよい。このとき $[a,b]$ の上で
$$ \lvert f''-S''\rvert\le\frac78Lh^2,\qquad\lvert f'-S'\rvert\le\frac78Lh^3,\qquad\lvert f-S\rvert\le\frac7{64}Lh^4 $$
である。

ステップ 1:残差の評価。 $F_i:=f''(x_i)$ とし、$r_i:=\mu_iF_{i-1}+2F_i+\lambda_iF_{i+1}-d_i$($0< i< n$)とおく。$l:=h_i$、$k:=h_{i+1}$ とし、$x_i$ のまわりで Taylor 展開する(以下 $f,f',\dots$ は $x_i$ での値、$\alpha,\beta,\gamma,\varepsilon$ は $f''''$ の値で、絶対値は $L$ 以下である)。
$$ \delta_{i+1}=f'+\frac k2f''+\frac{k^2}6f'''+\frac{k^3}{24}\alpha,\qquad\delta_i=f'-\frac l2f''+\frac{l^2}6f'''-\frac{l^3}{24}\beta $$
より $d_i=3f''+(k-l)f'''+\dfrac{k^3\alpha+l^3\beta}{4(k+l)}$ である。また $F_{i+1}=f''+kf'''+\frac{k^2}2\gamma$、$F_{i-1}=f''-lf'''+\frac{l^2}2\varepsilon$ より
$$ \mu_iF_{i-1}+2F_i+\lambda_iF_{i+1}=3f''+(k-l)f'''+\frac{k^3\gamma+l^3\varepsilon}{2(k+l)} $$
である。引き算して
$$ \lvert r_i\rvert\le\frac34L\cdot\frac{k^3+l^3}{k+l}=\frac34L(k^2-kl+l^2)\le\frac34Lh^2 $$
を得る。端の行も同様である。$k:=h_1$ とすると、$\frac{6(\delta_1-f'(a))}k=3f''+kf'''+\frac{k^2}4\alpha$、$2F_0+F_1=3f''+kf'''+\frac{k^2}2\gamma$(値は $a$ でのもの)なので、残差の絶対値は $\frac34Lk^2$ 以下である。右端も同じである。
ステップ 2:モーメントの誤差。 $u_i:=M_i-F_i$ は、thm-spl-main の完全スプラインの方程式の右辺を $-r_i$ に替えた方程式を満たす。lem-spl-dd($m=1$)により $\max_i\lvert u_i\rvert\le\frac34Lh^2$ である。
ステップ 3:$2$ 階導関数の誤差。 $x\in I_i$ とする。$S''$ は $M_{i-1},M_i$ を結ぶ 1 次式である。$\ell$ を $F_{i-1},F_i$ を結ぶ 1 次式とすると $\lvert S''-\ell\rvert\le\frac34Lh^2$ である。Lagrange補間 の定理「補間の誤差」を 2 点 $x_{i-1},x_i$ と $f''$ に使うと $\lvert f''-\ell\rvert\le\frac L2\cdot\frac{h_i^2}4=\frac18Lh^2$ である。合わせて $\lvert f''-S''\rvert\le\frac78Lh^2$ である。
ステップ 4:値の誤差。 $e:=f-S$ は $C^2$ 級で、節点で $0$ である。$x\in I_i$ に対し、$e$ を 2 点 $x_{i-1},x_i$ で補間した多項式は $0$ なので、同じ定理から $\lvert e(x)\rvert\le\frac{h_i^2}8\max\lvert e''\rvert\le\frac7{64}Lh^4$ である。Rolleの定理 により $e'$ は $I_i$ に零点 $c$ をもつので、$\lvert e'(x)\rvert=\bigl\lvert\int_c^xe''\bigr\rvert\le h\max\lvert e''\rvert\le\frac78Lh^3$ である。$\square$

定数 $\frac7{64}$ は最良ではない。ex-spl-order の $e^x$ では $\lvert f-S\rvert/(Lh^4)$ は約 $0.0026$ である。not-a-knot 条件でも、等間隔の節点で $f\in C^4$ なら、十分小さい $h$ で誤差は $Ch^4$ 以下である(DB22 Theorem 5.3.1。この記事では証明しない)。一方、自然スプラインは $f''(a)$ が $0$ でないと端で $S''(a)=0$ が外れ、誤差は $h^2$ の定数倍に落ちる(ex-spl-order)。

計算の手順

  1. 準備:節点を昇順に並べ、相異なることを確かめる。$h_i$ と $\delta_i$ を計算する。
  2. 端の条件を選ぶ:下の表のどれかを選ぶ。迷ったら、傾きが分かれば完全、分からなければ not-a-knot である。
  3. 方程式を作る:fml-spl-tri と端の条件を並べる。
  4. 解く:行列は三重対角なので、次の消去で解く。方程式を $a_iu_{i-1}+b_iu_i+c_iu_{i+1}=r_i$($i=1,\dots,N$、$a_1=c_N=0$)とする。$c'_0:=r'_0:=0$ として、$i=1,\dots,N$ の順に $c'_i\leftarrow c_i/(b_i-a_ic'_{i-1})$、$r'_i\leftarrow(r_i-a_ir'_{i-1})/(b_i-a_ic'_{i-1})$ とする。次に $u_N\leftarrow r'_N$、$i=N-1,\dots,1$ の順に $u_i\leftarrow r'_i-c'_iu_{i+1}$ とする(prop-spl-thomas)。
  5. 値を求める:点 $x$ を含む区間 $I_i$ を二分探索で見つけ、fml-spl-piece に入れる。
  6. 失敗の検出:節点が重なる($h_i=0$)、周期で $y_0\ne y_n$、not-a-knot で $n< 3$ のときは解けない。反復はないので、止める判定は要らない。
    端の条件未知数方程式の形
    自然$M_1,\dots,M_{n-1}$三重対角
    完全$M_0,\dots,M_n$三重対角
    周期$M_0,\dots,M_{n-1}$三重対角に、右上と左下の隅の成分が加わる
    not-a-knot$M_1,\dots,M_{n-1}$三重対角($M_0,M_n$ を消去した形)
    周期の場合は隅の成分があるので、一般の連立 1 次方程式として解くか、隅の列も追いかけて消去する。
手順の正しさ

$\lvert b_i\rvert>\lvert a_i\rvert+\lvert c_i\rvert$($i=1,\dots,N$)なら、手順 4 の分母はどれも $0$ でなく、すべての $i$ で $\lvert c'_i\rvert< 1$ である。手順 4 の結果は方程式の解で、四則演算の回数は $N$ の定数倍である。

$i$ についての帰納法で $\lvert c'_{i-1}\rvert< 1$ とする($i=1$ では $c'_0=0$)。$\lvert b_i-a_ic'_{i-1}\rvert\ge\lvert b_i\rvert-\lvert a_i\rvert>\lvert c_i\rvert$ なので、分母は $0$ でなく $\lvert c'_i\rvert< 1$ である。消去の 1 段は、第 $i$ 行から前の行の $a_i$ 倍を引いて $b_i-a_ic'_{i-1}$ で割ることにあたり、結果は $u_i+c'_iu_{i+1}=r'_i$ の形である。後退代入がこれを解く。各行の演算は定数回である。$\square$

thm-spl-main の証明の正規化された方程式は、自然・完全・not-a-knot のどれでもこの仮定を満たす。ピボットの入れ替えは要らない。

例題

4 点の自然スプラインと not-a-knot

問い:$(0,0)$、$(1,1)$、$(2,0)$、$(3,1)$ の自然スプライン $S$ と not-a-knot のスプライン $T$ を求める。
使う公式:fml-spl-piece、fml-spl-tri、thm-spl-minimal。
答え:$S$ は $M=(0,-4,4,0)$ で、$[0,1]$ では $S(x)=-\frac23x^3+\frac53x$ である。$S(\frac12)=0.75$、$S(\frac32)=0.5$、$S(\frac52)=0.25$、$\int_0^3S''^2=16$ である。$T$ は 4 点の補間多項式 $T(x)=\frac23x^3-3x^2+\frac{10}3x$ で、$T(\frac12)=1$、$\int_0^3T''^2=36$ である。

途中の計算を開く

$\delta=(1,-1,1)$、$h=1$ なので、$4M_1+M_2=6(-1-1)=-12$、$M_1+4M_2=6(1+1)=12$ より $M_1=-4$、$M_2=4$ である。fml-spl-piece で $i=1$ とすると $S(x)=\frac{-4x^3}6+(0)(1-x)+\bigl(1+\frac46\bigr)x=-\frac23x^3+\frac53x$ である。$\int_0^3S''^2$ は、$S''$ が $-4x$、$-4+8(x-1)$、$4-4(x-2)$ なので $\frac{16}3\times3=16$ である。$T$ は 3 階導関数が一定なので $M=(-6,-2,2,6)$ で、thm-spl-minimal のとおり $16\le36$ である。

等間隔でない 3 点

問い:$(0,0)$、$(1,2)$、$(3,0)$ の自然スプラインの $x=\frac12$、$x=2$ の値を求める。
使う公式:fml-spl-tri。
答え:$M_1=-3$、$S(\frac12)=1.1875$、$S(2)=1.75$ である。

途中の計算を開く

$h_1=1$、$h_2=2$、$\delta_1=2$、$\delta_2=-1$ なので、$2\cdot3M_1=6(-1-2)$ より $M_1=-3$ である。$[0,1]$ では $S(x)=-\frac12x^3+\frac52x$、$[1,3]$ では $S(x)=-\frac14(3-x)^3+2(3-x)$ である。$x=1$ でどちらも値 $2$、傾き $1$、$2$ 階導関数 $-3$ になる。

$\sin x$ の完全スプライン

問い:$\sin x$ を $[0,\pi]$ で $h=\pi/4$ の 5 点、$A=1$、$B=-1$ の完全スプラインで補間する。
使う公式:thm-spl-main、thm-spl-error。
答え:$M\approx(-0.010137,-0.741254,-1.053835,-0.741254,-0.010137)$、$S(0.5)\approx0.479339$($\sin0.5\approx0.479426$)である。最大誤差は約 $0.001124$ で、thm-spl-error の上界は $\frac7{64}h^4\approx0.04162$ である。

途中の計算を開く

対称性より $M_3=M_1$、$M_4=M_0$ である。$h=\pi/4$、$y=(0,s,1,s,0)$($s=\frac{\sqrt2}2$)として、$2M_0+M_1=\frac6h\bigl(\frac sh-1\bigr)$、$M_0+4M_1+M_2=\frac{6(1-2s)}{h^2}$、$2M_1+4M_2=\frac{6(2s-2)}{h^2}$ を解く。$\max_i\lvert M_i-f''(x_i)\rvert\approx0.05383$ で、thm-spl-error の証明のステップ 2 の上界 $\frac34h^2\approx0.4626$ の範囲にある。

$\cos x$ の周期スプライン

問い:$\cos x$ を $[0,2\pi]$ で $h=\pi/2$ の 5 点の周期スプラインで補間し、$x=\pi/4$ の値を求める。
使う公式:thm-spl-main。
答え:$M=\bigl(-\frac{12}{\pi^2},0,\frac{12}{\pi^2},0,-\frac{12}{\pi^2}\bigr)$、$S(\frac\pi4)=\frac{11}{16}=0.6875$($\cos\frac\pi4\approx0.707107$)である。

途中の計算を開く

値は $1,0,-1,0,1$、$\delta=(-1,-1,1,1)/h$ である。$M_1=M_3=0$、$M_2=-M_0$ を確かめると、$i=0$ の式は $4hM_0=6(\delta_1-\delta_4)=-\frac{12}h$ となり、$M_0=-3/h^2=-12/\pi^2$ である。解はただ 1 つなので、これが解である。fml-spl-piece の $x=h/2$ の値は $\frac12-\frac{M_0h^2}{16}=\frac12+\frac3{16}$ である。

Runge の関数

問い:$f(x)=1/(1+25x^2)$ を $[-1,1]$ の等間隔の $n+1$ 点で補間し、$n$ 次の多項式と自然スプラインの最大誤差を比べる。
答え:下の表のとおりで、多項式は発散し、スプラインは減る(数値計算による値)。

$n$多項式の最大誤差自然スプラインの最大誤差
$5$$0.4327$$0.4235$
$10$$1.916$$0.02197$
$20$$59.82$$0.003183$

図: 左は 11 点の補間多項式と自然スプライン。右は刻み幅と最大誤差の両対数グラフ 図: 左は 11 点の補間多項式と自然スプライン。右は刻み幅と最大誤差の両対数グラフ

収束の次数

問い:$[0,1]$ の等間隔の節点で、$h=1/n$ を半分にしたときの最大誤差の減り方を見る。
答え:$f=e^x$ の完全スプラインは $h^4$、$f=e^x$ の自然スプラインは $h^2$、$f=\lvert x-\frac13\rvert$ の完全スプラインは $h$ で減る(下の表。数値計算による値)。$f=\lvert x-\frac13\rvert^3$ の完全スプラインでは減り方は $h^3$ である。

$n$$e^x$ 完全$e^x$ 自然$\lvert x-\frac13\rvert$ 完全
$10$$6.956\times10^{-7}$$1.333\times10^{-3}$$2.945\times10^{-2}$
$20$$4.387\times10^{-8}$$3.335\times10^{-4}$$1.473\times10^{-2}$
$40$$2.754\times10^{-9}$$8.340\times10^{-5}$$7.362\times10^{-3}$
$80$$1.725\times10^{-10}$$2.085\times10^{-5}$$3.681\times10^{-3}$
比の $\log_2$(最後の 2 行)$3.997$$2.000$$1.000$

使える条件と反例

外す条件反例成り立たなくなること
端の条件を 2 つ置く点 $-1,0,1$、値がすべて $0$一意性:$0$ と $x^3-x$ がどちらも 3 次スプライン
thm-spl-minimal で $g$ が端の傾きを共有する点 $0,1$、値 $0,0$、$A=1$、$B=-1$ の完全スプライン最小性:$S=x(1-x)$ の $\int S''^2=4$ に対し、$g=0$ は $0$
$f\in C^4$$f=\lvert x-\frac13\rvert$($C^0$ だが $C^1$ でない)thm-spl-error の $h^4$ が $h$ に落ちる
端の条件が $f$ に合う$e^x$ の自然スプライン($f''(0)=1\ne0$)$h^4$ が $h^2$ に落ちる
節点が相異なる$x_1=x_2$ に別の値$h_2=0$ で式が立たず、関数でもない
データの形(単調性)の保存を期待する値 $0,0,0,1,1,1$ の自然スプライン単調なデータなのに $S$ は最小値 $-0.1092$、最大値 $1.1092$ をとる
反例の確認

端の条件がないとき:$x^3-x$ は $-1,0,1$ で $0$ で、1 つの 3 次式なので 3 次スプラインである。prop-spl-dim の次元 $n+3=5$ に対し補間の条件は 3 個で、差の 2 次元分が残る。
端の傾きが違う $g$:$S=x(1-x)$ は $S'(0)=1$、$S'(1)=-1$ を満たし、$S''=-2$ なので $\int_0^1S''^2=4$ である。$g=0$ は同じデータを補間するが $g'(0)=0\ne1$ なので、thm-spl-minimal の後半の仮定を満たさない。
単調性:値 $0,0,0,1,1,1$(節点 $0,\dots,5$)の自然スプラインは、$x\approx1.616$ で最小値 $-0.1092$、$x\approx3.384$ で最大値 $1.1092$ をとる(数値計算による値)。$S$ が $C^2$ 級という制約が、段差の手前で行き過ぎを生む。

よくある誤り

誤り正しくはなぜ
等間隔の $M_{i-1}+4M_i+M_{i+1}$ を不等間隔にも使う不等間隔では $h_i$、$2(h_i+h_{i+1})$、$h_{i+1}$ を係数にするfml-spl-tri
右辺の $6$ を落とす右辺は $6(\delta_{i+1}-\delta_i)$thm-spl-main の証明
補間の条件だけで決まると思う条件が 2 つ足りないprop-spl-dim
端の情報がないのに自然スプラインを使い、精度を $h^4$ と思う自然スプラインは $S''=0$ を課すので一般に $h^2$ex-spl-order
3 次スプラインは 3 階導関数まで連続と思う連続なのは $2$ 階まで。ex-spl-four の $S'''$ は $-4,8,-4$ と跳ぶdef-spl-spline
$\int S''^2$ の最小性を「曲率の最小性」と言う最小なのは $\int g''^2$ で、$\int\kappa^2ds$ ではないthm-spl-minimal

演習

3 点の自然スプライン

節点 $0,h,2h$、値 $y_0,y_1,y_2$ の自然スプラインの $M_1$ を求めよ。

解答を開く

fml-spl-tri で $M_0=M_2=0$ とすると $4hM_1=6\cdot\frac{y_2-2y_1+y_0}h$ なので、$M_1=\dfrac{3(y_0-2y_1+y_2)}{2h^2}$ である。$y=(0,1,0)$、$h=1$ なら $M_1=-3$ である。

折れ線の最小性

節点で同じ値をとる $C^1$ 級の $g$ と、節点を結ぶ折れ線 $S$ について、$\int_a^bg'^2\ge\int_a^bS'^2$ を示せ。

解答を開く

$e:=g-S$ とおく。$S'$ は $I_i$ で定数 $\delta_i$ なので、$\int_a^bS'e'=\sum_i\delta_i(e(x_i)-e(x_{i-1}))=0$ である。よって $\int g'^2=\int S'^2+\int e'^2\ge\int S'^2$ である。$\square$

補足

  • 値を 1 つ変えたときの影響:スプラインは大域的な方程式で決まるので、1 つの値を変えると全体が変わる(DB22 §5.3)。ただし影響は指数的に減る。等間隔の内部では $M_{i-1}+4M_i+M_{i+1}=0$ の解は $(-2\pm\sqrt3)^i$ なので、節点を 1 つ離れるごとに約 $2-\sqrt3\approx0.268$ 倍になる。$n=20$ で $y_{10}=1$、ほかを $0$ とした自然スプラインの $M_{10},\dots,M_{14}$ は $-4.392$、$2.785$、$-0.746$、$0.200$、$-0.054$ である(数値計算による値)。
  • B スプライン:スプラインの空間の基底として、台の小さい Bスプライン が使われる。漸化式は同記事の定義「B スプライン」と ESL17 の付録(pp. 186–187、式 (5.77)・(5.78))にあり、基底であることの証明は同記事の定理「Curry–Schoenberg の定理」にある。prop-spl-dim の基底は台が広く、数値的にはこちらがよい。
  • 自然スプラインの別の見方:$S''(a)=S''(b)=0$ は、$S$ を区間の外へ 1 次式で延ばしても $C^2$ 級になるということである(ESL17 §5.2.1、p. 145)。
  • 最適化との関係:スプラインは係数について線形なので、関数の当てはめの問題を有限次元の最適化に直すときの基底の族になる(BV04 §6.5.1、p. 327)。
  • 折れ線との比較:折れ線の誤差は $\frac18h^2\max\lvert f''\rvert$ 以下で(Lagrange補間 の定理「補間の誤差」)、方程式を解く必要がない。$e^x$ を $[0,1]$ の $n=10$ で補間すると、折れ線の誤差は約 $0.00323$、完全スプラインの誤差は約 $7\times10^{-7}$ である。

関連項目

参考文献

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する