相違点の分割

数学において、差分商は、歴史的には対数表や三角関数の計算に使用されてきたアルゴリズムである。^[要出典]チャールズ・バベッジの差分機関は、初期の機械式計算機であり、このアルゴリズムを動作に利用するように設計された。^[1]

差商法は再帰的な 除算プロセスです。データ ポイントのシーケンスが与えられると、この方法では、ニュートン形式でこれらのポイントの補間多項式の係数を計算します。 ${\displaystyle (x_{0},y_{0}),\ldots ,(x_{n},y_{n})}$

n  + 1 個のデータ ポイント がペアごとに異なると仮定すると、前方分割差は次のように定義されます。 $${\displaystyle (x_{0},y_{0}),\ldots ,(x_{n},y_{n})}$$${\displaystyle x_{k}}$$${\displaystyle {\begin{aligned}{\mathopen {[}}y_{k}]&:=y_{k},&&k\in \{0,\ldots ,n\}\\{\mathopen {[}}y_{k},\ldots ,y_{k+j}]&:={\frac {[y_{k+1},\ldots ,y_{k+j}]-[y_{k},\ldots ,y_{k+j-1}]}{x_{k+j}-x_{k}}},&&k\in \{0,\ldots ,nj\},\ j\in \{1,\ldots ,n\}.\end{aligned}}}$$

計算の再帰プロセスをより明確にするために、分割された差を表形式にすることができます。表の列は上記のjの値に対応し、表の各エントリは、そのすぐ左下のエントリとすぐ左上のエントリの差を、対応するx値の差で割って計算されます。 $${\displaystyle {\begin{行列}x_{0}&y_{0}=[y_{0}]&&&\\&&[y_{0},y_{1}]&&\\x_{1}&y_{1}=[y_ {1}]&&[y_{0},y_{1},y_{2}]&\\&&[y_{1},y_{2}]&&[y_{ 0},y_{1},y_{2},y_{3}]\\x_{2}&y_{2}=[y_{2}]&&[y_{1},y_{2},y_{3 }]&\\&&[y_{2},y_{3}]&&\\x_{3}&y_{3}=[y_{3}]&&&\\\end{行列}}}$$

差商は値とに依存するが、表記法ではx値への依存性が隠されていることに注意してください。データ ポイントが関数fによって与えられる場合、 差商を表記法で書くことが あります。ノードx ₀、...、  x _n上の関数ƒの差商のその他の表記法は次のとおりです。 ${\displaystyle [y_{k},\ldots ,y_{k+j}]}$${\displaystyle x_{k},\ldots ,x_{k+j}}$${\displaystyle y_{k},\ldots ,y_{k+j}}$$${\displaystyle (x_{0},y_{0}),\ldots ,(x_{k},y_{n})=(x_{0},f(x_{0})),\ldots ,(x_{n},f(x_{n}))}$$$${\displaystyle f[x_{k},\ldots ,x_{k+j}]\ {\stackrel {\text{def}}{=}}\ [f(x_{k}),\ldots ,f(x_{k+j})]=[y_{k},\ldots ,y_{k+j}].}$$$${\displaystyle f[x_{k},\ldots,x_{k+j}]={\mathopen {[}}x_{0},\ldots,x_{n}]f={\mathopen {[}}x_{0},\ldots,x_{n};f]=D[x_{0},\ldots,x_{n}]f.}$$

と の最初のいくつかの値の差商: ${\displaystyle k=0}$${\displaystyle j}$$${\displaystyle {\begin{aligned}{\mathopen {[}}y_{0}]&=y_{0}\\{\mathopen {[}}y_{0},y_{1}]&={\ frac {y_{1}-y_{0}}{x_{1}-x_{0}}}\\{\mathopen {[}}y_{0},y_{1},y_{2}]&={\frac {{\mathopen {[}}y_{1},y_{2}]-{\mathopen {[}} y_{0},y_{1}]}{x_{2}-x_{0}}}={\frac {{\frac {y_{2}-y_{1}}{x_{2}-x_{1}}}-{\frac {y_{1}-y_{0}}{x_{1}-x_{0}}}}{x_{2}-x_{0}}}={\frac {y_{2}-y_{1} }{(x_{2}-x_{1})(x_{2}-x_{0})}}-{\frac {y_{1}-y_{0}}{(x_{1}-x_{0})(x_{2}-x_{0})}}\\{\mathopen {[}}y_{0}, y_{1},y_{2},y_{3}]&={\frac {{\mathopen {[}}y_{1},y_{2},y_{3}]-{\mathopen {[}}y_{0},y_{1},y_{2}]}{x_{3}-x_{0}}}\end{整列}}}$$

したがって、これらの用語を 2 列まで対応する表の形式は次のようになります。 $${\displaystyle {\begin{matrix}x_{0}&y_{0}&&\\&&{y_{1}-y_{0} \over x_{1}-x_{0}}&\\x_{1}&y_{1}&&{{y_{2}-y_{1} \over x_{2}-x_{1}}-{y_{1}-y_{0} \over x_{1}-x_{0}} \over x_{2}-x_{0}}\\&&{y_{2}-y_{1} \over x_{2}-x_{1}}&\\x_{2}&y_{2}&&\vdots \\&&\vdots &\\\vdots &&&\vdots \\&&\vdots &\\x_{n}&y_{n}&&\\\end{行列}}}$$

• 直線性 $${\displaystyle {\begin{aligned}(f+g)[x_{0},\dots ,x_{n}]&=f[x_{0},\dots ,x_{n}]+g[x_{0},\dots ,x_{n}]\\(\lambda \cdot f)[x_{0},\dots ,x_{n}]&=\lambda \cdot f[x_{0},\dots ,x_{n}]\end{aligned}}}$$
• ライプニッツの法則 $${\displaystyle (f\cdot g)[x_{0},\dots ,x_{n}]=f[x_{0}]\cdot g[x_{0},\dots ,x_{n}]+f[x_{0},x_{1}]\cdot g[x_{1},\dots ,x_{n}]+\dots +f[x_{0},\dots ,x_{n}]\cdot g[x_{n}]=\sum _{r=0}^{n}f[x_{0},\ldots ,x_{r}]\cdot g[x_{r},\ldots ,x_{n}]}$$
• 差商は対称的である。が順列であるならば${\displaystyle \sigma :\{0,\dots ,n\}\to \{0,\dots ,n\}}$$${\displaystyle f[x_{0},\dots ,x_{n}]=f[x_{\sigma (0)},\dots ,x_{\sigma (n)}]}$$
• ニュートン形式の多項式補間： が次数の多項式関数であり、 が差の商である場合、${\displaystyle P}$${\displaystyle \leq n}$${\displaystyle p[x_{0},\dots ,x_{n}]}$$${\displaystyle P_{n-1}(x)=p[x_{0}]+p[x_{0},x_{1}](x-x_{0})+p[x_{0},x_{1},x_{2}](x-x_{0})(x-x_{1})+\cdots +p[x_{0},\ldots ,x_{n}](x-x_{0})(x-x_{1})\cdots (x-x_{n-1})}$$
• が次数 の多項式関数である場合、${\displaystyle p}$${\displaystyle <n}$$${\displaystyle p[x_{0},\dots ,x_{n}]=0.}$$
• 差分商の平均値定理: が n 回微分可能な場合、の最小値と最大値によって決まる開区間内の数値に対して。${\displaystyle f}$$${\displaystyle f[x_{0},\dots ,x_{n}]={\frac {f^{(n)}(\xi )}{n!}}}$$${\displaystyle \xi }$${\displaystyle x_{k}}$

差分商法は上三角行列に表すことができます。 $${\displaystyle T_{f}(x_{0},\dots ,x_{n})={\begin{pmatrix}f[x_{0}]&f[x_{0},x_{1}]&f[x_{0},x_{1},x_{2}]&\ldots &f[x_{0},\dots ,x_{n}]\\0&f[x_{1}]&f[x_{1},x_{2}]&\ldots &f[x_{1},\dots ,x_{n}]\\0&0&f[x_{2}]&\ldots &f[x_{2},\dots ,x_{n}]\\\vdots &\vdots &&\ddots &\vdots \\0&0&0&\ldots &f[x_{n}]\end{pmatrix}}.}$$

そしてそれは成り立つ

• ${\displaystyle T_{f+g}(x)=T_{f}(x)+T_{g}(x)}$
• ${\displaystyle T_{\lambda f}(x)=\lambda T_{f}(x)}$スカラーの場合${\displaystyle \lambda }$
• ${\displaystyle T_{f\cdot g}(x)=T_{f}(x)\cdot T_{g}(x)}$
  これはライプニッツの法則に従います。つまり、このような行列の乗算は可換です。まとめると、同じノード セットxに関する差分法の行列は可換環を形成します。
• は三角行列なので、その固有値は明らかに です。${\displaystyle T_{f}(x)}$${\displaystyle f(x_{0}),\dots ,f(x_{n})}$
• をクロネッカーのデルタのような関数とします。明らかに なので、は点関数乗算の固有関数です。つまり、 は の「固有行列」です。ただし、 のすべての列は互いの倍数であり、の行列階数は1 です。したがって、 のすべての固有ベクトルの行列を各 の - 番目の列から構成できます。 固有ベクトルの行列を で表します。例 の対角化は次のように記述できます。${\displaystyle \delta _{\xi }}$$${\displaystyle \delta _{\xi }(t)={\begin{cases}1&:t=\xi ,\\0&:{\mbox{else}}.\end{cases}}}$$${\displaystyle f\cdot \delta _{\xi }=f(\xi )\cdot \delta _{\xi }}$${\displaystyle \delta _{\xi }}$${\displaystyle T_{\delta _{x_{i}}}(x)}$${\displaystyle T_{f}(x)}$${\displaystyle T_{f}(x)\cdot T_{\delta _{x_{i}}}(x)=f(x_{i})\cdot T_{\delta _{x_{i}}}(x)}$${\displaystyle T_{\delta _{x_{i}}}(x)}$${\displaystyle T_{\delta _{x_{i}}}(x)}$${\displaystyle T_{f}(x)}$${\displaystyle i}$${\displaystyle T_{\delta _{x_{i}}}(x)}$${\displaystyle U(x)}$$${\displaystyle U(x_{0},x_{1},x_{2},x_{3})={\begin{pmatrix}1&{\frac {1}{(x_{1}-x_{0})}}&{\frac {1}{(x_{2}-x_{0})(x_{2}-x_{1})}}&{\frac {1}{(x_{3}-x_{0})(x_{3}-x_{1})(x_{3}-x_{2})}}\\0&1&{\frac {1}{(x_{2}-x_{1})}}&{\frac {1}{(x_{3}-x_{1})(x_{3}-x_{2})}}\\0&0&1&{\frac {1}{(x_{3}-x_{2})}}\\0&0&0&1\end{pmatrix}}}$$${\displaystyle T_{f}(x)}$$${\displaystyle U(x)\cdot \operatorname {diag} (f(x_{0}),\dots ,f(x_{n}))=T_{f}(x)\cdot U(x).}$$

行列には 、ノードに関する恒等関数 の差分商法が含まれているため、指数を持つべき乗関数の差分商法が含まれています。したがって、行列に を適用することで、多項式関数の差分商法を得ることができます。 の場合 、 となり、 これはオピッツの公式 として知られています。^{[2] [3]}$${\displaystyle J={\begin{pmatrix}x_{0}&1&0&0&\cdots &0\\0&x_{1}&1&0&\cdots &0\\0&0&x_{2}&1&&0\\\vdots &\vdots &&\ddots &\ddots &\\0&0&0&0&\;\ddots &1\\0&0&0&0&&x_{n}\end{pmatrix}}}$$${\displaystyle x_{0},\dots ,x_{n}}$${\displaystyle J^{m}}$ ${\displaystyle m}$ ${\displaystyle p}$${\displaystyle p}$${\displaystyle J}$$${\displaystyle p(\xi )=a_{0}+a_{1}\cdot \xi +\dots +a_{m}\cdot \xi ^{m}}$$$${\displaystyle p(J)=a_{0}+a_{1}\cdot J+\dots +a_{m}\cdot J^{m}}$$$${\displaystyle T_{p}(x)=p(J).}$$

ここで、 の次数を無限大に増やすこと、つまりテイラー多項式をテイラー級数に変換することを考えてみましょう。をべき級数に対応する関数とします。に対応する行列級数を に適用することで、の差分商スキームを計算できます。および の 場合 ${\displaystyle p}$${\displaystyle f}$${\displaystyle f}$${\displaystyle J}$$${\displaystyle f(\xi )=\sum _{k=0}^{\infty }a_{k}\xi ^{k}}$$$${\displaystyle f(J)=\sum _{k=0}^{\infty }a_{k}J^{k}}$$$${\displaystyle T_{f}(x)=f(J).}$$

$${\displaystyle {\begin{aligned}f[x_{0}]&=f(x_{0})\\f[x_{0},x_{1}]&={\frac {f(x_{0})}{(x_{0}-x_{1})}}+{\frac {f(x_{1})}{(x_{1}-x_{0})}}\\f[x_{0},x_{1},x_{2}]&={\frac {f(x_{0})}{(x_{0}-x_{1})\cdot (x_{0}-x_{2})}}+{\frac {f(x_{1})}{(x_{1}-x_{0})\cdot (x_{1}-x_{2})}}+{\frac {f(x_{2})}{(x_{2}-x_{0})\cdot (x_{2}-x_{1})}}\\f[x_{0},x_{1},x_{2},x_{3}]&={\frac {f(x_{0})}{(x_{0}-x_{1})\cdot (x_{0}-x_{2})\cdot (x_{0}-x_{3})}}+{\frac {f(x_{1})}{(x_{1}-x_{0})\cdot (x_{1}-x_{2})\cdot (x_{1}-x_{3})}}+\\&\quad \quad {\frac {f(x_{2})}{(x_{2}-x_{0})\cdot (x_{2}-x_{1})\cdot (x_{2}-x_{3})}}+{\frac {f(x_{3})}{(x_{3}-x_{0})\cdot (x_{3}-x_{1})\cdot (x_{3}-x_{2})}}\\f[x_{0},\dots ,x_{n}]&=\sum _{j=0}^{n}{\frac {f(x_{j})}{\prod _{k\in \{0,\dots ,n\}\setminus \{j\}}(x_{j}-x_{k})}}\end{aligned}}}$$

多項式関数 の助けを借りて、これは次のように書くことができる。 ${\displaystyle \omega (\xi )=(\xi -x_{0})\cdots (\xi -x_{n})}$$${\displaystyle f[x_{0},\dots ,x_{n}]=\sum _{j=0}^{n}{\frac {f(x_{j})}{\omega '(x_{j})}}.}$$

およびの場合、差商は次のように表すことができます^[4]。 ここで、は関数の-次導関数であり、はデータポイント に対する次の式で与えられる次数の特定のBスプラインです。 ${\displaystyle x_{0}<x_{1}<\cdots <x_{n}}$${\displaystyle n\geq 1}$ $${\displaystyle f[x_{0},\ldots ,x_{n}]={\frac {1}{(n-1)!}}\int _{x_{0}}^{x_{n}}f^{(n)}(t)\;B_{n-1}(t)\,dt}$$${\displaystyle f^{(n)}}$${\displaystyle n}$${\displaystyle f}$${\displaystyle B_{n-1}}$${\displaystyle n-1}$${\displaystyle x_{0},\dots ,x_{n}}$$${\displaystyle B_{n-1}(t)=\sum _{k=0}^{n}{\frac {(\max(0,x_{k}-t))^{n-1}}{\omega '(x_{k})}}}$$

これはペアノ​​核定理の結果であり、差分商のペアノ形式、差分商のペアノ核と呼ばれ、すべてジュゼッペ・ペアノにちなんで名付けられています。 ${\displaystyle B_{n-1}}$

データ ポイントが等間隔に分布している場合は、前進差分と呼ばれる特殊なケースになります。前進差分は、より一般的な分割差分よりも計算が簡単です。

n +1 個のデータ ポイント が与えられ、 前進差分は次のように定義されます 。 一方、後退差分は次のよう に定義されます。したがって、前進差分表は次のように記述されます。一方、後退差分表は次のように記述されます。$${\displaystyle (x_{0},y_{0}),\ldots ,(x_{n},y_{n})}$$$${\displaystyle x_{k}=x_{0}+kh,\ {\text{ for }}\ k=0,\ldots ,n{\text{ and fixed }}h>0}$$$${\displaystyle {\begin{aligned}\Delta ^{(0)}y_{k}&:=y_{k},\qquad k=0,\ldots ,n\\\Delta ^{(j)}y_{k}&:=\Delta ^{(j-1)}y_{k+1}-\Delta ^{(j-1)}y_{k},\qquad k=0,\ldots ,n-j,\ j=1,\dots ,n.\end{aligned}}}$$$${\displaystyle {\begin{aligned}\nabla ^{(0)}y_{k}&:=y_{k},\qquad k=0,\ldots ,n\\\nabla ^{(j)}y_{k}&:=\nabla ^{(j-1)}y_{k}-\nabla ^{(j-1)}y_{k-1},\qquad k=0,\ldots ,n-j,\ j=1,\dots ,n.\end{aligned}}}$$$${\displaystyle {\begin{matrix}y_{0}&&&\\&\Delta y_{0}&&\\y_{1}&&\Delta ^{2}y_{0}&\\&\Delta y_{1}&&\Delta ^{3}y_{0}\\y_{2}&&\Delta ^{2}y_{1}&\\&\Delta y_{2}&&\\y_{3}&&&\\\end{matrix}}}$$$${\displaystyle {\begin{matrix}y_{0}&&&\\&\nabla y_{1}&&\\y_{1}&&\nabla ^{2}y_{2}&\\&\nabla y_{2}&&\nabla ^{3}y_{3}\\y_{2}&&\nabla ^{2}y_{3}&\\&\nabla y_{3}&&\\y_{3}&&&\\\end{matrix}}}$$

分割差分と前方差分の関係は^[5] であるが、後方差分の場合は次のようになる。^{[引用が必要]}$${\displaystyle [y_{j},y_{j+1},\ldots ,y_{j+k}]={\frac {1}{k!h^{k}}}\Delta ^{(k)}y_{j},}$$$${\displaystyle [{y}_{j},y_{j-1},\ldots ,{y}_{j-k}]={\frac {1}{k!h^{k}}}\nabla ^{(k)}y_{j}.}$$

• 差の商
• ネヴィルのアルゴリズム
• 多項式補間
• 差の商の平均値定理
• ネルルンド・ライス積分
• パスカルの三角形

• ルイス・メルヴィル・ミルン・トムソン(2000) [1933].差分法. アメリカ数学会. 第1章: 差分商. ISBN 978-0-8218-2107-7。
• Myron B. Allen、Eli L. Isaacson (1998)。応用科学のための数値解析。John Wiley & Sons。付録A。ISBN 978-1-118-03027-1。
• ロン・ゴールドマン (2002)。ピラミッドアルゴリズム: 幾何学的モデリングのための曲線と表面への動的プログラミングアプローチ。モーガン・カウフマン。第 4 章:ニュートン補間と差分三角形。ISBN 978-0-08-051547-2。

• Haskellでの実装。