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

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

उदाहरण

नीचे की तालिका में ७ बिन्दुओं के निर्देशांक दिये हुए हैं। पास में ही इन बिन्दुओं की स्थिति लाल रंग के बिन्दुओं द्वारा दर्शायी गयी है।

x f(x) 0 0 1 0,8415 2 0,9093 3 0,1411 4 −0,7568 5 −0,9589 6 −0,2794

बायीं तरफ दी गयी सारणी के सात बिन्दु (लाल रंग में)

इन सातों बिन्दुओं के बीच कुल छः खण्ड हैं। बाएँ से दाएँ, इन खण्डों के बीच तीन-घात वाले निम्नलिखित बहुपद फिट किये जा सकते हैं।

$f(x)=\{\begin{array}{cc}-0,1522x^3+0,9937x,& \text{ for }x\in [0,1],\\ -0,01258x^3-0,4189x^2+1,4126x-0,1396,& \text{ for }x\in [1,2],\\ 0,1403x^3-1,3359x^2+3,2467x-1,3623,& \text{ for }x\in [2,3],\\ 0,1579x^3-1,4945x^2+3,7225x-1,8381,& \text{ for }x\in [3,4],\\ 0,05375x^3-0,2450x^2-1,2756x+4,8259,& \text{ for}x\in [4,5],\\ -0,1871x^3+3,3673x^2-19,3370x+34,9282,& \text{ for }x\in [5,6].\end{array}$

इतना ही नहीं, हम इन छः खण्डों के लिये सरल रेखा भी फिट कर सकते है, जो सबसे सरल है। इसी प्रकार ४,५ ६ या अधिक घात के बहुपद भी फिट किये जा सकते हैं। उपरोक्त तीन घात वाले बहुपदों में कुछ और भी गुण हैं जिनके कारण उन्हें 'सहज घन स्प्लाइन' (natural cubic spline) कहते हैं।

माना हमारे पास $n+1$ बिन्दुओं (knots) का एक अनुक्रम है जिसमें $(x_0,y_0)$ से लेकर $(x_n,y_n)$ बिन्दु हैं। दो क्रमागत बिन्दुओं $(x_{i-1},y_{i-1})$ और $(x_i,y_i)$ के बीच एक घन पद होगा (cubic polynomial) $q_i(x)=y$ होगा जो उन दोनों बिन्दुओं को जोड़ता है (यहाँ $i=1,2,\dots ,n$)। अर्थात $n$ बहुपद होंगे जिसमें से पहला बहुपद $(x_0,y_0)$ से आरम्भ होगा और अन्तिम बहुपद $(x_n,y_n)$ पर समाप्त होगा। इन घन पदों के निम्नलिखित गुण भी होने चाहिये-

$\{\begin{array}{c}{q}_i(x_i)=q_{i+1}(x_i)=y_i\\ q{\text{'}}_i(x_i)=q{\text{'}}_{i+1}(x_i)\\ q^{\prime }{\text{'}}_i(x_i)=q^{\prime }{\text{'}}_{i+1}(x_i)\end{array}1\le i\le n-1.$

यह तभी सम्भव है जब स्प्लाइन के लिये तीन घात वाले या उससे अधिक घात के बहुपदों का प्रयोग किया जाय। पहले से तीन घात वाले बहुपदों का उपयोग होता आया है।

ऊपर वर्णित तीन शर्तों के अलावा, यदि $q^{\prime }{\text{'}}_1(x_0)=q^{\prime }{\text{'}}_n(x_n)=0$ तो उसे 'सहज घन स्प्लाइन' कहते हैं।

ऊपर वर्णित तीन मुख्य शर्तों के अलावा यदि $q{\text{'}}_1(x_0)=f^{\prime }(x_0)$ तथा $q{\text{'}}_n(x_n)=f^{\prime }(x_n)$ जहाँ $f^{\prime }(x)$ इन्टर्पोलेशन बहुपद का अवकलज है तो ऐसे घन स्प्लाइन को तो a clamped cubic spline कहते हैं।

ऊपर वर्णित तीन मुख्य शर्तों के अलावा यदि $q^{″}{\text{'}}_1(x_1)=q^{″}{\text{'}}_2(x_1)$ तथा $q^{″}{\text{'}}_{n-1}(x_{n-1})=q^{″}{\text{'}}_n(x_{n-1})$. तो ऐसे घन स्प्लाइन को 'not-a-knot spline कहते हैं।

अन्तर्वेशी घन स्प्लाइन प्राप्त करने की कलन विधि

माना बहुपदों बिन्दु $(x_0,y_0)$ से लेकर $(x_n,y_n)$ तक दिये हुए हैम और हम सभी स्प्लाइन बहुपदों $q_i(x)$ को पाना चाहते हैं। इसके लिये हम केवल अकेली वक्र $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^{\prime }(x_1)=k_1,$

$q^{\prime }(x_2)=k_2.$

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

$q(x)=(1-t(x))y_1+t(x)y_2+t(x)(1-t(x))\left(\right(1-t(x))a+t(x)b),$ -- (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^{\prime }=\frac{dq}{dx}=\frac{dq}{dt}\frac{dt}{dx}=\frac{dq}{dt}\frac{1}{x_2-x_1}.$

इससे निम्नलिखित समीकरण प्राप्त होते हैं

$q^{\prime }=\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)

Setting साँचा:Math and साँचा:Math respectively in equations (5) and (6), one gets from (2) that indeed first derivatives साँचा:Math and साँचा:Math, and also second derivatives

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

If now साँचा:Math are साँचा:Math points, and

$q_i=(1-t)y_{i-1}+t{y}_i+t(1-t)((1-t)a_i+t{b}_i),$ -- (9)

where i = 1, 2, ..., n, and $t=\frac{x-x_{i-1}}{x_i-x_{i-1}}$ are n third-degree polynomials interpolating साँचा:Mvar in the interval साँचा:Math for i = 1, ..., n such that साँचा:Math for i = 1, ..., n − 1, then the n polynomials together define a differentiable function in the interval साँचा:Math, and

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

for i = 1, ..., n, where

$k_0={q_1}^{\prime }(x_0),$ -- (12)

$k_i={q_i}^{\prime }(x_i)=q_{i^{\prime }+1}(x_i),i=1,\dots ,n-1,$ -- (13)

$k_n={q_n}^{\prime }(x_n).$ -- (14)

If the sequence साँचा:Math is such that, in addition, साँचा:Math holds for i = 1, ..., n − 1, then the resulting function will even have a continuous second derivative.

From (7), (8), (10) and (11) follows that this is the case if and only if

$\frac{k_{i-1}}{x_i-x_{i-1}}+(\frac{1}{x_i-x_{i-1}}+\frac{1}{x_{i+1}-x_i})2k_i+\frac{k_{i+1}}{x_{i+1}-x_i}=3(\frac{y_i-y_{i-1}}{{(x_i-x_{i-1})}^2}+\frac{y_{i+1}-y_i}{{(x_{i+1}-x_i)}^2})$ -- (15)

for i = 1, ..., n − 1. The relations (15) are साँचा:Math linear equations for the साँचा:Math values साँचा:Math.

For the elastic rulers being the model for the spline interpolation, one has that to the left of the left-most "knot" and to the right of the right-most "knot" the ruler can move freely and will therefore take the form of a straight line with साँचा:Math. As साँचा:Mvar should be a continuous function of साँचा:Mvar, "natural splines" in addition to the साँचा:Math linear equations (15) should have

$q^{\prime }{\text{'}}_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^{\prime }{\text{'}}_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,$

i.e. that

$\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)

Eventually, (15) together with (16) and (17) constitute साँचा:Math linear equations that uniquely define the साँचा:Math parameters साँचा:Math.

There exist other end conditions, "clamped spline", which specifies the slope at the ends of the spline, and the popular "not-a-knot spline", which requires that the third derivative is also continuous at the साँचा:Math and साँचा:Math points. For the "not-a-knot" spline, the additional equations will read:

$q^{″}{\text{'}}_1(x_1)=q^{″}{\text{'}}_2(x_1)\Rightarrow \frac{1}{\mathrm{\Delta }{x}_1^2}{k}_0+(\frac{1}{\mathrm{\Delta }{x}_1^2}-\frac{1}{\mathrm{\Delta }{x}_2^2})k_1-\frac{1}{\mathrm{\Delta }{x}_2^2}{k}_2=2(\frac{\mathrm{\Delta }{y}_1}{\mathrm{\Delta }{x}_1^3}-\frac{\mathrm{\Delta }{y}_2}{\mathrm{\Delta }{x}_2^3}),$

$q^{″}{\text{'}}_{n-1}(x_{n-1})=q^{″}{\text{'}}_n(x_{n-1})\Rightarrow \frac{1}{\mathrm{\Delta }{x}_{n-1}^2}{k}_{n-2}+(\frac{1}{\mathrm{\Delta }{x}_{n-1}^2}-\frac{1}{\mathrm{\Delta }{x}_n^2})k_{n-1}-\frac{1}{\mathrm{\Delta }{x}_n^2}{k}_n=2(\frac{\mathrm{\Delta }{y}_{n-1}}{\mathrm{\Delta }{x}_{n-1}^3}-\frac{\mathrm{\Delta }{y}_n}{\mathrm{\Delta }{x}_n^3}),$

जहाँ $\mathrm{\Delta }{x}_i=x_i-x_{i-1},\mathrm{\Delta }{y}_i=y_i-y_{i-1}$.

इन्हें भी देखें

• स्प्लाइन