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

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

उदाहरण

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

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)=\left\{{\begin{matrix}-0{,}1522x^{3}+0{,}9937x,&{\mbox{ for }}x\in [0,1],\\-0{,}01258x^{3}-0{,}4189x^{2}+1{,}4126x-0{,}1396,&{\mbox{ for }}x\in [1,2],\\0{,}1403x^{3}-1{,}3359x^{2}+3{,}2467x-1{,}3623,&{\mbox{ for }}x\in [2,3],\\0{,}1579x^{3}-1{,}4945x^{2}+3{,}7225x-1{,}8381,&{\mbox{ for }}x\in [3,4],\\0{,}05375x^{3}-0{,}2450x^{2}-1{,}2756x+4{,}8259,&{\mbox{ for}}x\in [4,5],\\-0{,}1871x^{3}+3{,}3673x^{2}-19{,}3370x+34{,}9282,&{\mbox{ for }}x\in [5,6].\\\end{matrix}}\right.$

इतना ही नहीं, हम इन छः खण्डों के लिये सरल रेखा भी फिट कर सकते है, जो सबसे सरल है। इसी प्रकार ४,५ ६ या अधिक घात के बहुपद भी फिट किये जा सकते हैं। उपरोक्त तीन घात वाले बहुपदों में कुछ और भी गुण हैं जिनके कारण उन्हें 'सहज घन स्प्लाइन' (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{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.$

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

ऊपर वर्णित तीन शर्तों के अलावा, यदि $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)$ इन्टर्पोलेशन बहुपद का अवकलज है तो ऐसे घन स्प्लाइन को तो a clamped cubic spline कहते हैं।

ऊपर वर्णित तीन मुख्य शर्तों के अलावा यदि $q'''_{1}(x_{1})=q'''_{2}(x_{1})$ तथा $q'''_{n-1}(x_{n-1})=q'''_{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'(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)

Setting t = 0 and t = 1 respectively in equations (5) and (6), one gets from (2) that indeed first derivatives q′(x₁) = k₁ and q′(x₂) = k₂, 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 (x_i, y_i), i = 0, 1, ..., n are n + 1 points, and

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

where i = 1, 2, ..., n, and $t={\tfrac {x-x_{i-1}}{x_{i}-x_{i-1}}}$ are n third-degree polynomials interpolating y in the interval x_i−1 ≤ x ≤ x_i for i = 1, ..., n such that q′_i (x_i) = q′_i+1(x_i) for i = 1, ..., n − 1, then the n polynomials together define a differentiable function in the interval x₀ ≤ x ≤ x_n, 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}'(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)

If the sequence k₀, k₁, ..., k_n is such that, in addition, q′′_i(x_i) = q′′_i+1(x_i) 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}}}+\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)

for i = 1, ..., n − 1. The relations (15) are n − 1 linear equations for the n + 1 values k₀, k₁, ..., k_n.

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 q′′ = 0. As q′′ should be a continuous function of x, "natural splines" in addition to the n − 1 linear equations (15) should have

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

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 n + 1 linear equations that uniquely define the n + 1 parameters k₀, k₁, ..., k_n.

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 x₁ and x_n−1 points. For the "not-a-knot" spline, the additional equations will read:

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

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

• स्प्लाइन