相違点の分割

Algorithm for computing polynomial coefficients

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

差商法は再帰的な 除算処理です。データ点の列が与えられた場合、この手法ではこれらの点のニュートン形式における補間多項式の係数を計算します。 ${\displaystyle (x_{0},y_{0}),\ldots ,(x_{n},y_{n})}$

これは、バー付きのデルタ または で表されることもあります。 ${\displaystyle {\text{△}}\!\!\!|\,\,}$ ${\displaystyle {\text{◿}}\!{\text{◺}}}$

意味

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_{j}]&:={\frac {[y_{k+1},\ldots ,y_{j}]-[y_{k},\ldots ,y_{j-1}]}{x_{j}-x_{k}}},&&k\in \{0,\ldots ,n-1\},\ j\in \{k+1,\ldots ,n\}.\end{aligned}}}$$

計算の再帰プロセスをより明確にするために、分割された差を表形式にすることができます。表の列は上記のjの値に対応し、表の各エントリは、そのすぐ左下のエントリとすぐ左上のエントリの差を、対応するx値の差で割って計算されます。 $${\displaystyle {\begin{matrix}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{matrix}}}$$

表記

差商は値とに依存するが、表記法によって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{aligned}}}$$

したがって、これらの用語を 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{matrix}}}$$

プロパティ

• 直線性 $${\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}.}$$

明示的な式

データ点が等間隔に並んでいる場合、 の明示的な式も導出できる。 となる任意の固定されたとに対して、 ${\displaystyle [y_{j},\ldots ,y_{j+k}]}$ ${\displaystyle k\leq n}$ ${\displaystyle j}$ ${\displaystyle j+k\leq n}$ $${\displaystyle [y_{j},\ldots ,y_{j+k}]={\frac {(-1)^{j+k}}{k!h^{k}}}\sum _{i=j}^{j+k}(-1)^{i}y_{i}{\binom {k}{i-j}}.}$$

証明．これを帰納法で証明する： ${\displaystyle k}$

基本ケース:ととします。定義により となり、 ${\displaystyle k=0}$ ${\displaystyle j=0\ldots n}$ ${\displaystyle [y_{j}]=y_{j}}$ $${\displaystyle {\frac {(-1)^{j}}{0!h^{0}}}\sum _{i=j}^{j}(-1)^{i}y_{i}{\binom {0}{i-j}}=(-1)^{2j}y_{j}=y_{j}.}$$

帰納法のステップ：上式が まで成り立つと仮定し、となるようなものを考える。再帰的定義により、 ${\displaystyle k}$ ${\displaystyle j}$ ${\displaystyle j+k+1\leq n}$

$${\displaystyle [y_{j},\ldots ,y_{j+k+1}]={\frac {1}{h(k+1)}}\left([y_{j+1},\ldots ,y_{j+k+1}]-[y_{j},\ldots ,y_{j+k}]\right).}$$

左辺の両項に帰納的仮定を適用して、

$${\displaystyle {\frac {1}{h(k+1)}}\left({\frac {(-1)^{j+k+1}}{k!h^{k}}}\sum _{i=j+1}^{j+k+1}(-1)^{i}y_{i}{\binom {k}{i-j}}-{\frac {(-1)^{j+k}}{k!h^{k}}}\sum _{i=j}^{j+k}(-1)^{i}y_{i}{\binom {k}{i-j}}\right).}$$

これを次のように並べ替えることもできる。

$${\displaystyle {\frac {(-1)^{j+k+1}}{(k+1)!h^{k+1}}}\sum _{i=j}^{j+k+1}(-1)^{i}y_{i}\left({\binom {k}{i-j}}+{\binom {k}{i-j-1}}\right)}$$

となる 。恒等式を代入することで、 の命題が得られる。 ${\displaystyle {\binom {k}{s}}=0}$ ${\displaystyle s<k}$ ${\displaystyle k+1}$ $${\displaystyle {\binom {k}{i-j}}+{\binom {k}{i-j-1}}={\binom {k+1}{i-j}}.}$$

参照

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

参考文献

1. アイザックソン、ウォルター (2014). 『イノベーターズ』 サイモン＆シュスター社. p. 20. ISBN 978-1-4767-0869-0。
2. デ・ブール、カール、「差異の分割」、調査近似理論1（2005年）、46-69、[1]
3. Opitz、G. Steigungsmatrizen、Z. Angew。数学。メカ。 (1964)、44、T52–T54
4. Skof, Fulvia (2011-04-30). ジュゼッペ・ペアノ：数学と論理の間：ジュゼッペ・ペアノ生誕150周年および数学公式100周年を記念した国際会議議事録（イタリア、トリノ）2008年10月2日～3日. Springer Science & Business Media. p. 40. ISBN 978-88-470-1836-5。
5. Burden, Richard L.; Faires, J. Douglas (2011).数値解析（第9版）. Cengage Learning. p. 129. ISBN 9780538733519。

• ルイス・メルヴィル・ミルン＝トムソン(2000) [1933].差分法. アメリカ数学会. 第1章 差の商. ISBN 978-0-8218-2107-7。
• マイロン・B・アレン、イーライ・L・アイザックソン (1998).応用科学のための数値解析. ジョン・ワイリー・アンド・サンズ. 付録A. ISBN 978-1-118-03027-1。
• ロン・ゴールドマン（2002年） 『ピラミッドアルゴリズム：曲線と曲面の幾何学モデリングのための動的計画法アプローチ』モーガン・カウフマン著。第4章：ニュートン補間と差分三角形。ISBN 978-0-08-051547-2。

外部リンク

• Haskellでの実装。

Retrieved from "https://en.wikipedia.org/w/index.php?title=Divided_differences&oldid=1320153404"