補間と近似

n次多項式にはちょうどn+1個の自由な係数があり、n+1個の点の値を固定することはちょうどそれだけの自由度を使い切る——多くも少なくもない——ため、1つの解が入る余地はあっても、異なる2つの解が入る余地はない。

ステップ1(存在)。ラグランジュ構成 $P(x) = \sum_{i=0}^{n} y_i L_i(x)$($L_i(x) = \prod_{j\ne i} \dfrac{x-x_j}{x_i-x_j}$)はすでにすべての $k$ について $P(x_k)=y_k$ を満たす。なぜなら $L_i(x_k)$ は $i=k$ のとき $1$、それ以外のとき $0$ となり、和は単一の項 $y_k \cdot 1 = y_k$ に潰れるからである。よって少なくとも1つの有効な $P$ が存在し、各 $L_i$ はちょうど次数 $n$($n$ 個の1次因子の積)を持つので、$P$ の次数は $n$ 以下である。

ステップ2(2つの解を仮定する)。$Q$ を、すべての $i$ について $Q(x_i)=y_i$ を満たす次数 $n$ 以下の別の任意の多項式とする。差 $D(x) = P(x) - Q(x)$ を考える。$P$ と $Q$ がともに次数 $n$ 以下なので、$D$ もそうである。

ステップ3(差の根を数える)。各節点 $x_i$ に対し $D(x_i) = P(x_i)-Q(x_i) = y_i - y_i = 0$。$n+1$ 個の相異なる節点 $x_0, x_1, \dots, x_n$ があるので、$D$ は少なくとも $n+1$ 個の相異なる根を持つ。

ステップ4(Dが恒等的に0であることを示す)。次数 $n$ 以下の非零多項式は多くとも $n$ 個の根しか持てない(各根は1つの1次因子を与え、次数 $n$ の多項式はそのような因子を $n$ 個より多く含みえない)。$D$ は $n+1$ 個の根を持ち、これはその次数が許す数を超えるので、$D$ が零多項式でない限り矛盾する。よって $D(x)\equiv0$、すなわち $Q=P$ である。したがってステップ1で見つけた補間多項式は唯一である。

補間多項式は節点ではfと正確に一致するが、節点の間ではfについて何も知らない。そのため残りの誤差はすべての節点で消えなければならない——まさに積の項が強制すること——であり、それは次数nの多項式が捉えきれないfの曲がり具合を測る残りの導関数によってスケールされる。

ステップ1(巧妙な補助関数)。節点のいずれでもない点 $x$ を固定する(節点であれば誤差は自明に $0$)。$w(t) = \prod_{i=0}^{n} (t - x_i)$ とし、定数 $c = \dfrac{f(x)-P(x)}{w(x)}$($w(x)\ne0$ なので well-defined)を定義する。補助関数 $g(t) = f(t) - P(t) - c\, w(t)$ を定義する。

ステップ2(gの根を数える)。各節点 $x_i$ において、補間の性質より $f(x_i)-P(x_i)=0$、かつ $w$ の定義より $w(x_i)=0$ なので、すべての $n+1$ 個の節点で $g(x_i)=0$ となる。また $c$ の選び方により $g(x) = f(x)-P(x) - c\,w(x) = f(x)-P(x) - [f(x)-P(x)] = 0$ である。よって $g$ は $n+2$ 個の相異なる根を持つ:$n+1$ 個の節点と $x$ 自身である。

ステップ3(ロルの定理を繰り返し適用する)。$g$ の連続する根の各組の間($n+2$ 個の根の間に $n+1$ 個のそのような間隔がある)で、ロルの定理により $g'$ が消える点が存在するので、$g'$ は少なくとも $n+1$ 個の根を持つ。この議論を $g', g'', \dots$ に繰り返し適用すると、微分するたびに根が1つずつ失われるので、$n+1$ 回適用した後、$g^{(n+1)}$ はその区間内に少なくとも1つの根 $\xi$ を持つ。

ステップ4(微分して誤差を解く)。$P$ の次数は $n$ 以下なので、その $(n+1)$ 階導関数は $0$ である;また $w$ は次数 $n+1$ のモニック多項式なので、すべての $t$ について $w^{(n+1)}(t) = (n+1)!$ である。$g$ を微分すると $g^{(n+1)}(t) = f^{(n+1)}(t) - 0 - c\,(n+1)!$ となり、$g^{(n+1)}(\xi)=0$ とおくと $c = \dfrac{f^{(n+1)}(\xi)}{(n+1)!}$ が得られる。$c=\dfrac{f(x)-P(x)}{w(x)}$ を思い出して誤差について解くと、まさに $f(x) - P(x) = \dfrac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{i=0}^{n} (x - x_i)$ が得られる。

多くの点を通る単一の高次多項式は波打つ傾向があるが、多くの緩やかな3次片をつなぎ合わせ、継ぎ目で滑らかに一致することだけを要求すると、激しい振動なしにデータに適合するのにちょうど十分な自由度が得られ、自然境界条件は系全体を解けるようにするために必要なちょうど2つの追加の方程式を与える。

ステップ1(未知数:各節点での2階導関数)。$i=0,\dots,n$ について $M_i = S''(x_i)$ とする。自然境界条件により直ちに $M_0=0$ と $M_n=0$ が定まり、残り $n-1$ 個の未知数 $M_1,\dots,M_{n-1}$ を決定すればよい。

ステップ2(各3次片をM値から再構成する)。$[x_i,x_{i+1}]$ 上では、$S$ が3次なので $S''$ は線形であり、$(x_i,M_i)$ と $(x_{i+1},M_{i+1})$ を通る直線でなければならない。この線形関数を2回積分し、$S(x_i)=y_i$ と $S(x_{i+1})=y_{i+1}$ を用いて2つの積分定数を固定すると、その区間上の $S$ が $M_i, M_{i+1}, y_i, y_{i+1}$ と間隔 $h_i=x_{i+1}-x_i$ によって完全に決まる。よってすべての $M_i$ が分かれば $S$ は完全に決まる。

ステップ3(傾きを一致させると線形方程式系が得られる)。構成により $S$ と $S''$ はすでに各節点で連続である。各内部節点 $x_i$($i=1,\dots,n-1$)で1階導関数 $S'$ も両側から一致することを要求すると、内部節点ごとに連続する3つの未知数を関連づける線形方程式が1つ得られる:$h_{i-1} M_{i-1} + 2(h_{i-1}+h_i) M_i + h_i M_{i+1} = 6\left(\dfrac{y_{i+1}-y_i}{h_i} - \dfrac{y_i-y_{i-1}}{h_{i-1}}\right)$。これにより $n-1$ 個の未知数 $M_1,\dots,M_{n-1}$($M_0=M_n=0$ を用いて)についての $n-1$ 個の線形方程式が得られる。

ステップ4(系は唯一の解を持つ)。この系の係数行列は三重対角であり、対角成分は $2(h_{i-1}+h_i)$、非対角成分は $h_{i-1}$ と $h_i$ である;すべての間隔について $h_i>0$ なので $2(h_{i-1}+h_i) > h_{i-1}+h_i$ が成り立ち、この行列は狭義優対角であり、狭義優対角行列は常に正則である。よって $M_1,\dots,M_{n-1}$ についての線形系はちょうど1つの解を持ち、ステップ2によりこれはちょうど1つのスプライン $S$ を定めるので、存在と一意性の両方が証明される。