差商

数学における差商（さしょう、英: divided differences; 分割差分、差分商[1]）は、差分商をとる操作を再帰的に繰り返すことで与えられる。歴史的には対数表や三角函数表の計算に用いられ、チャールズ・バベッジの階差機関（初期の機械式計算機）はこれを実装するものとして設計された[2]。

差商はニュートン補間における補間多項式の計算に用いることができる。

定義

n + 1 個の節点 ( x 0 , y 0 ) , … , ( x n , y n ) {\textstyle (x_{0},y_{0}),\ldots ,(x_{n},y_{n})} に対する、前進差商は

[ y ν ] := y ν ( ν ∈ { 0 , … , n } ) , [ y ν , … , y ν + j ] := [ y ν + 1 , … , y ν + j ] − [ y ν , … , y ν + j − 1 ] x ν + j − x ν ( ν ∈ { 0 , … , n − j } ,   j ∈ { 1 , … , n } ) {\displaystyle {\begin{aligned}{}[y_{\nu }]&:=y_{\nu }\quad (\nu \in \{0,\ldots ,n\}),\\[5pt][y_{\nu },\ldots ,y_{\nu +j}]&:={\frac {[y_{\nu +1},\ldots ,y_{\nu +j}]-[y_{\nu },\ldots ,y_{\nu +j-1}]}{x_{\nu +j}-x_{\nu }}}\quad (\nu \in \{0,\ldots ,n-j\},\ j\in \{1,\ldots ,n\})\end{aligned}}}
で定義される。同様に後退差商は
[ y ν ] := y ν ( ν ∈ { 0 , … , n } ) , [ y ν , … , y ν − j ] := [ y ν , … , y ν − j + 1 ] − [ y ν − 1 , … , y ν − j ] x ν − x ν − j ( ν ∈ { j , … , n } ,   j ∈ { 1 , … , n } ) {\displaystyle {\begin{aligned}{}[y_{\nu }]&:=y_{\nu }\quad (\nu \in \{0,\ldots ,n\}),\\[5pt][y_{\nu },\ldots ,y_{\nu -j}]&:={\frac {[y_{\nu },\ldots ,y_{\nu -j+1}]-[y_{\nu -1},\ldots ,y_{\nu -j}]}{x_{\nu }-x_{\nu -j}}}\quad (\nu \in \{j,\ldots ,n\},\ j\in \{1,\ldots ,n\})\end{aligned}}}
と定義される。

以下本項では主に前進差商のみを扱い、それを単に差商と呼ぶ。

等間隔の場合

詳細は「差分商」を参照

節点（の x-座標）が等間隔に並んでいるときには、前進差分（あるいは後退・中央の各有限差分）の定める差分商によって差商を記述することができる。この場合は、より一般の差商よりも計算が楽になる。注目すべきは、差商の分母が既知であるならば、差分商から差商を容易に回復することができることである。

すなわち、上と同じ節点のデータが与えられ、適当な数 h > 0 に対して xν = x0 + νh (ν = 0, …, n) となっているとき、前進差分は

Δ ( 0 ) y i := y i , Δ ( k ) y i := Δ ( k − 1 ) y i + 1 − Δ ( k − 1 ) y i ( k ≥ 1 ) {\displaystyle {\begin{aligned}\Delta ^{(0)}y_{i}&:=y_{i},\\\Delta ^{(k)}y_{i}&:=\Delta ^{(k-1)}y_{i+1}-\Delta ^{(k-1)}y_{i}\quad (k\geq 1)\end{aligned}}}
で定義される。前進差分と差商との関係は
f [ x 0 , x 1 , … , x k ] = 1 k ! h k Δ ( k ) f ( x 0 ) {\displaystyle f[x_{0},x_{1},\ldots ,x_{k}]={\frac {1}{k!h^{k}}}\Delta ^{(k)}f(x_{0})}
と書ける[3]。

ニュートンの三角形

隣り合う二項から次の階数の項が次々に作られる様子は、パスカルの三角形の類似で、差商を三角形状に並べるとわかりよい。

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 ] {\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}} あるいは y 0 Δ y 0 y 1 Δ 2 y 0 Δ y 1 Δ 3 y 0 y 2 Δ 2 y 1 Δ y 2 y 3 {\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}}

記法

節点が函数 f を用いて ( x 0 , f ( x 0 ) ) , … , ( x n , f ( x n ) ) {\textstyle (x_{0},f(x_{0})),\ldots ,(x_{n},f(x_{n}))} と与えられているときには、

f [ x ν ] := f ( x ν ) , ν ∈ { 0 , … , n } , f [ x ν , … , x ν + j ] := f [ x ν + 1 , … , x ν + j ] − f [ x ν , … , x ν + j − 1 ] x ν + j − x ν ( ν ∈ { 0 , … , n − j } ,   j ∈ { 1 , … , n } ) {\displaystyle {\begin{aligned}f[x_{\nu }]&:=f(x_{\nu }),\qquad \nu \in \{0,\ldots ,n\},\\[5pt]f[x_{\nu },\ldots ,x_{\nu +j}]&:={\frac {f[x_{\nu +1},\ldots ,x_{\nu +j}]-f[x_{\nu },\ldots ,x_{\nu +j-1}]}{x_{\nu +j}-x_{\nu }}}\quad (\nu \in \{0,\ldots ,n-j\},\ j\in \{1,\ldots ,n\})\end{aligned}}}
と書くこともある。同様に
[ x 0 , … , x n ] f , [ x 0 , … , x n ; f ] , D [ x 0 , … , x n ] f {\displaystyle [x_{0},\ldots ,x_{n}]f,\quad [x_{0},\ldots ,x_{n};f],\quad D[x_{0},\ldots ,x_{n}]f}
などとも書く。

具体的に書き下せば:

f [ x 0 ] = f ( x 0 ) f [ x 0 , x 1 ] = f ( x 0 ) ( x 0 − x 1 ) + f ( x 1 ) ( x 1 − x 0 ) f [ x 0 , x 1 , x 2 ] = f ( x 0 ) ( x 0 − x 1 ) ⋅ ( x 0 − x 2 ) + f ( x 1 ) ( x 1 − x 0 ) ⋅ ( x 1 − x 2 ) + f ( x 2 ) ( x 2 − x 0 ) ⋅ ( x 2 − x 1 ) f [ x 0 , x 1 , x 2 , x 3 ] = f ( x 0 ) ( x 0 − x 1 ) ⋅ ( x 0 − x 2 ) ⋅ ( x 0 − x 3 ) + f ( x 1 ) ( x 1 − x 0 ) ⋅ ( x 1 − x 2 ) ⋅ ( x 1 − x 3 ) + f ( x 2 ) ( x 2 − x 0 ) ⋅ ( x 2 − x 1 ) ⋅ ( x 2 − x 3 ) + f ( x 3 ) ( x 3 − x 0 ) ⋅ ( x 3 − x 1 ) ⋅ ( x 3 − x 2 ) {\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})}}+{\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})}}\end{aligned}}}
のようになる。一般に
f [ x 0 , … , x n ] = ∑ j = 0 n f ( x j ) ∏ k = 0 , … n ; k ≠ j ( x j − x k ) {\displaystyle f[x_{0},\dots ,x_{n}]=\sum _{j=0}^{n}{\frac {f(x_{j})}{\prod _{k=0,\ldots n;k\neq j}(x_{j}-x_{k})}}}
となり、これを多項式函数 q ( ξ ) = ( ξ − x 0 ) ⋯ ( ξ − x n ) {\textstyle q(\xi )=(\xi -x_{0})\cdots (\xi -x_{n})} を用いて
f [ x 0 , … , x n ] = ∑ j = 0 n f ( x j ) q ′ ( x j ) {\displaystyle f[x_{0},\dots ,x_{n}]=\sum _{j=0}^{n}{\frac {f(x_{j})}{q'(x_{j})}}}
と書くことができる。また極限を用いて
f [ x 0 , … , x n ] = ∑ j = 0 n lim x → x j [ f ( x j ) ( x − x j ) ∏ k = 0 n ( x − x k ) ] {\displaystyle f[x_{0},\dots ,x_{n}]=\sum _{j=0}^{n}\lim _{x\to x_{j}}\left[{\frac {f(x_{j})(x-x_{j})}{\prod _{k=0}^{n}(x-x_{k})}}\right]}
とも書ける。

性質

  • 線型性:
    ( f + g ) [ x 0 , … , x n ] = f [ x 0 , … , x n ] + g [ x 0 , … , x n ] ( λ ⋅ f ) [ x 0 , … , x n ] = λ ⋅ f [ x 0 , … , x n ] {\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}}}
  • ライプニッツの法則:
    ( f ⋅ g ) [ x 0 , … , x n ] = f [ x 0 ] ⋅ g [ x 0 , … , x n ] + f [ x 0 , x 1 ] ⋅ g [ x 1 , … , x n ] + ⋯ + f [ x 0 , … , x n ] ⋅ g [ x n ] {\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}]}
  • 対称性:
    f [ x 0 , … , x n ] = f [ x σ ( 0 ) , … , x σ ( n ) ] ( σ ∈ S n ) {\displaystyle f[x_{0},\dots ,x_{n}]=f[x_{\sigma (0)},\dots ,x_{\sigma (n)}]\quad (\sigma \in S_{n})}
  • 差商に対する平均値の定理より:
    f [ x 0 , … , x n ] = f ( n ) ( ξ ) n ! ( ∃ ξ ∈ ( min x k , max x k ) ) {\displaystyle f[x_{0},\dots ,x_{n}]={\frac {f^{(n)}(\xi )}{n!}}\quad (\exists \xi \in (\min x_{k},\max x_{k}))}

別定義

ペアノ形

次数 n − 1 のBスプライン Bn−1 を用いて、差商を

f [ x 0 , … , x n ] = 1 n ! ∫ x 0 x n f ( n ) ( t ) B n − 1 ( t ) d t {\displaystyle f[x_{0},\ldots ,x_{n}]={\frac {1}{n!}}\int _{x_{0}}^{x_{n}}f^{(n)}(t)B_{n-1}(t)\,dt}
と書くことができる。f(n) は f の n-階導函数である。

これを差商のペアノ形 (Peano form) と言い、Bn−1 をこの差商のペアノ核（英語版）と呼ぶ。ともに名称はジゼッペ・ペアノに因む。

テイラー形

考えている節点が集積しているならば、ほとんどゼロに近い値での割り算が生じ、桁落ちによって相対誤差が大きくなるから、数値計算はおぼつかない。しかしその場合も、差分商を微分商で（あるいはその逆に）近似することはできる:

f ( y ) − f ( x ) y − x ≈ f ′ ( x ) ( x ≈ y ) . {\displaystyle {\frac {f(y)-f(x)}{y-x}}\approx f'(x)\quad (x\approx y).}

この近似はテイラーの定理

f ( y ) = f ( x ) + f ′ ( x ) ⋅ ( y − x ) + f ″ ( x ) ⋅ ( y − x ) 2 2 ! + f ‴ ( x ) ⋅ ( y − x ) 3 3 ! + ⋯ {\displaystyle f(y)=f(x)+f'(x)\cdot (y-x)+f''(x)\cdot {\frac {(y-x)^{2}}{2!}}+f'''(x)\cdot {\frac {(y-x)^{3}}{3!}}+\dotsb }
が適用できる函数に関しては等式
f ( y ) − f ( x ) y − x = f ′ ( x ) + f ″ ( x ) ⋅ y − x 2 ! + f ‴ ( x ) ⋅ ( y − x ) 2 3 ! + ⋯ {\displaystyle {\frac {f(y)-f(x)}{y-x}}=f'(x)+f''(x)\cdot {\frac {y-x}{2!}}+f'''(x)\cdot {\frac {(y-x)^{2}}{3!}}+\dotsb }
に変えることができる。また、中央差分を利用すれば y − x の奇数冪の項を消すことができる:
f ( y ) − f ( x ) y − x = f ( m + h ) − f ( m − h ) 2 ⋅ h = f ′ ( m ) + f ‴ ( m ) ⋅ h 2 3 ! + ⋯ . {\displaystyle {\frac {f(y)-f(x)}{y-x}}={\frac {f(m+h)-f(m-h)}{2\cdot h}}=f'(m)+f'''(m)\cdot {\frac {h^{2}}{3!}}+\dotsb .}

原理的には、テイラー級数および任意の函数項級数（英語版）に差商近似が適用できる。テイラー級数は冪函数に関する無限和で、函数にその差商を対応させる写像 f ↦ f[x0, …, xn] は線型汎函数であるから、基底函数にこの汎函数を適用すればよい。

通常の冪函数 pn(x) ≔ xn によって、通常のテイラー級数を

f = f ( 0 ) ⋅ p 0 + f ′ ( 0 ) ⋅ p 1 + f ″ ( 0 ) 2 ! ⋅ p 2 + f ‴ ( 0 ) 3 ! ⋅ p 3 + … {\displaystyle f=f(0)\cdot p_{0}+f'(0)\cdot p_{1}+{\frac {f''(0)}{2!}}\cdot p_{2}+{\frac {f'''(0)}{3!}}\cdot p_{3}+\dotsc }
と書けば、差商のテイラー級数は
f [ x 0 , … , x n ] = f ( 0 ) ⋅ p 0 [ x 0 , … , x n ] + f ′ ( 0 ) ⋅ p 1 [ x 0 , … , x n ] + f ″ ( 0 ) 2 ! ⋅ p 2 [ x 0 , … , x n ] + f ‴ ( 0 ) 3 ! ⋅ p 3 [ x 0 , … , x n ] + ⋯ {\displaystyle f[x_{0},\dots ,x_{n}]=f(0)\cdot p_{0}[x_{0},\dots ,x_{n}]+f'(0)\cdot p_{1}[x_{0},\dots ,x_{n}]+{\frac {f''(0)}{2!}}\cdot p_{2}[x_{0},\dots ,x_{n}]+{\frac {f'''(0)}{3!}}\cdot p_{3}[x_{0},\dots ,x_{n}]+\dotsb }
と書けることになる。この最初の n 項は多項式の次数よりも高階の差分だから消えており、それ以降の項も以下のように知ることができる:
{ p j [ x 0 , … , x n ] = 0 ( j < n ) p n [ x 0 , … , x n ] = 1 p n + 1 [ x 0 , … , x n ] = x 0 + ⋯ + x n p n + m [ x 0 , … , x n ] = ∑ 0 ≤ a 1 ≤ a 2 ≤ ⋯ ≤ a m ≤ n ∏ j ∈ { a 1 , a 2 , … , a m } x j . {\displaystyle {\begin{cases}p_{j}[x_{0},\dots ,x_{n}]=0&(j<n)\\[3pt]p_{n}[x_{0},\dots ,x_{n}]=1&\\[3pt]p_{n+1}[x_{0},\dots ,x_{n}]&=x_{0}+\dots +x_{n}\\[8pt]p_{n+m}[x_{0},\dots ,x_{n}]&=\displaystyle \sum _{0\leq a_{1}\leq a_{2}\leq \dots \leq a_{m}\leq n}\prod _{j\in \{a_{1},a_{2},\ldots ,a_{m}\}}x_{j}.\\\end{cases}}}

行列表示

多項式の差商はライプニッツの法則の恩恵を受けられる点で興味を持たれる。

行列 J を

J = ( x 0 1 0 0 ⋯ 0 0 x 1 1 0 ⋯ 0 0 0 x 2 1 0 ⋮ ⋮ ⋱ ⋱ ⋮ ⋮ ⋱ 1 0 0 0 0 ⋯ x n ) {\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 &\\\vdots &\vdots &&&\ddots &1\\0&0&0&0&\cdots &x_{n}\end{pmatrix}}}
とすれば、これは節点 x0, …, xn に関する恒等写像 f(x) = x の差商をすべて包摂したものと考えることができる。特に Jn は冪函数 xn に対する差商が全て現れる。差商の線型性により、多項式 p に対する多項式函数を J に適用したものは、
p ( J ) = a 0 ⋅ I + a 1 ⋅ J + ⋯ + a n ⋅ J n = ( p [ x 0 ] p [ x 0 , x 1 ] p [ x 0 , x 1 , x 2 ] … p [ x 0 , … , x n ] 0 p [ x 1 ] p [ x 1 , x 2 ] … p [ x 1 , … , x n ] ⋮ ⋱ ⋱ ⋱ ⋮ 0 … 0 0 p [ x n ] ) {\displaystyle {\begin{aligned}p(J)&=a_{0}\cdot I+a_{1}\cdot J+\dots +a_{n}\cdot J^{n}\\[5pt]&={\begin{pmatrix}p[x_{0}]&p[x_{0},x_{1}]&p[x_{0},x_{1},x_{2}]&\ldots &p[x_{0},\dots ,x_{n}]\\0&p[x_{1}]&p[x_{1},x_{2}]&\ldots &p[x_{1},\dots ,x_{n}]\\[10pt]\vdots &\ddots &\ddots &\ddots &\vdots \\[10pt]0&\ldots &0&0&p[x_{n}]\end{pmatrix}}\end{aligned}}}
と書くことができ、オピッツの公式と呼ばれる[4][5]。

多項式 p の次数を無限大に飛ばして形式冪級数とすれば、テイラー展開可能な函数 f に対しても、その差商を J を用いた行列表示

T f ( x 0 , … , x n ) = f ( J ) = ( f [ x 0 ] f [ x 0 , x 1 ] f [ x 0 , x 1 , x 2 ] … f [ x 0 , … , x n ] 0 f [ x 1 ] f [ x 1 , x 2 ] … f [ x 1 , … , x n ] ⋮ ⋮ ⋮ ⋱ ⋮ 0 0 0 … f [ x n ] ) {\displaystyle T_{f}(x_{0},\dots ,x_{n})=f(J)={\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}]\\[20pt]\vdots &\vdots &\vdots &\ddots &\vdots \\0&0&0&\ldots &f[x_{n}]\end{pmatrix}}}
によって与えることができる。

節点 x0, …, xn が全て等しいとき、J はジョルダン細胞であり、ジョルダン標準形を考えることでスカラー函数を行列函数に一般化することができる。

関連項目

参考文献

  1. ^ 世界大百科事典『差分商』 - コトバンク
  2. ^ Isaacson, Walter (2014). The Innovators. Simon & Schuster. p. 20. ISBN 978-1-4767-0869-0 
  3. ^ Burden, Richard L.; Faires, J. Douglas (2011). Numerical Analysis (9th ed.). p. 129 
  4. ^ de Boor, Carl, Divided Differences, Surv. Approx. Theory 1 (2005), 46–69, [1]
  5. ^ Opitz, G. Steigungsmatrizen, Z. Angew. Math. Mech. (1964), 44, T52–T54
  • Louis Melville Milne-Thomson (2000) [1933]. The Calculus of Finite Differences. American Mathematical Soc.. Chapter 1: Divided Differences. ISBN 978-0-8218-2107-7 
  • Myron B. Allen; Eli L. Isaacson (1998). Numerical Analysis for Applied Science. John Wiley & Sons. Appendix A. ISBN 978-1-118-03027-1 
  • Ron Goldman (2002). Pyramid Algorithms: A Dynamic Programming Approach to Curves and Surfaces for Geometric Modeling. Morgan Kaufmann. Chapter 4:Newton Interpolation and Difference Triangles. ISBN 978-0-08-051547-2 

外部リンク

  • Weisstein, Eric W. "Divided Difference". mathworld.wolfram.com (英語).
  • divided difference - PlanetMath.（英語）
  • An implementation in Haskell.