logo

ニュートンの前進差分公式の導出 📂数値解析

ニュートンの前進差分公式の導出

式

異なるx0,⋯ ,xnx_{0} , \cdots , x_{n}のデータ(x0,f(x0)),⋯ ,(xn,f(xn))(x_{0}, f(x_{0} )) , \cdots , (x_{n} , f( x_{n} ) )について pn(x)=∑i=0nf[x0,⋯ ,xi]∏j=0i−1(x−xj) p_{n} (x) =\sum_{i=0}^{n} f [ x_{0} , \cdots , x_{i} ] \prod_{j=0}^{i-1} (x - x_{j} )

説明

複雑に見えるが、n=0,1,2n=0,1,2について実際に展開してみると、次のように単純に表される。 p0(x)=f(x0)p1(x)=f(x0)+(x−x0)f[x0,x1]p2(x)=f(x0)+(x−x0)f[x0,x1]+(x−x0)(x−x1)f[x0,x1,x2] \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*} ニュートンの差分公式は、差分法を使って多項式補間を表す方法で、ラグランジュの公式に比べて複雑に見えるが、データが追加されるにつれて更新をする必要がある場合は、はるかに便利だ。ニュートンの差分公式を再帰的に表現すると pn(x)=pn−1(x)+f[x0,⋯ ,xn]∏i=0n−1(x−xi) p_{n} (x) = p_{n-1}(x) + f[x_{0} , \cdots , x_{n} ] \prod_{i=0}^{n-1} (x - x_{i}) のような形になるが、ラグランジュの公式しかなかったら、pn−1p_{n-1}をすでに知っているにも関わらず、また(n+1)×(n+1)(n+1) \times (n+1)サイズの逆行列を計算しなければならない手間がある。どのような計算方法であれ、結果自体はラグランジュの公式と全く同じであるため、追加されるデータが少ない場合はニュートンの差分公式が便利に使える。

また、ラグランジュの公式と正確に同じでありながらも異なる形を持っていることを利用して、差分に関する様々な便利な定理を証明できる。

導出

戦略: pnp_{n}とpn−1p_{n-1}の差をCCとすると、pnp_{n}とCCの最高次項の係数は同じでなければならないので、CCの係数だけを計算して、間接的に再帰式を導出する。

pn(x)=pn−1(x)+C(x) p_{n}(x) = p_{n-1}(x) + C(x) とした場合、deg⁡C=n\deg C = nであり、i=0,⋯ ,(n−1)i= 0, \cdots, (n-1)に対して pn(xi)=f(xi)=pn−1(xi) p_{n}(x_{i}) = f(x_{i}) = p_{n-1}(x_{i}) であるため、ある定数an≠0a_{n} \ne 0について C(x)=an(x−x0)⋯(x−xn−1) C (x) = a_{n} (x - x_{0}) \cdots (x - x_{n-1}) のように表される。pnp_{n}とCCの最高次項は同じであるため、an=f[x0,⋯ ,xn]a_{n} = f [ x_{0} , \cdots , x_{n}]が成立することを示せばよい。データ{x0,⋯ ,xk}\left\{ x_{0}, \cdots , x_{k} \right\}からxkx_{k}を抜いたデータ{x0,⋯ ,xk−1}\left\{ x_{0}, \cdots , x_{k-1} \right\}で得られた多項式補間をLk−1(x)L_{k-1}(x)、x0x_{0}を抜いたデータ{x1,⋯ ,xk}\left\{ x_{1}, \cdots , x_{k} \right\}で得られた多項式補間をRk−1(x)R_{k-1}(x)としよう。各アルファベットは左Leftと右Rightを意味する。これに対してpkp_{k}を次のように置く。 pk(x):=(x−x0)Rk−1(x)−(x−xk)Lk−1(x)xk−x0 p_{k}(x) := {{ (x-x_{0}) R_{k-1} (x) - (x-x_{k}) L_{k-1} (x) } \over { x_{k} - x_{0} }} すると、i=1,⋯ ,k−1i=1,\cdots , k-1について pk(x0)=Lk−1(x0)=f(x0) p_{k}(x_{0}) = L_{k-1} (x_{0}) = f(x_{0})

pk(xi)=Lk−1(xi)=Rk−1(xi)=f(xi) p_{k}(x_{i}) = L_{k-1} (x_{i}) = R_{k-1} (x_{i}) = f(x_{i})

pk(xk)=Rk−1(xk)=f(xk) p_{k}(x_{k}) = R_{k-1} (x_{k}) = f(x_{k}) したがって、pkp_{k}は与えられたデータをうまく補間することが保証される。pkp_{k}の最高次項の係数をaka_{k}とすると、ak=f[x0,⋯ ,xk]a_k = f[ x_{0} , \cdots , x_{k} ]が数学的帰納法で示される。

k=1k=1のとき p1(x)=(x−x0)f(x1)−(x−xk)f(x0)(x)x1−x0 p_{1}(x) = {{ (x-x_{0}) f(x_{1}) - (x-x_{k}) f(x_{0}) (x) } \over { x_{1} - x_{0} }} であるため、最高次項xxの係数は a1=f(x1−x0)x1−x0=f[x0,x1] a_{1} = {{ f(x_{1} - x_{0}) } \over { x_{1} - x_{0} }} = f[x_{0},x_{1}] k>1k > 1のときak−1=f[x0,⋯ ,xk−1]a_{k-1} = f[ x_{0} , \cdots , x_{k-1} ]が成立すると仮定すると、Lk−1L_{k-1}の最高次項の係数はf[x0,⋯ ,xk−1]f[ x_{0} , \cdots , x_{k-1} ]であり、Rk−1R_{k-1}の最高次項の係数はf[x1,⋯ ,xk]f[ x_{1} , \cdots , x_{k} ]である。pkp_{k}の分数形を解くと pk(x)=Rk−1(x)−Lk−1(x)xk−x0x+xkLk−1(x)−x0Rk−1(x)xk−x0 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} }} したがって、pk(x)p_{k}(x)の最高次項の係数は ak=f[x1,⋯ ,xk]−f[x0,⋯ ,xk−1]xk−x0=f[x0,⋯ ,xk] 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} ] 数学的帰納法により、すべての自然数 nnに対して an=f[x0,⋯ ,xn] a_{n} = f [ x_{0} , \cdots , x_{n}]

■