विभाजित अंतर

गणित में, विभाजित अंतर एक एल्गोरिदम (कलन विधि) है, जिसका उपयोग ऐतिहासिक रूप से लॉगरिदम और त्रिकोणमितीय कार्य की तालिकाओं की गणना के लिए किया जाता है। चार्ल्स बैबेज का अंतर इंजन, एक प्रारंभिक यांत्रिक कैलकुलेटर, अपने संचालन में इस एल्गोरिदम का उपयोग करने के लिए डिज़ाइन किया गया था।

विभाजित अंतर एक पुनरावर्ती विभाजन प्रक्रिया है। डेटा बिंदुओं $(x_{0},y_{0}),\ldots ,(x_{n},y_{n})$ के अनुक्रम को देखते हुए, विधि न्यूटन फॉर्म में इन बिंदुओं के इंटरपोलेशन बहुपद के गुणांक की गणना करती है।

परिभाषा

n + 1 डेटा पॉइंट दिया गया है

$$(x_{0},y_{0}),\ldots ,(x_{n},y_{n})$$

जहां $x_{k}$ जोड़ीवार अलग-अलग माना जाता है, आगे विभाजित मतभेदों को इस प्रकार परिभाषित किया गया है:

$${\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 ,n-j\},\ j\in \{1,\ldots ,n\}.\end{aligned}}$$

गणना की पुनरावर्ती प्रक्रिया को स्पष्ट करने के लिए, विभाजित अंतरों को सारणीबद्ध रूप में रखा जा सकता है, जहां कॉलम उपरोक्त j के मान के अनुरूप होते हैं, और तालिका में प्रत्येक प्रविष्टि की गणना प्रविष्टियों के अंतर से उसके तत्काल निचले बाएँ तक की जाती है और इसके ठीक ऊपरी बायीं ओर, संगत x-मानों के अंतर से विभाजित:

$${\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_{k},\ldots ,y_{k+j}]$ मूल्यों पर निर्भर करता है $x_{k},\ldots ,x_{k+j}$ और $y_{k},\ldots ,y_{k+j}$, लेकिन अंकन x-मानों पर निर्भरता को अप्रदर्शित करता है। यदि डेटा बिंदु किसी फलन ƒ द्वारा दिए गए हैं,

$$(x_{0},f(x_{0})),\ldots ,(x_{k},f(x_{n}))$$

कोई कभी-कभी लिखता है

$$f[x_{k},\ldots ,x_{k+j}]$$

लिखने के स्थान पर विभाजित अंतर के लिए

$$[f(x_{k}),\ldots ,f(x_{k+j})]$$

या

$$[y_{k},\ldots ,y_{k+j}].$$

उदाहरण के लिए, नोड्स x₀, ..., x_n पर फलन ƒ के विभाजित अंतर के लिए कई अन्य नोटेशन का भी उपयोग किया जाता है:

$${\begin{aligned}&{\mathopen {[}}x_{0},\ldots ,x_{n}]f,\\&{\mathopen {[}}x_{0},\ldots ,x_{n};f],\\&D[x_{0},\ldots ,x_{n}]f\end{aligned}}$$

उदाहरण

$k=0$ और $j$ के पहले कुछ मानों के लिए विभाजित अंतर:

$${\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}}$$

गुण

• रैखिक कार्यात्मक
  $${\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\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}]$$
• विभाजित अंतर सममित हैं: यदि $\sigma :\{0,\dots ,n\}\to \{0,\dots ,n\}$ तो फिर एक क्रमपरिवर्तन है
  $$f[x_{0},\dots ,x_{n}]=f[x_{\sigma (0)},\dots ,x_{\sigma (n)}]$$
• न्यूटन बहुपद में बहुपद प्रक्षेप: यदि $P$ डिग्री का एक बहुपद फलन है $\leq n$, और $p[x_{0},\dots ,x_{n}]$ तो फिर विभाजित अंतर है
  $$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})$$
• यदि $p$ डिग्री का एक बहुपद फलन है $<n$, तब
  $$p[x_{0},\dots ,x_{n}]=0.$$
• विभाजित अंतरों के लिए माध्य मान प्रमेय: यदि $f$ तो फिर, n गुना अवकलनीय है
  $$f[x_{0},\dots ,x_{n}]={\frac {f^{(n)}(\xi )}{n!}}$$
  किसी संख्या $\xi$ के लिए विवृत अंतराल में सबसे छोटे और सबसे बड़े $x_{k}$'s द्वारा निर्धारित किया जाता है।

आव्यूह फॉर्म

विभाजित अंतर योजना को ऊपरी त्रिकोणीय आव्यूह में रखा जा सकता है:

$$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}}.$$

फिर यह दृढ़ रहता है

• $T_{f+g}(x)=T_{f}(x)+T_{g}(x)$
• $T_{\lambda f}(x)=\lambda T_{f}(x)$ यदि $\lambda$ एक अदिश राशि है
• $T_{f\cdot g}(x)=T_{f}(x)\cdot T_{g}(x)$
  यह लीबनिज नियम का अनुसरण करता है। इसका अर्थ यह है कि ऐसे आव्यूहों का गुणन क्रमविनिमेयता है। संक्षेप में, नोड्स x के समान समुच्चय के संबंध में विभाजित अंतर योजनाओं के आव्यूह एक क्रमविनिमेय रिंग बनाते हैं।
• तब से $T_{f}(x)$ एक त्रिकोणीय आव्यूह है, इसके ईजेन वैल्यू ​​​​स्पष्ट रूप से हैं $f(x_{0}),\dots ,f(x_{n})$.
• होने देना $\delta _{\xi }$ क्रोनकर डेल्टा जैसा फलन बनें, अर्थात
  $$\delta _{\xi }(t)={\begin{cases}1&:t=\xi ,\\0&:{\mbox{else}}.\end{cases}}$$
  स्पष्टत रूप से $f\cdot \delta _{\xi }=f(\xi )\cdot \delta _{\xi }$, इस प्रकार $\delta _{\xi }$ बिंदुवार फलन गुणन का एक ईजेनफलन है। वह है $T_{\delta _{x_{i}}}(x)$ किसी तरह का एक ईजेनआव्यूह है $T_{f}(x)$: $T_{f}(x)\cdot T_{\delta _{x_{i}}}(x)=f(x_{i})\cdot T_{\delta _{x_{i}}}(x)$. हालाँकि, के सभी कॉलम $T_{\delta _{x_{i}}}(x)$ एक दूसरे के गुणज हैं, आव्यूह रैंक $T_{\delta _{x_{i}}}(x)$ 1 है। तो आप सभी ईजेनसदिश के आव्यूह की रचना कर सकते हैं $T_{f}(x)$ से $i$ प्रत्येक का -वाँ स्तंभ $T_{\delta _{x_{i}}}(x)$. ईजेनसदिश के आव्यूह को निरूपित करें $U(x)$. उदाहरण
  $$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}}$$
  का विकर्णीय आव्यूह $T_{f}(x)$ के रूप में लिखा जा सकता है
  $$U(x)\cdot \operatorname {diag} (f(x_{0}),\dots ,f(x_{n}))=T_{f}(x)\cdot U(x).$$

बहुपद और घात श्रृंखला

गणित का सवाल

$$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}}$$

इसमें नोड्स $x_{0},\dots ,x_{n}$ के संबंध में पहचान फलन के लिए विभाजित अंतर योजना सम्मिलित है, इस प्रकार $J^{m}$ में घातांक $m$ के साथ घात फलन के लिए विभाजित अंतर सम्मिलित हैं। परिणामस्वरूप, आप आव्यूह $J$ पर $p$ लागू करके एक बहुपद फलन $p$ के लिए विभाजित अंतर प्राप्त कर सकते हैं: यदि

$$p(\xi )=a_{0}+a_{1}\cdot \xi +\dots +a_{m}\cdot \xi ^{m}$$

और

$$p(J)=a_{0}+a_{1}\cdot J+\dots +a_{m}\cdot J^{m}$$

तब

$$T_{p}(x)=p(J).$$

अब $p$ की घात को अनंत तक बढ़ाने पर विचार करें, यानी टेलर बहुपद को टेलर श्रृंखला में बदल दें। मान लीजिए कि $f$ एक फलन है जो घात श्रृंखला से मेल खाता है। आप संबंधित आव्यूह श्रृंखला को $J$ पर लागू करके $f$ के लिए विभाजित अंतर योजना की गणना कर सकते हैं: यदि

$$f(\xi )=\sum _{k=0}^{\infty }a_{k}\xi ^{k}$$

और

$$f(J)=\sum _{k=0}^{\infty }a_{k}J^{k}$$

तब

$$T_{f}(x)=f(J).$$

वैकल्पिक लक्षण वर्णन

विस्तृत रूप

$${\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}}$$

बहुपद फलन की सहायता से $\omega (\xi )=(\xi -x_{0})\cdots (\xi -x_{n})$ इसे इस प्रकार लिखा जा सकता है

$$f[x_{0},\dots ,x_{n}]=\sum _{j=0}^{n}{\frac {f(x_{j})}{\omega '(x_{j})}}.$$

पीनो फॉर्म

यदि $x_{0}<x_{1}<\cdots <x_{n}$ और $n\geq 1$, विभाजित मतभेदों को इस प्रकार व्यक्त किया जा सकता है

$$f[x_{0},\ldots ,x_{n}]={\frac {1}{(n-1)!}}\int _{x_{0}}^{x_{n}}f^{(n)}(t)\;B_{n-1}(t)\,dt$$

कहाँ $f^{(n)}$ है $n$-फलन का व्युत्पन्न $f$ और $B_{n-1}$ डिग्री की एक निश्चित बी-पट्टी है $n-1$ डेटा बिंदुओं के लिए $x_{0},\dots ,x_{n}$, सूत्र द्वारा दिया गया है

$$B_{n-1}(t)=\sum _{k=0}^{n}{\frac {(\max(0,x_{k}-t))^{n-1}}{\omega '(x_{k})}}$$

यह पीनो का कर्नेल प्रमेय का परिणाम है; इसे विभाजित मतभेदों का पीनो रूप कहा जाता है $B_{n-1}$ विभाजित मतभेदों के लिए पीनो कर्नेल है, सभी का नाम ग्यूसेप पीनो के नाम पर रखा गया है।

आगे का अंतर

Further information: परिमित अंतर

जब डेटा बिंदुओं को समान रूप से वितरित किया जाता है तो हमें विशेष मामला मिलता है जिसे फॉरवर्ड डिफरेंस कहा जाता है। अधिक सामान्य विभाजित अंतरों की तुलना में उनकी गणना करना आसान है।

n+1 डेटा पॉइंट दिया गया है

$$(x_{0},y_{0}),\ldots ,(x_{n},y_{n})$$

साथ

$$x_{k}=x_{0}+kh,\ {\text{ for }}\ k=0,\ldots ,n{\text{ and fixed }}h>0$$

आगे के अंतरों को इस प्रकार परिभाषित किया गया है

$${\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}}$$

$${\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}}$$

विभाजित मतभेदों और आगे के मतभेदों के बीच संबंध है

$$[y_{0},y_{1},\ldots ,y_{n}]={\frac {1}{n!h^{n}}}\Delta ^{(n)}y_{0}.$$

यह भी देखें

• अंतर भागफल
• नेविल का एल्गोरिदम
• बहुपद प्रक्षेप
• विभाजित अंतरों के लिए माध्य मान प्रमेय
• नॉरलुंड-चावल अभिन्न
• पास्कल का त्रिकोण

संदर्भ

• 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.

बाहरी संबंध

• An implementation in Haskell.