Bスプライン

同義語:B-splineB-スプラインBスプライン関数Bスプライン基底B-spline basis

概要

Bスプライン(B-spline)とは、節点列から漸化式で定まる区分多項式で、次数 $d$ のものは隣り合う $d+1$ 個の節点区間でしか $0$ でない非負の関数である。使う範囲では和が $1$ になり、単純な内部節点と両端を $d+1$ 重にした節点列のものはスプラインの空間の基底をなす。係数を $1$ つ変えても曲線が変わるのは $d+1$ 個の区間だけで、値は凸結合の繰り返しで計算できる。

$$\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}} $$

前提知識: スプライン補間, 線形独立, Rolleの定理, 畳み込み

3 次スプラインを スプライン補間 のように節点での $2$ 階導関数で表すと、値を $1$ つ変えただけで全体が変わる。切断べき $(x-x_i)_+^3$ を基底にとると、係数を $1$ つ変えた影響は右端まで届く。どちらも局所的な修正には向かない。
B スプライン は、スプラインの空間の基底のうち、台がいちばん狭いものである。次数 $d$ の B スプラインは隣り合う $d+1$ 個の節点区間でしか $0$ でなく、値は負にならず、和は $1$ になる。そのため、係数 $c_i$ を $1$ つ動かしても曲線が変わるのは $d+1$ 個の区間だけで、値の計算は凸結合の繰り返しで安定に行える。
この記事では、漸化式による定義から出発し、Marsden の恒等式、基底であること(Curry–Schoenberg の定理)、補間が解ける条件(Schoenberg–Whitney の定理)を証明する。3 次スプラインの方程式と端の条件は スプライン補間 に任せる。

定義と使える条件

$d\ge0$、$n\ge1$ とし、$t_1\le t_2\le\cdots\le t_{n+d+1}$ を実数の列とする。これを 節点列 といい、同じ値が $m$ 回並ぶとき、その点の 重複度 は $m$ であるという。

B スプライン

節点列に対し、$d=0$ では
$$ B_{i,0}(x):=\begin{cases}1&(t_i\le x< t_{i+1})\\0&(\text{それ以外})\end{cases} $$
とおき、$d\ge1$ では
$$ B_{i,d}(x):=\frac{x-t_i}{t_{i+d}-t_i}B_{i,d-1}(x)+\frac{t_{i+d+1}-x}{t_{i+d+1}-t_{i+1}}B_{i+1,d-1}(x) $$
とおく。ただし分母が $0$ の項は $0$ とする。$B_{i,d}$ を節点 $t_i,\dots,t_{i+d+1}$ の 次数 $d$ の B スプライン という。$d+1$ を 階数 と呼ぶ文献もある。

漸化式は ESL17 の付録(p. 187、式 (5.77)・(5.78))にある。この記事では係数の略記として
$$ \omega_{i,d}(x):=\frac{x-t_i}{t_{i+d}-t_i},\qquad\alpha_{i,d}:=\frac1{t_{i+d}-t_i} $$
を使い(分母が $0$ なら $0$)、定義の式を $B_{i,d}=\omega_{i,d}B_{i,d-1}+(1-\omega_{i+1,d})B_{i+1,d-1}$ と書く。分母が $0$ になるのは対応する $B$ が恒等的に $0$ のときだけなので(prop-bsp-support)、この書き方で値は変わらない。
節点の並べ方。両端を $d+1$ 重にした列を 開いた節点列 という。区間 $[a,b]$ と $a< \xi_1< \cdots< \xi_L< b$ に対し
$$ \underbrace{a,\dots,a}_{d+1},\ \xi_1,\dots,\xi_L,\ \underbrace{b,\dots,b}_{d+1} $$
と並べたもので、このとき $n=L+d+1$ である。節点がすべて相異なる列を 単純な節点列 という。
B スプラインを使う条件は次のとおりである。

  • (i) 節点列は単調増加に並べる。重複は許す。
  • (ii) 和 $\sum_ic_iB_{i,d}$ を使う範囲は $I:=[t_{d+1},t_{n+1})$ である。cor-bsp-unity はこの外では成り立たない。
  • (iii) 定義は右連続の形なので、開いた節点列の右端 $x=b$ では左極限の値を使う。
  • (iv) なめらかさは節点の重複度で決まる。内部の節点が単純なら $C^{d-1}$ 級である(prop-bsp-smooth)。
台と符号
  1. $B_{i,d}$ は $[t_i,t_{i+d+1})$ の外で $0$ であり、各節点区間の上で次数 $d$ 以下の多項式である。
  2. すべての $x$ で $B_{i,d}(x)\ge0$ である。
  3. $t_i< x< t_{i+d+1}$ とする。$x$ が節点でないか、節点列が単純なら、$B_{i,d}(x)>0$ である。

$d$ についての帰納法を使う。$d=0$ は定義のとおりである。$d\ge1$ とする。$B_{i,d-1}$ の台は $[t_i,t_{i+d})$、$B_{i+1,d-1}$ の台は $[t_{i+1},t_{i+d+1})$ で、それぞれの上で係数 $\omega_{i,d}$、$1-\omega_{i+1,d}$ は非負の 1 次式である。これで 1 と 2 を得る。
3 を示す。$x< t_{i+d}$ なら $\omega_{i,d}(x)>0$ で、帰納法の仮定から $B_{i,d-1}(x)>0$ である。$x\ge t_{i+d}$ で $x>t_{i+1}$ なら、同様に第 2 項が正である。残るのは節点列が単純で $d=1$、$x=t_{i+1}$ の場合で、定義から $B_{i,1}(x)=B_{i+1,0}(x)=1$ である。$\square$

公式の表

公式使える条件根拠
$B_{i,d}\ge0$、台は $[t_i,t_{i+d+1}]$すべての節点列prop-bsp-support
$(y-x)^d=\sum_i\prod_{j=1}^d(y-t_{i+j})\,B_{i,d}(x)$$x\in I$thm-bsp-marsden
$\sum_iB_{i,d}=1$$x\in I$cor-bsp-unity
$\sum_it_i^*B_{i,d}(x)=x$、$t_i^*=\frac1d(t_{i+1}+\cdots+t_{i+d})$$x\in I$、$d\ge1$cor-bsp-unity
$B_{i,d}'=d(\alpha_{i,d}B_{i,d-1}-\alpha_{i+1,d}B_{i+1,d-1})$$d\ge1$、節点でない $x$fml-bsp-derivative
$\bigl(\sum_ic_iB_{i,d}\bigr)'=d\sum_i\alpha_{i,d}(c_i-c_{i-1})B_{i,d-1}$同上($c_0=c_{n+1}=0$)fml-bsp-derivative
$\sum_ic_iB_{i,d}=\sum_ic_i^{[1]}B_{i,d-1}$、$c_i^{[1]}=\omega_{i,d}c_i+(1-\omega_{i,d})c_{i-1}$$d\ge1$prop-bsp-deboor
$M_d=M_{d-1}*\mathbf 1_{[0,1)}$節点 $0,1,\dots,d+1$prop-bsp-cardinal

主定理と証明

Marsden の恒等式

B スプラインの性質の多くは、次の 1 つの恒等式から出る。

Marsden の恒等式

$d+1\le\mu\le n$、$t_\mu< t_{\mu+1}$ とし、$x\in[t_\mu,t_{\mu+1})$ とする。すべての実数 $y$ について
$$ (y-x)^d=\sum_{i=\mu-d}^{\mu}\psi_{i,d}(y)\,B_{i,d}(x),\qquad\psi_{i,d}(y):=\prod_{j=1}^{d}(y-t_{i+j}) $$
である。

$d$ についての帰納法で示す。$d=0$ では $\psi_{\mu,0}=1$ で、$B_{\mu,0}(x)=1$ である。
$d\ge1$ とする。右辺に定義の漸化式を入れる。$x$ の位置から $B_{\mu-d,d-1}(x)=B_{\mu+1,d-1}(x)=0$ なので(prop-bsp-support)、残るのは $i=\mu-d+1,\dots,\mu$ の $B_{i,d-1}(x)$ で、その係数は
$$ \psi_{i,d}(y)\,\omega_{i,d}(x)+\psi_{i-1,d}(y)\bigl(1-\omega_{i,d}(x)\bigr) $$
である。この範囲では $t_i\le t_\mu< t_{\mu+1}\le t_{i+d}$ なので、分母 $t_{i+d}-t_i$ は正である。$\psi_{i,d}(y)=(y-t_{i+d})\psi_{i,d-1}(y)$、$\psi_{i-1,d}(y)=(y-t_i)\psi_{i,d-1}(y)$ を使うと、係数は $\psi_{i,d-1}(y)$ の
$$ \frac{(y-t_{i+d})(x-t_i)+(y-t_i)(t_{i+d}-x)}{t_{i+d}-t_i}=y-x $$
倍である(分子を展開すると $(y-x)(t_{i+d}-t_i)$ になる)。よって右辺は $(y-x)\sum_{i=\mu-d+1}^{\mu}\psi_{i,d-1}(y)B_{i,d-1}(x)$ で、帰納法の仮定から $(y-x)^d$ に等しい。$\square$

1 の分割と 1 次式の再現

$x\in I$ なら $\sum_{i=1}^nB_{i,d}(x)=1$ である。$d\ge1$ なら、$t_i^*:=\frac1d(t_{i+1}+\cdots+t_{i+d})$ について $\sum_{i=1}^nt_i^*B_{i,d}(x)=x$ である。

thm-bsp-marsden の両辺を $y$ の多項式と見る。$\psi_{i,d}(y)=y^d-d\,t_i^*y^{d-1}+\cdots$ で、左辺は $y^d-dxy^{d-1}+\cdots$ である。$y^d$ と $y^{d-1}$ の係数を比べる。$\mu$ の範囲外の $i$ の項は $x$ で $0$ である。$\square$

$t_i^*$ を Greville 点 という。折れ線 $(t_i^*,c_i)$ を 制御折れ線 といい、cor-bsp-unity の 2 つから、グラフ上の点 $(x,\sum_ic_iB_{i,d}(x))$ は制御点 $(t_i^*,c_i)$ の凸結合である。

局所的な線形独立性

thm-bsp-marsden の $\mu$ について、$B_{\mu-d,d},\dots,B_{\mu,d}$ を $[t_\mu,t_{\mu+1})$ に制限したものは、次数 $d$ 以下の多項式の空間の基底である。

制限はどれも次数 $d$ 以下の多項式である(prop-bsp-support)。$d+1$ 個の相異なる $y$ の $(y-x)^d$ は Vandermonde 行列の正則性により次数 $d$ 以下の多項式の空間を張る。thm-bsp-marsden からこの空間は $d+1$ 個の制限で張られるので、それらは基底である。$\square$

$\mu< d+1$ や $\mu>n$ の区間でも、左右に節点を足して節点列を延ばすと、$1\le i\le n$ の $B_{i,d}$ を変えずに同じ結論を使える。

導関数となめらかさ

導関数の公式

$d\ge1$ とする。節点でない $x$ で
$$ B_{i,d}'(x)=d\bigl(\alpha_{i,d}B_{i,d-1}(x)-\alpha_{i+1,d}B_{i+1,d-1}(x)\bigr) $$
である。

要点:定義の式を微分し、$B_{\cdot,d-1}$ の微分に帰納法の仮定を入れて、$B_{\cdot,d-2}$ の係数を比べる。

詳しい証明を開く

$d=1$ は定義の式を微分すればよい($B_{\cdot,0}$ は節点の外で局所定数)。$d\ge2$ とし、$d-1$ で正しいとする。定義の式を微分すると $B_{i,d}'=\alpha_{i,d}B_{i,d-1}-\alpha_{i+1,d}B_{i+1,d-1}+E$、$E:=\omega_{i,d}B_{i,d-1}'+(1-\omega_{i+1,d})B_{i+1,d-1}'$ である。示すべきことは $E=(d-1)(\alpha_{i,d}B_{i,d-1}-\alpha_{i+1,d}B_{i+1,d-1})$ である。左辺に帰納法の仮定を、右辺に定義の漸化式を入れ、$B_{i,d-2},B_{i+1,d-2},B_{i+2,d-2}$ の係数を比べる(どちらも $(d-1)$ 倍で、以下その中身を比べる)。

$B_{i,d-2}$:どちらも $\frac{x-t_i}{(t_{i+d}-t_i)(t_{i+d-1}-t_i)}$ である。$B_{i+2,d-2}$:どちらも $-\frac{t_{i+d+1}-x}{(t_{i+d+1}-t_{i+1})(t_{i+d+1}-t_{i+2})}$ である。$B_{i+1,d-2}$:$a=t_i$、$b=t_{i+1}$、$c=t_{i+d}$、$e=t_{i+d+1}$ とおくと、左辺は $\frac1{c-b}\bigl(1-\frac{x-b}{e-b}-\frac{x-a}{c-a}\bigr)$、右辺は $\frac1{c-a}\cdot\frac{c-x}{c-b}-\frac1{e-b}\cdot\frac{x-b}{c-b}$ で、$1-\frac{x-a}{c-a}=\frac{c-x}{c-a}$ から等しい。

分母が $0$ の場合:たとえば $c=b$ なら $B_{i+1,d-2}=0$ で、この項は比較しなくてよい。$B_{i+1,d-2}\ne0$ なら $b< c$ なので $a< c$、$b< e$ で、現れる分母はすべて正である。ほかの 2 項も同様である。$\square$

和の導関数の式は、この公式を足して $B_{i,d-1}$ でまとめ直したものである。

なめらかさ

$d\ge1$ とする。$\xi$ が $t_i,\dots,t_{i+d+1}$ の中に高々 $1$ 回しか現れないなら、$B_{i,d}$ は $\xi$ の近くで $C^{d-1}$ 級である。

$\xi$ が現れないなら $\xi$ の近くで多項式である。現れるとして $d$ についての帰納法で示す。$d=1$:$\xi=t_{i+1}$ なら左右の極限はどちらも $1$、$\xi=t_i$ または $\xi=t_{i+2}$ ならどちらも $0$ である。$d\ge2$:$B_{i,d-1}$ と $B_{i+1,d-1}$ の節点は $t_i,\dots,t_{i+d+1}$ の一部なので、帰納法の仮定からどちらも $\xi$ の近くで $C^{d-2}$ 級である。定義の式から $B_{i,d}$ は $\xi$ で連続で、fml-bsp-derivative から $\xi$ の外の導関数は $\xi$ まで $C^{d-2}$ 級に延びる。連続な関数の導関数が点の外で定まり、その点まで連続に延びるなら、関数はその点で $C^1$ 級である。よって $B_{i,d}$ は $C^{d-1}$ 級である。$\square$

内部の節点を重複させると、なめらかさが重複度 $1$ につき $1$ 段下がる(ESL17 p. 187。この記事では単純な場合だけ証明する)。

Curry–Schoenberg の定理

$a< \xi_1< \cdots< \xi_L< b$ に対し、$[a,b]$ 上の関数で、各区間 $[\xi_j,\xi_{j+1}]$($\xi_0:=a$、$\xi_{L+1}:=b$)で次数 $d$ 以下の多項式に等しく、$C^{d-1}$ 級のものの全体を $S_d(\xi)$ と書く。これは スプライン補間 の定義「スプライン関数」の次数 $d$ のスプラインの空間である。

Curry–Schoenberg の定理

$d\ge1$、$n:=L+d+1$ とする。開いた節点列 $a$($d+1$ 重)、$\xi_1,\dots,\xi_L$、$b$($d+1$ 重)の $B_{1,d},\dots,B_{n,d}$ は、$x=b$ を左極限で補うと、$S_d(\xi)$ の基底である。とくに $\dim S_d(\xi)=L+d+1$ である。

次元の上界。 $S\in S_d(\xi)$ の $[a,\xi_1]$ の上の多項式を $q$ とする。$j=1,\dots,L$ の順に見ると、$\xi_j$ の両側の多項式の差は $\xi_j$ で $d-1$ 階まで $0$ なので $e_j(x-\xi_j)^d$ の形である。よって $S=q+\sum_{j=1}^Le_j(x-\xi_j)_+^d$ で、$\dim S_d(\xi)\le(d+1)+L=n$ である。
$B_{i,d}$ が $S_d(\xi)$ に属すること。 prop-bsp-support から節点区間ごとに次数 $d$ 以下の多項式である。内部の節点 $\xi_j$ は節点列の中で単純なので、prop-bsp-smooth から $C^{d-1}$ 級である。
線形独立性。 $\mu=d+1,\dots,n$ のどの $\mu$ でも $t_\mu< t_{\mu+1}$ である。$\sum_ic_iB_{i,d}=0$ を $[t_\mu,t_{\mu+1})$ に制限すると、cor-bsp-local から $c_{\mu-d}=\cdots=c_\mu=0$ である。$\mu$ を動かすと $c_1=\cdots=c_n=0$ を得る。
$n$ 個の線形独立な元があり次元が $n$ 以下なので、基底である。$\square$

Schoenberg–Whitney の定理

スプラインで補間するとき、どの点を選べば解けるかは次の定理で決まる。証明の核は、スプラインの零点の個数の評価である。

零点の個数

節点列は単純とし、$d\ge1$、$p\le q$ とする。$s=\sum_{i=p}^qc_iB_{i,d}$ の係数の少なくとも $1$ つが $0$ でないとき、$J:=(t_p,t_{q+d+1})$ の中の $s$ の零点の集合の連結成分は $q-p$ 個以下である。

端の係数を消す。 $c_p=0$ なら $s$ は $(t_p,t_{p+1}]$ で $0$ で、$p$ を $p+1$ に替えた主張から、成分の数は高々 $1$ 増えるだけである。$c_q=0$ も同じである。そこで $q-p$ についての帰納法により $c_p\ne0$、$c_q\ne0$ としてよい。$p=q$ は prop-bsp-support の 3 から零点がない。
$d=1$。 $s$ は折れ線で、$s(t_{i+1})=c_i$ である。$c_p,c_q\ne0$ なので、$(t_p,t_{p+1}]$ と $[t_{q+1},t_{q+2})$ に零点はない。残りの $q-p$ 個の閉区間 $[t_{i+1},t_{i+2}]$ では、1 次式の零点の集合は空か $1$ 点か区間全体で連結である。成分はどれかの閉区間と交わり、$1$ つの閉区間と交わる成分は $1$ つだけなので、成分は $q-p$ 個以下である。
$d\ge2$。 $d-1$ で正しいとする。$J$ の中の成分を $C_1<\cdots< C_z$ とする。$s$ は $C^1$ 級で(prop-bsp-smooth)、$J$ の両端で $0$ である。$c_p,c_q\ne0$ より両端の近くの $J$ の内側で $s\ne0$ である(prop-bsp-support の 3)。よって両端の $2$ 点と $C_1,\dots,C_z$ の間に $z+1$ 個の隙間があり、Rolleの定理 から各隙間に $s'(\xi)=0$、$s(\xi)\ne0$ を満たす点 $\xi$ がある。隣り合う $2$ 点の間に $s=0$ の点があるので、その $2$ 点の間で $s'$ が恒等的に $0$ にはならない。したがって $s'$ の零点の集合は $J$ の中に $z+1$ 個以上の成分をもつ。fml-bsp-derivative から $s'=\sum_{i=p}^{q+1}c_i'B_{i,d-1}$ の形で、$s$ は台がコンパクトで $0$ でないので $s'\ne0$ である。指標の範囲は $q+1-p+1$ 個で、対応する開区間は同じ $J$ である。帰納法の仮定から $z+1\le q+1-p$ である。$\square$

Schoenberg–Whitney の定理

節点列は単純で $d\ge1$ とし、$\tau_1<\cdots<\tau_n$ とする。行列 $A:=(B_{j,d}(\tau_i))_{i,j=1}^n$ が正則であるための必要十分条件は、すべての $i$ で
$$ t_i<\tau_i< t_{i+d+1} $$
が成り立つことである。

必要性。 $\tau_i\le t_i$ のある $i$ があるとする。$k\le i\le j$ なら $\tau_k\le t_j$ なので、$B_{j,d}(\tau_k)=0$ である($d\ge1$ なので左端でも値は $0$)。$A$ の第 $1,\dots,i$ 行は第 $1,\dots,i-1$ 列にしか $0$ でない成分をもたないので、階数が足りない。$\tau_i\ge t_{i+d+1}$ のときは、$j\le i\le k$ で $B_{j,d}(\tau_k)=0$ となり、第 $i,\dots,n$ 行が第 $i+1,\dots,n$ 列にしか成分をもたない。
十分性。 条件のもとで $Ac=0$、$c\ne0$ とし、$s:=\sum_ic_iB_{i,d}$ とする。$s$ は $0$ でないので、$s$ が恒等的に $0$ でない節点区間 $(t_\mu,t_{\mu+1})$ がある。そのような $\mu$ の連続する極大な範囲を $u,\dots,v-1$ とする。
$u\ge2$ なら $s$ は $(t_{u-1},t_u)$ で $0$ なので、cor-bsp-local から $c_{u-1-d},\dots,c_{u-1}$ は $0$ である(節点列を延ばして使う。添字が範囲の外の分は無視する)。同様に $v\le n+d$ なら $c_{v-d},\dots,c_v$ は $0$ である。よって $p:=u$、$q:=v-d-1$ とおくと、$J:=(t_u,t_v)$ の上で $s=\sum_{i=p}^qc_iB_{i,d}$ であり、$p\le q$ である。$J$ のどの節点区間でも $s$ は $0$ でない多項式なので、$J$ の中の零点は有限個の孤立点である。
一方、$p\le i\le q$ の $\tau_i$ は $t_p\le t_i<\tau_i< t_{i+d+1}\le t_{q+d+1}$ を満たすので $J$ に含まれ、$s(\tau_i)=0$ である。これは $q-p+1$ 個の相異なる零点で、lem-bsp-zeros に反する。$\square$

等間隔の節点

節点が $0,1,\dots,d+1$ の B スプラインを $M_d$ と書く(基数 B スプライン)。

畳み込みによる表示

$d\ge1$ なら $M_d=M_{d-1}*\mathbf 1_{[0,1)}$ である。したがって $M_d$ は $[0,1)$ の一様分布に従う独立な $d+1$ 個の確率変数の和の密度で、Fourier 変換は
$$ \int_{\mathbb R}M_d(x)e^{-\mathrm{i}\omega x}\,dx=\Bigl(\frac{1-e^{-\mathrm{i}\omega}}{\mathrm{i}\omega}\Bigr)^{d+1} $$
である。

$g(x):=(M_{d-1}*\mathbf 1_{[0,1)})(x)=\int_{x-1}^xM_{d-1}$ とおく。$M_{d-1}$ の節点は $0,\dots,d$、平行移動 $M_{d-1}(\cdot-1)$ の節点は $1,\dots,d+1$ である。節点間隔が $1$ なので $\alpha=1/d$ で、fml-bsp-derivative は $M_d'(x)=M_{d-1}(x)-M_{d-1}(x-1)$ を与える。これは節点の外で $g'$ に等しい。$M_d$ と $g$ は連続で($d=1$ は直接確かめる。$d\ge2$ は prop-bsp-smooth)、$x< 0$ でどちらも $0$ なので一致する。残りは 畳み込み の Fourier 変換の性質と、$\mathbf 1_{[0,1)}$ の変換を計算することによる。$\square$

これは VKG14 の elementary B-spline(§6.3、式 (6.34)・(6.37)、pp. 541–542)を $\frac{d+1}2$ だけ平行移動したものにあたる。

計算の手順

値 $s(x)=\sum_ic_iB_{i,d}(x)$ を求める de Boor の手順 は次のとおりである。

  1. 区間を探す:$t_\mu\le x< t_{\mu+1}$ となる $\mu$($d+1\le\mu\le n$)を二分探索で見つける。
  2. 初期値:$c_i^{[0]}:=c_i$($i=\mu-d,\dots,\mu$)とする。
  3. 更新:$r=1,\dots,d$、$i=\mu-d+r,\dots,\mu$ について
    $$ \lambda:=\frac{x-t_i}{t_{i+d+1-r}-t_i},\qquad c_i^{[r]}:=(1-\lambda)c_{i-1}^{[r-1]}+\lambda c_i^{[r-1]} $$
    とする。
  4. 答え:$s(x)=c_\mu^{[d]}$ である。
  5. 導関数:fml-bsp-derivative の係数 $d\,\alpha_{i,d}(c_i-c_{i-1})$ と次数 $d-1$ で同じ手順を使う。
  6. 失敗の検出:$x$ が $I$ の外なら止める。$\mu$ を $t_\mu< t_{\mu+1}$ となるように選べば分母は正である。
手順の正しさ

手順の結果は $s(x)$ に等しく、各 $\lambda$ は $[0,1]$ に入る。四則演算の回数は $d^2$ の定数倍である。

定義の式を $\sum_ic_iB_{i,d}$ に入れて $B_{i,d-1}$ でまとめると
$$ \sum_ic_iB_{i,d}=\sum_i\bigl(\omega_{i,d}c_i+(1-\omega_{i,d})c_{i-1}\bigr)B_{i,d-1} $$
である。$x\in[t_\mu,t_{\mu+1})$ で $B_{i,d-1}(x)\ne0$ となりうるのは $i=\mu-d+1,\dots,\mu$ だけで、これが $r=1$ の更新である。繰り返すと $s(x)=\sum_ic_i^{[r]}B_{i,d-r}(x)$ で、$r=d$ で $B_{\mu,0}(x)=1$ から結論を得る。$i\le\mu$、$i+d+1-r\ge\mu+1$ より $t_i\le x< t_{i+d+1-r}$ なので $0\le\lambda\le1$ である。$\square$

各段が凸結合なので、途中の値は $c_i$ の最小値と最大値の間に留まり、桁あふれや誤差の増幅が起こりにくい。
図: 左は開いた節点列の 3 次 B スプラインの基底関数。右は同じ節点列のスプラインで、1 つの係数を変えると 4 つの区間だけが変わることを示す 図: 左は開いた節点列の 3 次 B スプラインの基底関数。右は同じ節点列のスプラインで、1 つの係数を変えると 4 つの区間だけが変わることを示す

例題

等間隔の 3 次 B スプライン

問い:$M_3$(節点 $0,1,2,3,4$)の値を求める。
使う公式:定義の漸化式、prop-bsp-support。
答え:$M_3(1)=\frac16$、$M_3(2)=\frac23$、$M_3(3)=\frac16$、$M_3(\frac12)=\frac1{48}\approx0.02083$、$M_3(\frac32)=\frac{23}{48}\approx0.47917$ である。整数点の値の和は $1$ で、cor-bsp-unity と合う。

式を開く

$[0,1)$ で $\frac{x^3}6$、$[1,2)$ で $\frac{-3x^3+12x^2-12x+4}6$ で、$[2,4)$ は $M_3(4-x)=M_3(x)$ で与えられる。


整数点の値が $\frac16,\frac46,\frac16$ なので、$s=\sum_ic_iM_3(\cdot-i+2)$ の整数点の値を与える補間は三重対角の方程式 $\frac16c_{k-1}+\frac46c_k+\frac16c_{k+1}=y_k$ になる。スプライン補間 の等間隔の式の係数 $1,4,1$ と同じである。

開いた節点列の 2 次 B スプラインと de Boor の手順

問い:節点列 $0,0,0,1,2,2,2$($d=2$、$n=4$)で、$c=(1,3,2,4)$ の $s(\frac32)$ を求める。
使う公式:prop-bsp-deboor、cor-bsp-unity。
答え:$s(\frac32)=\frac{21}8=2.625$ である。Greville 点は $0,\frac12,\frac32,2$ である。

途中の計算を開く

$x=\frac32$ は $[t_4,t_5)=[1,2)$ にあり、$\mu=4$ である。$c^{[0]}=(c_2,c_3,c_4)=(3,2,4)$。$r=1$:$\lambda=\frac{3/2-0}{2-0}=\frac34$ で $c_3^{[1]}=\frac14\cdot3+\frac34\cdot2=\frac94$、$\lambda=\frac{3/2-1}{2-1}=\frac12$ で $c_4^{[1]}=3$。$r=2$:$\lambda=\frac12$ で $c_4^{[2]}=\frac12\cdot\frac94+\frac12\cdot3=\frac{21}8$。直接の値は $B_{2,2}=\frac18$、$B_{3,2}=\frac58$、$B_{4,2}=\frac14$ で、$\frac38+\frac54+1=\frac{21}8$ である。

内部の節点がないとき

問い:節点列 $0,0,0,0,1,1,1,1$ の $B_{i,3}$ を求める。
使う公式:thm-bsp-basis($L=0$)、thm-bsp-marsden。
答え:$B_{i,3}(x)=\binom3{i-1}x^{i-1}(1-x)^{4-i}$($i=1,\dots,4$)で、Bernstein 多項式である。$x=\frac14$ の値は $\frac{27}{64},\frac{27}{64},\frac9{64},\frac1{64}$ で、和 $\sum_ic_iB_{i,3}$ は Bézier 曲線の式である。

補間が解ける点と解けない点

問い:節点 $0,1,\dots,6$、$d=2$、$n=4$ で、$\tau=(\frac12,\frac52,\frac72,\frac{11}2)$ と $\tau=(\frac12,1,\frac32,2)$ の行列式を調べる。
使う公式:thm-bsp-sw。
答え:前者は $t_i<\tau_i< t_{i+3}$ を満たし、$\det A=\frac{35}{4096}\approx0.00854$ である。後者は $\tau_4=2\le t_4=3$ で条件を満たさず、$\det A=0$ である(第 $1\sim4$ 行に $B_{4,2}$ の成分がない)。

使える条件と反例

外す条件反例成り立たなくなること
$x\in I$節点 $0,1,2,3$、$d=1$、$n=2$ の $x=\frac12$cor-bsp-unity:和は $\frac12$ で $1$ でない
内部の節点が単純$d=2$、節点列 $0,0,0,1,1,1,2,2,2$prop-bsp-smooth:$B_{3,2}$ は $x=1$ で $1$ から $0$ へ跳ぶ
内部の節点が単純$d=2$、節点列 $0,0,0,1,1,2,2,2$連続だが $x=1$ で傾きが $2$ から $-2$ へ跳び、$C^1$ 級でない
$t_i<\tau_i< t_{i+d+1}$ex-bsp-sw の $\tau=(\frac12,1,\frac32,2)$thm-bsp-sw:$\det A=0$
右端を左極限で補う開いた節点列の $x=b$定義のままでは全部 $0$ で、cor-bsp-unity も thm-bsp-basis も成り立たない
反例の確認

$I$ の外:節点 $0,1,2,3$、$d=1$ なら $I=[1,2)$ である。$x=\frac12$ では $B_{1,1}(x)=\frac12$、$B_{2,1}(x)=0$ である。
重複した節点:節点列 $0,0,0,1,1,1,2,2,2$ では、$[0,1)$ で $B_{3,2}(x)=x^2$、$[1,2)$ で $B_{4,2}(x)=(2-x)^2$ である。$B_{3,2}$ の左極限は $1$ で、$x=1$ の値は $0$ である。重複度 $2$ の節点列 $0,0,0,1,1,2,2,2$ では、$B_{3,2}$ は $[0,1)$ で $x^2$、$[1,2)$ で $(2-x)^2$ の連続な関数である。

よくある誤り

誤り正しくはなぜ
次数と階数を取り違える次数 $d$ は階数 $d+1$。cubic は次数 $3$、階数 $4$def-bsp-bspline
台の節点の数を $d+1$ 個と数える節点は $d+2$ 個、節点区間は $d+1$ 個prop-bsp-support
基底の個数を節点の個数と同じだと思う全節点が $n+d+1$ 個なら基底は $n$ 個def-bsp-bspline
制御点の上を曲線が通ると思う一般には通らない。開いた節点列の両端では通るcor-bsp-unity
分母が $0$ の項で計算を止めるその項は $0$ とするdef-bsp-bspline
補間点を自由に選べると思う点は節点と $t_i<\tau_i< t_{i+d+1}$ の関係が要るthm-bsp-sw

演習

2 次の基数 B スプライン

$M_2$(節点 $0,1,2,3$)を区間ごとに書き、最大値を求めよ。

解答を開く

$[0,1)$ で $\frac{x^2}2$、$[1,2)$ で $\frac{-2x^2+6x-3}2$、$[2,3)$ で $\frac{(3-x)^2}2$ である。$[1,2)$ の頂点は $x=\frac32$ で、最大値は $\frac34$ である。

2 次式の再現

$d\ge2$ のとき、$x\in I$ で $x^2$ を $\sum_ic_iB_{i,d}(x)$ の形に書く係数を求めよ。

解答を開く

thm-bsp-marsden の $y^{d-2}$ の係数を比べる。左辺は $\binom d2x^2$、右辺は $\sum_ie_2(t_{i+1},\dots,t_{i+d})B_{i,d}(x)$($e_2$ は基本対称式)なので、$c_i=e_2(t_{i+1},\dots,t_{i+d})\big/\binom d2$ である。$\square$

補足

  • 切断べきとの関係:単純な節点では、$B_{i,d}$ は切断べき $s\mapsto(s-x)_+^d$ の節点 $t_i,\dots,t_{i+d+1}$ での差分商の $t_{i+d+1}-t_i$ 倍に等しい。この記事では証明しない。差分商については Newton補間 を見よ。
  • 回帰スプライン:データの点より少ない節点の $B_{i,d}$ を基底にして最小二乗法で当てはめる方法で、行列が帯状になるので速い(ESL17 pp. 187–189)。節点を全部のデータ点に置いて罰則を付けると 平滑化スプライン になる。
  • 複数の変数:1 変数の B スプラインの積(テンソル積)で曲面を表す(ESL17 §5.7)。

関連項目

参考文献

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