View source for विभाजित अंतर

{{Short description|Algorithm for computing polynomial coefficients}}

गणित में, विभाजित अंतर एक [[कलन विधि]] है, जिसका उपयोग ऐतिहासिक रूप से [[लघुगणक]] और [[त्रिकोणमितीय कार्य]]ों की तालिकाओं की गणना के लिए किया जाता है।{{Citation needed |date=October 2017}} [[चार्ल्स बैबेज]] का [[अंतर इंजन]], एक प्रारंभिक [[यांत्रिक कैलकुलेटर]], अपने संचालन में इस एल्गोरिदम का उपयोग करने के लिए डिज़ाइन किया गया था।<ref name="Isaacson2014">{{cite book |last1=Isaacson |first1=Walter |title=इनोवेटर्स|date=2014 |publisher=Simon & Schuster |isbn=978-1-4767-0869-0 |page=20 }}</ref>
विभाजित अंतर एक पुनरावर्ती विभाजन (गणित) प्रक्रिया है। डेटा बिंदुओं का एक क्रम दिया गया है <math>(x_0, y_0), \ldots, (x_{n}, y_{n})</math>, विधि [[न्यूटन बहुपद]] में इन बिंदुओं के [[बहुपद प्रक्षेप]] के गुणांक की गणना करती है।

==परिभाषा==
n + 1 डेटा पॉइंट दिया गया है
<math display="block">(x_0, y_0),\ldots,(x_{n}, y_{n})</math>
जहां <math>x_k</math> जोड़ीवार अलग-अलग माना जाता है, आगे विभाजित मतभेदों को इस प्रकार परिभाषित किया गया है:
<math display="block">\begin{align}
\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{align}</math>
गणना की पुनरावर्ती प्रक्रिया को स्पष्ट करने के लिए, विभाजित अंतरों को सारणीबद्ध रूप में रखा जा सकता है, जहां कॉलम उपरोक्त j के मान के अनुरूप होते हैं, और तालिका में प्रत्येक प्रविष्टि की गणना उसके तत्काल निचले बाएँ और उसके तत्काल ऊपरी बाएँ प्रविष्टियों के अंतर से की जाती है, जो संबंधित x-मानों के अंतर से विभाजित होती है:
<math display="block">
\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}
</math>


=== संकेतन ===
ध्यान दें कि विभाजित अंतर <math>[y_k,\ldots,y_{k+j}]</math> मूल्यों पर निर्भर करता है <math>x_k,\ldots,x_{k+j}</math> और <math>y_k,\ldots,y_{k+j}</math>, लेकिन अंकन x-मानों पर निर्भरता को छुपाता है। यदि डेटा बिंदु किसी फ़ंक्शन f द्वारा दिए गए हैं,
<math display="block">(x_0, f(x_0)), \ldots, (x_{k}, f(x_{n}))</math>
कोई कभी-कभी लिखता है
<math display="block">f[x_k,\ldots,x_{k+j}]</math>
लिखने के बजाय विभाजित अंतर के लिए
<math display="block">[f(x_k),\ldots,f(x_{k+j})]</math>
या
 <math display="block">[y_{k},\ldots,y_{k+j}].</math>
नोड्स x पर फ़ंक्शन के विभाजित अंतर के लिए कई अन्य नोटेशन<sub>0</sub>, ..., एक्स<sub>''n''</sub> उदाहरण के लिए, इनका भी उपयोग किया जाता है:
<math display="block">\begin{align}
&\mathopen[x_0,\ldots,x_n]f, \\
&\mathopen[x_0,\ldots,x_n;f], \\
&D[x_0,\ldots,x_n]f
\end{align}</math>


==उदाहरण==

के लिए मतभेद विभाजित <math>k=0</math> और के पहले कुछ मान <math>j</math>:
<math display="block">
\begin{align}
  \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{align}
</math> <!-- the \mathopen command is there because latex otherwise thinks that [...] denotes an optional argument -->


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

==मैट्रिक्स फॉर्म==
विभाजित अंतर योजना को ऊपरी [[त्रिकोणीय मैट्रिक्स]] में रखा जा सकता है:
<math display="block">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}.</math>
फिर यह कायम रहता है
* <math>T_{f+g}(x) = T_f(x) + T_g(x)</math>
* <math>T_{\lambda f}(x) = \lambda T_f(x)</math> अगर <math>\lambda</math> एक अदिश राशि है
* <math>T_{f\cdot g}(x) = T_f(x) \cdot T_g(x)</math> {{pb}} यह लीबनिज नियम का अनुसरण करता है। इसका अर्थ यह है कि ऐसे आव्यूहों का गुणन क्रमविनिमेयता है। संक्षेप में, नोड्स x के समान सेट के संबंध में विभाजित अंतर योजनाओं के मैट्रिक्स एक क्रमविनिमेय रिंग बनाते हैं।
* तब से <math> T_f(x) </math> एक त्रिकोणीय मैट्रिक्स है, इसके [[eigenvalue]]s स्पष्ट रूप से हैं <math> f(x_0), \dots, f(x_n) </math>.
* होने देना <math>\delta_\xi</math> [[क्रोनकर डेल्टा]] जैसा फ़ंक्शन बनें, अर्थात <math display="block">\delta_\xi(t) = \begin{cases}
1 &: t=\xi , \\
0 &: \mbox{else}.
\end{cases}</math> ज़ाहिर तौर से <math>f\cdot \delta_\xi = f(\xi)\cdot \delta_\xi</math>, इस प्रकार <math>\delta_\xi</math> बिंदुवार फ़ंक्शन गुणन का एक [[eigenfunction]] है। वह है <math>T_{\delta_{x_i}}(x)</math> किसी तरह का एक [[eigenmatrix]] है <math>T_f(x)</math>: <math> T_f(x) \cdot T_{\delta_{x_i}} (x) = f(x_i) \cdot T_{\delta_{x_i}}(x) </math>. हालाँकि, के सभी कॉलम <math>T_{\delta_{x_i}}(x)</math> एक दूसरे के गुणज हैं, [[मैट्रिक्स रैंक]] <math>T_{\delta_{x_i}}(x)</math> 1 है। तो आप सभी eigenvectors के मैट्रिक्स की रचना कर सकते हैं <math>T_f(x)</math> से <math>i</math>प्रत्येक का -वाँ स्तंभ <math>T_{\delta_{x_i}}(x)</math>. eigenvectors के मैट्रिक्स को निरूपित करें <math>U(x)</math>. उदाहरण <math display="block"> 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} </math> का [[विकर्णीय मैट्रिक्स]] <math>T_f(x)</math> के रूप में लिखा जा सकता है <math display="block"> U(x) \cdot \operatorname{diag}(f(x_0),\dots,f(x_n)) = T_f(x) \cdot U(x) .</math>


===बहुपद और घात श्रृंखला===
गणित का सवाल
 <math display="block">
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}
</math>
इसमें नोड्स के संबंध में पहचान फ़ंक्शन के लिए विभाजित अंतर योजना शामिल है <math>x_0,\dots,x_n</math>, इस प्रकार <math>J^m</math> इसमें घातांक के साथ [[एकपद]]ी के लिए विभाजित अंतर शामिल हैं <math>m</math>.
परिणामस्वरूप, आप एक बहुपद फलन के लिए विभाजित अंतर प्राप्त कर सकते हैं <math>p</math> लगाने से <math>p</math> मैट्रिक्स के लिए <math>J</math>: अगर
<math display="block">p(\xi) = a_0 + a_1 \cdot \xi + \dots + a_m \cdot \xi^m</math>
और
<math display="block">p(J) = a_0 + a_1\cdot J + \dots + a_m\cdot J^m</math>
तब
<math display="block">T_p(x) = p(J).</math>
इसे ओपिट्ज़ सूत्र के नाम से जाना जाता है।<ref>[[Carl de Boor|de Boor, Carl]], ''Divided Differences'', Surv. Approx. Theory  1  (2005), 46–69, [http://www.emis.de/journals/SAT/papers/2/]</ref><ref>Opitz, G. ''Steigungsmatrizen'', Z. Angew. Math. Mech. (1964), 44, T52–T54</ref>
अब की डिग्री बढ़ाने पर विचार करें <math>p</math> अनंत तक, यानी टेलर बहुपद को [[टेलर श्रृंखला]] में बदल दें।
होने देना <math>f</math> एक ऐसा फ़ंक्शन बनें जो पावर श्रृंखला से मेल खाता हो।
आप विभाजित अंतर योजना की गणना कर सकते हैं <math>f</math> संबंधित मैट्रिक्स श्रृंखला को लागू करके <math>J</math>:
अगर
<math display="block">f(\xi) = \sum_{k=0}^\infty a_k \xi^k</math>
और
<math display="block">f(J)=\sum_{k=0}^\infty a_k J^k</math>
तब
<math display="block">T_f(x)=f(J).</math>


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

===विस्तृत रूप===
<math display="block">
\begin{align}
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{align}
</math>
बहुपद फलन की सहायता से <math>\omega(\xi) = (\xi-x_0) \cdots (\xi-x_n)</math> इसे इस प्रकार लिखा जा सकता है
<math display="block">
f[x_0,\dots,x_n] = \sum_{j=0}^{n} \frac{f(x_j)}{\omega'(x_j)}.
</math>


===पीनो फॉर्म===
अगर <math>x_0<x_1<\cdots<x_n</math> और <math>n\geq 1</math>, विभाजित मतभेदों को इस प्रकार व्यक्त किया जा सकता है<ref>{{Cite book |last=Skof |first=Fulvia |url=https://books.google.com/books?id=ulUM2GagwacC&dq=This+is+called+the+Peano+form+of+the+divided+differences&pg=PA41 |title=Giuseppe Peano between Mathematics and Logic: Proceeding of the International Conference in honour of Giuseppe Peano on the 150th anniversary of his birth and the centennial of the Formulario Mathematico Torino (Italy) October 2-3, 2008 |date=2011-04-30 |publisher=Springer Science & Business Media |isbn=978-88-470-1836-5 |pages=40 |language=en}}</ref>
<math display="block">f[x_0,\ldots,x_n] = \frac{1}{(n-1)!} \int_{x_0}^{x_n} f^{(n)}(t)\;B_{n-1}(t) \, dt</math>
कहाँ <math>f^{(n)}</math> है <math>n</math>-फ़ंक्शन का व्युत्पन्न <math>f</math> और <math>B_{n-1}</math> डिग्री की एक निश्चित [[बी-पट्टी]] है <math>n-1</math> डेटा बिंदुओं के लिए <math>x_0,\dots,x_n</math>, सूत्र द्वारा दिया गया है
<math display="block">B_{n-1}(t) = \sum_{k=0}^n \frac{(\max(0,x_k-t))^{n-1}}{\omega'(x_k)}</math>
यह [[पीनो का कर्नेल प्रमेय]] का परिणाम है; इसे विभाजित मतभेदों का पीनो रूप कहा जाता है <math>B_{n-1}</math> विभाजित मतभेदों के लिए पीनो कर्नेल है, सभी का नाम ग्यूसेप पीनो के नाम पर रखा गया है।

===आगे का अंतर===
{{details|Finite difference}}

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

''n''+1 डेटा पॉइंट दिया गया है
<math display="block">(x_0, y_0), \ldots, (x_n, y_n)</math>
साथ
<math display="block">x_{k} = x_0 + k h,\ \text{ for } \ k=0,\ldots,n \text{ and fixed } h>0</math>
आगे के अंतरों को इस प्रकार परिभाषित किया गया है
<math display="block">\begin{align}
\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{align}</math>
<math display="block">
\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}
</math>
विभाजित मतभेदों और आगे के मतभेदों के बीच संबंध है<ref>{{cite book|last1=Burden|first1=Richard L.| last2=Faires|first2=J. Douglas | title=संख्यात्मक विश्लेषण|url=https://archive.org/details/numericalanalysi00rlbu |url-access=limited | date=2011|page=[https://archive.org/details/numericalanalysi00rlbu/page/n146 129]| isbn=9780538733519| edition=9th}}</ref>
<math display="block">[y_0, y_1, \ldots , y_n] = \frac{1}{n!h^n}\Delta^{(n)}y_0.</math>


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

==संदर्भ==
{{Reflist|1}}
* {{cite book|author=Louis Melville Milne-Thomson|author-link=L. M. Milne-Thomson| title=The Calculus of Finite Differences | year=2000|orig-year=1933| publisher=American Mathematical Soc.| isbn=978-0-8218-2107-7|at=Chapter 1: Divided Differences}}
* {{cite book|author1=Myron B. Allen|author2=Eli L. Isaacson| title=Numerical Analysis for Applied Science | year=1998|publisher=John Wiley & Sons|isbn=978-1-118-03027-1| at=Appendix A}}
* {{cite book|author=Ron Goldman|title=Pyramid Algorithms: A Dynamic Programming Approach to Curves and Surfaces for Geometric Modeling|year=2002| publisher=Morgan Kaufmann| isbn=978-0-08-051547-2| at=Chapter 4:Newton Interpolation and Difference Triangles}}


== बाहरी संबंध  ==
* An [http://code.henning-thielemann.de/htam/src/Numerics/Interpolation/DividedDifference.hs implementation] in [[Haskell (programming language)|Haskell]].
[[Category: परिमित अंतर]] 

[[de:Polynominterpolation#Bestimmung der Koeffizienten: Schema der dividierten Differenzen]]



[[Category: Machine Translated Page]]
[[Category:Created On 25/07/2023]]