多項式補間
定義 1
異なる$x_{0} , \cdots , x_{n}$のデータ$(x_{0}, y_{0}) , \cdots , (x_{n} , y_{n})$について、$p (x_{i} ) = y_{i}$と$\deg p \le n$を満たす多項式関数$p$を多項式補間polynomial Interpolationという。
定理
存在性と一意性
- [1]: 与えられたデータに対し、 $p$は一意に存在する。
ラグランジュの公式
- [2]: $$p_{n} (x) = \sum_{i=0}^{n} y_{i} l_{i} (X)$$
ニュートンの差分公式
- [3]: $$p_{n} (x) = f(x_{0}) + \sum_{i=1}^{n} f [ x_{0} , \cdots , x_{i} ] \prod_{j=0}^{i-1} (x - x_{j} )$$
誤差解析
- [4]: $(n+1)$回微分可能な$f : \mathbb{R} \to \mathbb{R}$とある$\xi \in \mathscr{H} \left\{ x_{0} , \cdots , x_{n} \right\}$に対し、$f$の多項式補間$p_{n}$はある$t \in \mathbb{R}$に対して次を満たす。$$\displaystyle f(t) - p_{n} (t) = {{ (t - x_{0}) \cdots (t - x_{n}) } \over { (n+1)! }} f^{(n+1)} ( \xi )$$
- $\mathscr{H} \left\{ a,b,c, \cdots \right\}$は$a,b,c, \cdots$を含む最小の区間を表す。
説明
多項式補間は韓国語で多項式補間法と簡化される。
条件 $\deg p \le n$
$\deg p \le n$という条件は、$p$が$\deg p = n$を満たす保証が常にあるわけではないことを意味する。例えば$n=2$の時、上のように3点が一直線上にある場合、$(n+1)=3$個の点を通る$p_{2} (x) = a_{2} x^{2} + a_{1} x + a_{0}$は存在しないが、それよりも低い次数の$p_{1} (x) = a_{1} x + a_{0}$は存在する。これは実際に$p_{2} (x) = a_{2} x^{2} + a_{1} x + a_{0}$を見つけたが$a_{2} = 0$の場合を意味する。
ラグランジュの公式とニュートンの差分公式は同じである
公式[2]と[3]は違うように見えても、実際には[1]によって同じであることがわかる。本質的に2つの公式の違いは$p_{n}$をどう表すかの差に過ぎず、機能的な違いは新しいデータが追加された時にニュートンの差分公式が更新しやすいという点だけである。
実際の関数との誤差
定理[4]は、ある関数$f$を補間する$p_{n}$が$f$とどの程度違うかを示す。通常の場合には$(n+1)!$の発散速度は非常に速いため、データが多ければ多いほど補間$p_{n}$の正確性は上がる。しかし、この公式は特に収束性を論じるわけではないことに注意が必要だ。簡単な例で$t$が$\mathscr{H} \left\{ x_{0} , \cdots , x_{n} \right\}$から非常に遠い場所にある場合を考えることができる。また、$f$がそれほど良くなくて微分するたびに値が大きくなり、それが更に$(n+1)!$の発散速度よりも速い場合、どんなに変になるかだってある。
証明
[1]
戦略: $(n+1)$個の連立方程式を行列で表し、逆行列の存在性と一意性を同時に持ってくる。
全ての$i = 0, \cdots , n$に対して$y_{i} = p_{n} (x_{i}) = a_{0} + a_{1} x_{i} + \cdots + a_{n} x_{i}^{n}$を満たす$p_{n}$の係数$a_{0} , a_{1} , \cdots , a_{n}$が一意であることを示せば良い。 $$ \mathbf{y} := \begin{bmatrix} y_{0} \\ y_{1} \\ \vdots \\ y_{n} \end{bmatrix}, X := \begin{bmatrix} 1 & x_{0} & \cdots & x_{0}^{n} \\ 1 & x_{1} & \cdots & x_{1}^{n} \\ \vdots & \vdots & \ddots & \vdots \\ 1 & x_{n} & \cdots & x_{n}^{n} \end{bmatrix} , \mathbf{a} := \begin{bmatrix} a_{0} \\ a_{1} \\ \vdots \\ a_{n} \end{bmatrix} $$と定義し、連立方程式を行列で表すと $$ \begin{bmatrix} y_{0} \\ y_{1} \\ \vdots \\ y_{n} \end{bmatrix} = \begin{bmatrix} 1 & x_{0} & \cdots & x_{0}^{n} \\ 1 & x_{1} & \cdots & x_{1}^{n} \\ \vdots & \vdots & \ddots & \vdots \\ 1 & x_{n} & \cdots & x_{n}^{n} \end{bmatrix} \begin{bmatrix} a_{0} \\ a_{1} \\ \vdots \\ a_{n} \end{bmatrix} $$ 今、$\mathbf{y} = X \mathbf{a}$を満たす解$\mathbf{a}$を見つける問題に変わった。
ヴァンデルモンド行列の行列式: $X$の行列式は$\displaystyle \det X = \prod_{1 \le i < j \le n } (x_{j} - x_{i})$
仮定から$x_{0} , \cdots , x_{n}$は異なるので$\det X \ne 0$であり、$X^{-1}$が存在する。したがって、$\mathbf{a} = X^{-1} \mathbf{y}$も存在する。一方で、与えられた行列に対する逆行列は一意なので、$\mathbf{a}$も一意である。
■
[2]
■
[3]
■
[4]
戦略: 新しいダミー関数を定義し、それらの微分可能性を利用して直接的な計算を回避する。設定が複雑なので、実際には後ろから理解するほうが楽である。
Claim: $E (x) := f(x) - p_{n} (X)$に対して次が成立する。 $$ E(t) = {{ (t - x_{0}) \cdots (t - x_{n}) } \over { (n+1)! }} f^{(n+1)} ( \xi ) $$
Part 1.
まず、$t$がノードポイント$x_{0} , \cdots , x_{n}$と同じなら自明に成立するので、$t$がこれらのノードポイントと異なると仮定する。 $$ \begin{align*} \Psi (x) :=& (x - x_{0} ) (x - x_{1}) \cdots (x - x_{n}) \\ G (x) :=& E(x) - {{ \Psi (x) } \over { \Psi (t) }} E(t) \end{align*} $$ 上記のように新しい関数を定義すると、$f$、$p_{n}$、$\Psi$が$(n+1)$回微分可能であるため、$G$も$(n+1)$回微分可能である。
Part 2.
$x = x_{i}$を$G$に代入すると$E(x_{i}) = f(x_{i}) - p_{n} (x_{i}) = 0$であり、$\Psi (x_{i} ) = 0$なので $$ G(x_{i}) = E(x_{i} ) - {{ \Psi (x_{i}) } \over { \Psi (t) }} E(t) = 0 $$ $x = t$を$G$に代入すると$\displaystyle {{ \Psi (t) } \over { \Psi (t) }} = 1$なので $$ G(t) = E(t) - E(t) =0 $$ したがって、$G$は$(n+2)$個の異なる零点$x_{0} , \cdots , x_{n} , t$を持つ。
Part 3.
便宜上$x_{n+1} :=t$としよう。
ロルの定理: 関数$f(x)$が$[a,b]$で連続であり、$(a,b)$で微分可能であり、$f(a)=f(b)$ならば、$f ' (c)=0$を満たす$c$が$(a,b)$に少なくとも一つ存在する。
全ての$i=0, \cdots , n$に対して $$ G(x_{i}) = 0 = G(x_{i+1}) $$ なのでロルの定理により$g ' ( x’_{i}) = 0$を満たす$x'_{i} \in \mathscr{H} \left\{ x_{i} , x_{i+1} \right\}$が存在し、同様に全ての$i=0, \cdots , (n-1)$に対して $$ g ' (x’_{i}) = 0 = g ' (x’_{i+1}) $$ なのでロルの定理により$G''( x’’_{i}) = 0$を満たす$x''_{i} \in \mathscr{H} \left\{ x’_{i} , x’_{i+1} \right\}$が存在する。このように帰納的にロルの定理を$(n+1)$回使用して $$ G^{(n+1)} ( \xi ) = 0 $$ を満たす$\xi \in \mathscr{H} \left\{ x_{0} , \cdots , x_{n+1} \right\}$の存在を保証することができる。
一方で、$p_{n}$は$n$次の多項式なので $$ E^{(n+1)} (x) = f^{(n+1)} ( x) $$ $\Psi$の最高次項は$x^{n+1}$であるため $$ \Psi^{(n+1)} (x) = (n+1)! $$ $\displaystyle G (x) = E(x) - {{ \Psi (x) } \over { \Psi (t) }} E(t)$の両辺を$x$に対して$(n+1)$回微分すると $$ G^{(n+1)} (x) = f^{(n+1)} ( x) - {{ (n+1)! } \over { \Psi (t) }} E(t) $$ $x=\xi$を$G^{(n+1)}$と$f^{(n+1)}$に代入すると $$ 0 = f^{(n+1)} ( \xi ) - {{ (n+1)! } \over { \Psi (t) }} E(t) $$ $E (t) = f(t) - p_{n} (t)$なので、次を得る。 $$ f(t) - \sum_{j=0}^{n} f( x_{j} ) l_{j} (t) = {{ (t - x_{0}) \cdots (t - x_{n}) } \over { (n+1)! }} f^{(n+1)} ( \xi ) $$
■
Atkinson. (1989). 数値解析入門(第2版): p131. ↩︎