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

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)