स्पलाइन अंतर्वेशन

For broader coverage of this topic, see Spline (mathematics).

संख्यात्मक विश्लेषण के गणितीय क्षेत्र में, स्पलाइन अंतर्वेशन अंतर्वेशन का एक रूप है जहां इंटरपोलेंट एक विशेष प्रकार का खण्डवार बहुपद होता है जिसे स्पलाइन कहा जाता है। इसका अर्थ यह है कि सभी मानों के लिए एक ही उच्च-डिग्री बहुपद को एक साथ फिट करने के बजाय, स्पलाइन अंतर्वेशन निम्न-डिग्री बहुपद को मानों के लघु उपसमूहों में फिट करता है, उदाहरण के लिए, उन सभी में एक डिग्री दस बहुपद फिट करने के बजाय दस अंकों के प्रत्येक जोड़े के बीच नौ घन बहुपद फिट करना है। स्पलाइन अंतर्वेशन को अक्सर बहुपद अंतर्वेशन पर प्राथमिकता दी जाती है क्योंकि स्पलाइन के लिए निम्न-डिग्री बहुपद का उपयोग करते समय भी अंतर्वेशन त्रुटि को निम्न किया जा सकता है। स्प्लाइन अंतर्वेशन की घटना की समस्या से भी बचाता है, जिसमें उच्च-डिग्री बहुपद का उपयोग करके इंटरपोल करने पर बिंदुओं के बीच दोलन हो सकता है।

परिचय

आठ बिंदुओं के बीच घन विभाजन के साथ अंतर्वेशन है। जहाज निर्माण के लिए हाथ से बनाए गए तकनीकी चित्र तख़्ता प्रक्षेप का एक ऐतिहासिक उदाहरण हैं; चित्रों का निर्माण लचीले शासकों का उपयोग करके किया गया था जो पूर्व-निर्धारित बिंदुओं का पालन करने के लिए मुड़े हुए थे।

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

हम गणितीय समीकरणों के एक समुच्चय का उपयोग करके समान प्रकार के वक्रों का मॉडल बनाना चाहते हैं। मान लीजिए कि हमारे पास एक अनुक्रम है $n+1$ अंशों, $(x_{0},y_{0})$ द्वारा $(x_{n},y_{n})$. एक घन बहुपद होगा $q_{i}(x)=y$ अंश के प्रत्येक क्रमिक जोड़े के बीच $(x_{i-1},y_{i-1})$ और $(x_{i},y_{i})$ उन दोनों से जुड़कर कहां $i=1,2,\dots ,n$. तो वहाँ होगा $n$ बहुपद, पहले बहुपद से प्रारंभ होता है $(x_{0},y_{0})$, और अंतिम बहुपद पर समाप्त होता है $(x_{n},y_{n})$.

किसी भी वक्र की वक्रता $y=y(x)$ परिभाषित किया जाता है

$\kappa ={\frac {y''}{(1+y'^{2})^{3/2}}},$

कहाँ $y'$ और $y''$ के पहले और दूसरे व्युत्पन्न हैं $y(x)$ इसके संबंध में $x$. तख़्ते को एक ऐसा आकार देने के लिए जो झुकने को कम करता है (सभी अंश से गुजरने की बाधा के तहत), हम दोनों को परिभाषित करेंगे $y'$ और $y''$ अंश सहित हर जगह निरंतर रहना। प्रत्येक क्रमिक बहुपद में उनके जुड़ने वाले अंश पर समान मान (जो संबंधित डेटापॉइंट के y-मान के बराबर होते हैं), डेरिवेटिव और दूसरा डेरिवेटिव होना चाहिए, जिसका अर्थ है कि

${\begin{cases}q_{i}(x_{i})=q_{i+1}(x_{i})=y_{i}\\q'_{i}(x_{i})=q'_{i+1}(x_{i})\\q''_{i}(x_{i})=q''_{i+1}(x_{i})\end{cases}}\qquad 1\leq i\leq n-1.$

यह केवल तभी प्राप्त किया जा सकता है जब घात 3 (घन बहुपद) या उससे अधिक के बहुपदों का उपयोग किया जाए। शास्त्रीय दृष्टिकोण बिल्कुल 3 डिग्री - घन स्पलाइन के बहुपदों का उपयोग करना है।

उपरोक्त तीन स्थितियों के अतिरिक्त, एक 'प्राकृतिक घन स्पलाइन' में यह शर्त होती है $q''_{1}(x_{0})=q''_{n}(x_{n})=0$.

उपरोक्त तीन मुख्य स्थितियों के अतिरिक्त, एक 'क्लैम्प्ड घन स्पलाइन' में ये स्थितियाँ होती हैं $q'_{1}(x_{0})=f'(x_{0})$ और $q'_{n}(x_{n})=f'(x_{n})$ कहाँ $f'(x)$ इंटरपोलेटेड फलन का व्युत्पन्न है।

उपरोक्त तीन मुख्य स्थितियों के अतिरिक्त, 'नॉट-अ-नॉट स्प्लाइन' में वे स्थितियाँ होती हैं जो $q'''_{1}(x_{1})=q'''_{2}(x_{1})$ और $q'''_{n-1}(x_{n-1})=q'''_{n}(x_{n-1})$.

इंटरपोलेटिंग घन स्पलाइन को खोजने के लिए एल्गोरिदम

हम प्रत्येक बहुपद ज्ञात करना चाहते हैं $q_{i}(x)$ अंक दिए गए $(x_{0},y_{0})$ द्वारा $(x_{n},y_{n})$. ऐसा करने के लिए, हम वक्र के केवल एक खंड पर विचार करेंगे, $q(x)$, जो से प्रक्षेपित होगा $(x_{1},y_{1})$ को $(x_{2},y_{2})$. इस खंड में स्लोप होगी $k_{1}$ और $k_{2}$ इसके अंतिम बिंदु पर. या, अधिक सटीक रूप से,

$q(x_{1})=y_{1},$

$q(x_{2})=y_{2},$

$q'(x_{1})=k_{1},$

$q'(x_{2})=k_{2}.$

पूरा समीकरण $q(x)$ सममित रूप में लिखा जा सकता है

$q(x)={\big (}1-t(x){\big )}\,y_{1}+t(x)\,y_{2}+t(x){\big (}1-t(x){\big )}{\Big (}{\big (}1-t(x){\big )}\,a+t(x)\,b{\Big )},$

(1)

कहाँ

$t(x)={\frac {x-x_{1}}{x_{2}-x_{1}}},$

(2)

$a=k_{1}(x_{2}-x_{1})-(y_{2}-y_{1}),$

(3)

$b=-k_{2}(x_{2}-x_{1})+(y_{2}-y_{1}).$

(4)

लेकिन क्या हैं $k_{1}$ और $k_{2}$? इन महत्वपूर्ण मूल्यों को प्राप्त करने के लिए, हमें उस पर विचार करना चाहिए

$q'={\frac {dq}{dx}}={\frac {dq}{dt}}{\frac {dt}{dx}}={\frac {dq}{dt}}{\frac {1}{x_{2}-x_{1}}}.$

इसके बाद यह अनुसरण करता है

$q'={\frac {y_{2}-y_{1}}{x_{2}-x_{1}}}+(1-2t){\frac {a(1-t)+bt}{x_{2}-x_{1}}}+t(1-t){\frac {b-a}{x_{2}-x_{1}}},$

(5)

$q''=2{\frac {b-2a+(a-b)3t}{{(x_{2}-x_{1})}^{2}}}.$

(6)

समुच्चयिंग t = 0 और t = 1 क्रमशः समीकरणों में (5) और (6), एक से मिलता है (2) वह वास्तव में पहला व्युत्पन्न है q′(x₁) = k₁ और q′(x₂) = k₂, और दूसरा डेरिवेटिव भी

$q''(x_{1})=2{\frac {b-2a}{{(x_{2}-x_{1})}^{2}}},$

(7)

$q''(x_{2})=2{\frac {a-2b}{{(x_{2}-x_{1})}^{2}}}.$

(8)

यदि अब (x_i, y_i), i = 0, 1, ..., n हैं n + 1 अंक, और

$q_{i}=(1-t)\,y_{i-1}+t\,y_{i}+t(1-t){\big (}(1-t)\,a_{i}+t\,b_{i}{\big )},$

(9)

जहां मैं = 1, 2, ..., एन, और $t={\tfrac {x-x_{i-1}}{x_{i}-x_{i-1}}}$ n तृतीय-डिग्री बहुपद प्रक्षेप हैं y अंतराल में x_i−1 ≤ x ≤ x_i i = 1, ..., n के लिए ऐसा कि q′_i (x_i) = q′_i+1(x_i) i = 1, ..., n − 1 के लिए, तो n बहुपद मिलकर अंतराल में एक अवकलनीय फलन को परिभाषित करते हैं x₀ ≤ x ≤ x_n, और

$a_{i}=k_{i-1}(x_{i}-x_{i-1})-(y_{i}-y_{i-1}),$

(10)

$b_{i}=-k_{i}(x_{i}-x_{i-1})+(y_{i}-y_{i-1})$

(11)

i = 1, ..., n, कहां के लिए

$k_{0}=q_{1}'(x_{0}),$

(12)

$k_{i}=q_{i}'(x_{i})=q_{i+1}'(x_{i}),\qquad i=1,\dots ,n-1,$

(13)

$k_{n}=q_{n}'(x_{n}).$

(14)

यदि क्रम k₀, k₁, ..., k_n ऐसा है कि, इसके अतिरिक्त, q′′_i(x_i) = q′′_i+1(x_i) i = 1, ..., n − 1 के लिए धारण करता है, तो परिणामी फलन में निरंतर दूसरा व्युत्पन्न भी होगा।

से (7), (8), (10) और (11) इस प्रकार है कि यह मामला है यदि और केवल यदि

${\frac {k_{i-1}}{x_{i}-x_{i-1}}}+\left({\frac {1}{x_{i}-x_{i-1}}}+{\frac {1}{x_{i+1}-x_{i}}}\right)2k_{i}+{\frac {k_{i+1}}{x_{i+1}-x_{i}}}=3\left({\frac {y_{i}-y_{i-1}}{{(x_{i}-x_{i-1})}^{2}}}+{\frac {y_{i+1}-y_{i}}{{(x_{i+1}-x_{i})}^{2}}}\right)$

(15)

i = 1, ..., n − 1 के लिए। संबंध (15) हैं n − 1 के लिए रैखिक समीकरण n + 1 मान k₀, k₁, ..., k_n.

स्पलाइन प्रक्षेप के लिए मॉडल होने वाले लोचदार रूलर के लिए, सबसे बाईं ओर की गाँठ के बाईं ओर और सबसे दाईं ओर की गाँठ के दाईं ओर शासक स्वतंत्र रूप से घूम सकता है और इसलिए एक सीधी रेखा का रूप ले लेगा q′′ = 0. जैसा q′′ का एक सतत कार्य होना चाहिए x, इसके अतिरिक्त प्राकृतिक विभाजन n − 1 रेखीय समीकरण (15) होना चाहिए

$q''_{1}(x_{0})=2{\frac {3(y_{1}-y_{0})-(k_{1}+2k_{0})(x_{1}-x_{0})}{{(x_{1}-x_{0})}^{2}}}=0,$

$q''_{n}(x_{n})=-2{\frac {3(y_{n}-y_{n-1})-(2k_{n}+k_{n-1})(x_{n}-x_{n-1})}{{(x_{n}-x_{n-1})}^{2}}}=0,$

यानी कि

${\frac {2}{x_{1}-x_{0}}}k_{0}+{\frac {1}{x_{1}-x_{0}}}k_{1}=3{\frac {y_{1}-y_{0}}{(x_{1}-x_{0})^{2}}},$

(16)

${\frac {1}{x_{n}-x_{n-1}}}k_{n-1}+{\frac {2}{x_{n}-x_{n-1}}}k_{n}=3{\frac {y_{n}-y_{n-1}}{(x_{n}-x_{n-1})^{2}}}.$

(17)

अंततः, (15) के साथ साथ (16) और (17) गठित करना n + 1 रैखिक समीकरण जो विशिष्ट रूप से परिभाषित करते हैं n + 1 पैरामीटर k₀, k₁, ..., k_n.

अन्य अंतिम स्थितियाँ मौजूद हैं, क्लैम्प्ड स्प्लाइन, जो स्प्लाइन के सिरों पर स्लोप को निर्दिष्ट करती है, और लोकप्रिय नॉट-ए-नॉट स्प्लाइन, जिसके लिए आवश्यक है कि तीसरा व्युत्पन्न भी निरंतर हो। x₁ और x_n−1 अंक. नॉट-अ-गाँठ स्पलाइन के लिए, अतिरिक्त समीकरण पढ़ेंगे:

$q'''_{1}(x_{1})=q'''_{2}(x_{1})\Rightarrow {\frac {1}{\Delta x_{1}^{2}}}k_{0}+\left({\frac {1}{\Delta x_{1}^{2}}}-{\frac {1}{\Delta x_{2}^{2}}}\right)k_{1}-{\frac {1}{\Delta x_{2}^{2}}}k_{2}=2\left({\frac {\Delta y_{1}}{\Delta x_{1}^{3}}}-{\frac {\Delta y_{2}}{\Delta x_{2}^{3}}}\right),$

$q'''_{n-1}(x_{n-1})=q'''_{n}(x_{n-1})\Rightarrow {\frac {1}{\Delta x_{n-1}^{2}}}k_{n-2}+\left({\frac {1}{\Delta x_{n-1}^{2}}}-{\frac {1}{\Delta x_{n}^{2}}}\right)k_{n-1}-{\frac {1}{\Delta x_{n}^{2}}}k_{n}=2\left({\frac {\Delta y_{n-1}}{\Delta x_{n-1}^{3}}}-{\frac {\Delta y_{n}}{\Delta x_{n}^{3}}}\right),$

कहाँ $\Delta x_{i}=x_{i}-x_{i-1},\ \Delta y_{i}=y_{i}-y_{i-1}$.

उदाहरण

तीन बिंदुओं के बीच घन प्राकृतिक विभाजनों के साथ अंतर्वेशन

तीन बिंदुओं के मामले में मान $k_{0},k_{1},k_{2}$ त्रिविकर्ण आव्यूह को हल करके पाए जाते हैं

${\begin{bmatrix}a_{11}&a_{12}&0\\a_{21}&a_{22}&a_{23}\\0&a_{32}&a_{33}\\\end{bmatrix}}{\begin{bmatrix}k_{0}\\k_{1}\\k_{2}\\\end{bmatrix}}={\begin{bmatrix}b_{1}\\b_{2}\\b_{3}\\\end{bmatrix}}$

साथ

$a_{11}={\frac {2}{x_{1}-x_{0}}},$

$a_{12}={\frac {1}{x_{1}-x_{0}}},$

$a_{21}={\frac {1}{x_{1}-x_{0}}},$

$a_{22}=2\left({\frac {1}{x_{1}-x_{0}}}+{\frac {1}{x_{2}-x_{1}}}\right),$

$a_{23}={\frac {1}{x_{2}-x_{1}}},$

$a_{32}={\frac {1}{x_{2}-x_{1}}},$

$a_{33}={\frac {2}{x_{2}-x_{1}}},$

$b_{1}=3{\frac {y_{1}-y_{0}}{(x_{1}-x_{0})^{2}}},$

$b_{2}=3\left({\frac {y_{1}-y_{0}}{{(x_{1}-x_{0})}^{2}}}+{\frac {y_{2}-y_{1}}{{(x_{2}-x_{1})}^{2}}}\right),$

$b_{3}=3{\frac {y_{2}-y_{1}}{(x_{2}-x_{1})^{2}}}.$

तीन बिंदुओं के लिए

$(-1,0.5),\ (0,0),\ (3,3),$

किसी को वह मिल जाता है

$k_{0}=-0.6875,\ k_{1}=-0.1250,\ k_{2}=1.5625,$

और से (10) और (11) वह

$a_{1}=k_{0}(x_{1}-x_{0})-(y_{1}-y_{0})=-0.1875,$

$b_{1}=-k_{1}(x_{1}-x_{0})+(y_{1}-y_{0})=-0.3750,$

$a_{2}=k_{1}(x_{2}-x_{1})-(y_{2}-y_{1})=-3.3750,$

$b_{2}=-k_{2}(x_{2}-x_{1})+(y_{2}-y_{1})=-1.6875.$

चित्र में, दो घन बहुपदों से युक्त स्पलाइन फलन $q_{1}(x)$ और $q_{2}(x)$ द्वारा दिए गए (9) यह प्रदर्शित है।

यह भी देखें

• घन हर्माइट स्पलाइन
• सेंट्रिपेटल कैटमुल-रोम स्पलाइन
• असतत स्पलाइन प्रक्षेप
• मोनोटोन घन अंतर्वेशन
• गैर-समान तर्कसंगत बी-स्पलाइन
• बहुभिन्नरूपी प्रक्षेप
• बहुपद प्रक्षेप
• स्पलाइन को चिकना करना
• स्पलाइन तरंगिका
• पतली प्लेट स्पलाइन
• पॉलीहार्मोनिक स्पलाइन

कंप्यूटर कोड

TinySpline: स्पलाइन के लिए ओपन सोर्स सी-लाइब्रेरी जो घन स्पलाइन अंतर्वेशन लागू करती है

SciPy स्प्लाइन अंतर्वेशन: एक पायथन पैकेज जो अंतर्वेशन लागू करता है

घन अंतर्वेशन: घन स्पलाइन अंतर्वेशन के लिए ओपन सोर्स सी#-लाइब्रेरी

संदर्भ

• Schoenberg, Isaac J. (1946). "Contributions to the Problem of Approximation of Equidistant Data by Analytic Functions: Part A.—On the Problem of Smoothing or Graduation. A First Class of Analytic Approximation Formulae". Quarterly of Applied Mathematics. 4 (2): 45–99. doi:10.1090/qam/15914.
• Schoenberg, Isaac J. (1946). "Contributions to the Problem of Approximation of Equidistant Data by Analytic Functions: Part B.—On the Problem of Osculatory Interpolation. A Second Class of Analytic Approximation Formulae". Quarterly of Applied Mathematics. 4 (2): 112–141. doi:10.1090/qam/16705.

बाहरी संबंध

• Cubic Spline Interpolation Online Calculation and Visualization Tool (with JavaScript source code)
• "Spline interpolation", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
• Dynamic cubic splines with JSXGraph
• Lectures on the theory and practice of spline interpolation
• Paper which explains step by step how cubic spline interpolation is done, but only for equidistant knots.
• Numerical Recipes in C, Go to Chapter 3 Section 3-3
• A note on cubic splines
• Information about spline interpolation (including code in Fortran 77)