ニュートンの前進差分公式の導出
式
異なる$x_{0} , \cdots , x_{n}$のデータ$(x_{0}, f(x_{0} )) , \cdots , (x_{n} , f( x_{n} ) )$について $$ p_{n} (x) =\sum_{i=0}^{n} f [ x_{0} , \cdots , x_{i} ] \prod_{j=0}^{i-1} (x - x_{j} ) $$
説明
複雑に見えるが、$n=0,1,2$について実際に展開してみると、次のように単純に表される。 $$ \begin{align*} p_{0} (x) =& f(x_{0}) \\ p_{1} (x) =& f( x_{0} ) + (x - x_{0} ) f [ x_{0} , x_{1} ] \\ p_{2} (x) =& f( x_{0} ) + (x - x_{0} ) f [ x_{0} , x_{1} ] + ( x - x_{0} ) ( x - x_{1} ) f [ x_{0} , x_{1} , x_{2} ] \end{align*} $$ ニュートンの差分公式は、差分法を使って多項式補間を表す方法で、ラグランジュの公式に比べて複雑に見えるが、データが追加されるにつれて更新をする必要がある場合は、はるかに便利だ。ニュートンの差分公式を再帰的に表現すると $$ p_{n} (x) = p_{n-1}(x) + f[x_{0} , \cdots , x_{n} ] \prod_{i=0}^{n-1} (x - x_{i}) $$ のような形になるが、ラグランジュの公式しかなかったら、$p_{n-1}$をすでに知っているにも関わらず、また$(n+1) \times (n+1)$サイズの逆行列を計算しなければならない手間がある。どのような計算方法であれ、結果自体はラグランジュの公式と全く同じであるため、追加されるデータが少ない場合はニュートンの差分公式が便利に使える。
また、ラグランジュの公式と正確に同じでありながらも異なる形を持っていることを利用して、差分に関する様々な便利な定理を証明できる。
導出
戦略: $p_{n}$と$p_{n-1}$の差を$C$とすると、$p_{n}$と$C$の最高次項の係数は同じでなければならないので、$C$の係数だけを計算して、間接的に再帰式を導出する。
$$ p_{n}(x) = p_{n-1}(x) + C(x) $$とした場合、$\deg C = n$であり、$i= 0, \cdots, (n-1)$に対して $$ p_{n}(x_{i}) = f(x_{i}) = p_{n-1}(x_{i}) $$ であるため、ある定数$a_{n} \ne 0$について $$ C (x) = a_{n} (x - x_{0}) \cdots (x - x_{n-1}) $$ のように表される。$p_{n}$と$C$の最高次項は同じであるため、$a_{n} = f [ x_{0} , \cdots , x_{n}]$が成立することを示せばよい。データ$\left\{ x_{0}, \cdots , x_{k} \right\}$から$x_{k}$を抜いたデータ$\left\{ x_{0}, \cdots , x_{k-1} \right\}$で得られた多項式補間を$L_{k-1}(x)$、$x_{0}$を抜いたデータ$\left\{ x_{1}, \cdots , x_{k} \right\}$で得られた多項式補間を$R_{k-1}(x)$としよう。各アルファベットは左Leftと右Rightを意味する。これに対して$p_{k}$を次のように置く。 $$ p_{k}(x) := {{ (x-x_{0}) R_{k-1} (x) - (x-x_{k}) L_{k-1} (x) } \over { x_{k} - x_{0} }} $$ すると、$i=1,\cdots , k-1$について $$ p_{k}(x_{0}) = L_{k-1} (x_{0}) = f(x_{0}) $$
$$ p_{k}(x_{i}) = L_{k-1} (x_{i}) = R_{k-1} (x_{i}) = f(x_{i}) $$
$$ p_{k}(x_{k}) = R_{k-1} (x_{k}) = f(x_{k}) $$ したがって、$p_{k}$は与えられたデータをうまく補間することが保証される。$p_{k}$の最高次項の係数を$a_{k}$とすると、$a_k = f[ x_{0} , \cdots , x_{k} ]$が数学的帰納法で示される。
$k=1$のとき $$ p_{1}(x) = {{ (x-x_{0}) f(x_{1}) - (x-x_{k}) f(x_{0}) (x) } \over { x_{1} - x_{0} }} $$ であるため、最高次項$x$の係数は $$ a_{1} = {{ f(x_{1} - x_{0}) } \over { x_{1} - x_{0} }} = f[x_{0},x_{1}] $$ $k > 1$のとき$a_{k-1} = f[ x_{0} , \cdots , x_{k-1} ]$が成立すると仮定すると、$L_{k-1}$の最高次項の係数は$f[ x_{0} , \cdots , x_{k-1} ]$であり、$R_{k-1}$の最高次項の係数は$f[ x_{1} , \cdots , x_{k} ]$である。$p_{k}$の分数形を解くと $$ p_{k}(x) = {{ R_{k-1} (x) - L_{k-1} (x) } \over { x_{k} - x_{0} }} x + {{ x_{k} L_{k-1} (x) - x_{0} R_{k-1} (x) } \over { x_{k} - x_{0} }} $$ したがって、$p_{k}(x)$の最高次項の係数は $$ a_{k} = {{ f[ x_{1} , \cdots , x_{k} ]- f[ x_{0} , \cdots , x_{k-1} ] } \over { x_{k} - x_{0} }} = f[ x_{0} , \cdots , x_{k} ] $$ 数学的帰納法により、すべての自然数 $n$に対して $$ a_{n} = f [ x_{0} , \cdots , x_{n}] $$
■