📂数値解析

多項式補間

定義 ¹

異なる$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 )$$

■