दे बूर'स अल्गोरिथम

संख्यात्मक विश्लेषण के गणित उपक्षेत्र में डी बूर के एल्गोरिथ्म बी-स्पलाइन रूप में स्पलाइन वक्रों का मूल्यांकन करने के लिए एक बहुपद-समय और संख्यात्मक रूप से स्थिर एल्गोरिद्म है। यह बेज़ियर कर्व्स के लिए डी कास्टलजौ के एल्गोरिदम का सामान्यीकरण है। एल्गोरिथ्म कार्ल आर डी बूर द्वारा तैयार किया गया था। डी बूर एल्गोरिथम के सरलीकृत, संभावित तेज़ संस्करण बनाए गए हैं लेकिन वे तुलनात्मक रूप से कम स्थिरता से पीड़ित हैं। रेफरी>Lee, E. T. Y. (December 1982). "एक सरलीकृत बी-स्पलाइन संगणना रूटीन". Computing. Springer-Verlag. 29 (4): 365–371. doi:10.1007/BF02246763. S2CID 2407104.</रेफरी>

परिचय

बी-स्पलाइन का सामान्य परिचय बी-स्पलाइन में दिया गया है। यहां हम डी बूर के एल्गोरिदम पर चर्चा करते हैं, जो स्पलाइन वक्र का मूल्यांकन करने के लिए एक कुशल और संख्यात्मक रूप से स्थिर योजना है $\mathbf {S} (x)$ स्थिति पर $x$. वक्र को बी-स्पलाइन कार्यों के योग से बनाया गया है $B_{i,p}(x)$ संभावित वेक्टर-मूल्यवान स्थिरांक के साथ गुणा $\mathbf {c} _{i}$, नियंत्रण बिंदु कहा जाता है,

$\mathbf {S} (x)=\sum _{i}\mathbf {c} _{i}B_{i,p}(x).$

बी-आदेश की splines $p+1$ डिग्री के टुकड़े-वार बहुपद कार्य जुड़े हुए हैं $p$ गांठों के एक ग्रिड पर परिभाषित ${t_{0},\dots ,t_{i},\dots ,t_{m}}$ (हम हमेशा निम्नलिखित में शून्य-आधारित सूचकांकों का उपयोग करते हैं)। डी बूर का एल्गोरिदम बिग ओ नोटेशन का उपयोग करता है (पी²) + बिग ओ नोटेशन (पी) संचालन स्पलाइन वक्र का मूल्यांकन करने के लिए। नोट: बी-स्पलाइन|बी-स्पलाइन और क्लासिक प्रकाशनों के बारे में मुख्य लेख एक अलग संकेतन का उपयोग करें: बी-स्पलाइन को इस रूप में अनुक्रमित किया गया है $B_{i,n}(x)$ साथ $n=p+1$.

स्थानीय समर्थन

बी-स्प्लिंस को स्थानीय समर्थन प्राप्त है, जिसका अर्थ है कि बहुपद केवल परिमित डोमेन में सकारात्मक हैं और कहीं और शून्य हैं। कॉक्स-डी बूर पुनरावर्तन सूत्र यह दिखाता है:

$B_{i,0}(x):={\begin{cases}1&{\text{if }}\quad t_{i}\leq x<t_{i+1}\\0&{\text{otherwise}}\end{cases}}$

$B_{i,p}(x):={\frac {x-t_{i}}{t_{i+p}-t_{i}}}B_{i,p-1}(x)+{\frac {t_{i+p+1}-x}{t_{i+p+1}-t_{i+1}}}B_{i+1,p-1}(x).$

सूचकांक दें $k$ गाँठ अंतराल को परिभाषित करें जिसमें स्थिति हो, $x\in [t_{k},t_{k+1})$. हम पुनरावर्तन सूत्र में देख सकते हैं कि केवल B-splines के साथ $i=k-p,\dots ,k$ इस गाँठ अंतराल के लिए गैर-शून्य हैं। इस प्रकार, राशि कम हो जाती है:

$\mathbf {S} (x)=\sum _{i=k-p}^{k}\mathbf {c} _{i}B_{i,p}(x).$

यह इस प्रकार है $i\geq 0$ वह $k\geq p$. इसी तरह, हम पुनरावर्तन में देखते हैं कि उच्चतम क्वेरी गाँठ स्थान सूचकांक पर है $k+1+p$. इसका मतलब है कि कोई भी गाँठ अंतराल $[t_{k},t_{k+1})$ जो वास्तव में उपयोग किया जाता है वह कम से कम होना चाहिए $p$ पहले और बाद में अतिरिक्त गांठें। एक कंप्यूटर प्रोग्राम में, यह आमतौर पर पहले और आखिरी बार इस्तेमाल किए गए गाँठ स्थान को दोहराकर हासिल किया जाता है $p$ बार। उदाहरण के लिए, के लिए $p=3$ और वास्तविक गाँठ स्थान $(0,1,2)$, कोई नॉट वेक्टर को पैड करेगा $(0,0,0,0,1,2,2,2,2)$.

एल्गोरिथम

इन परिभाषाओं के साथ, अब हम डी बूर के एल्गोरिथम का वर्णन कर सकते हैं। एल्गोरिदम बी-स्पलाइन फ़ंक्शंस की गणना नहीं करता है $B_{i,p}(x)$ सीधे। इसके बजाय यह मूल्यांकन करता है $\mathbf {S} (x)$ समतुल्य पुनरावर्तन सूत्र के माध्यम से।

होने देना $\mathbf {d} _{i,r}$ के साथ नए नियंत्रण बिंदु बनें $\mathbf {d} _{i,0}:=\mathbf {c} _{i}$ के लिये $i=k-p,\dots ,k$. के लिये $r=1,\dots ,p$ निम्नलिखित पुनरावर्तन लागू होता है:

$\mathbf {d} _{i,r}=(1-\alpha _{i,r})\mathbf {d} _{i-1,r-1}+\alpha _{i,r}\mathbf {d} _{i,r-1};\quad i=k-p+r,\dots ,k$

$\alpha _{i,r}={\frac {x-t_{i}}{t_{i+1+p-r}-t_{i}}}.$

एक बार पुनरावृत्तियाँ पूर्ण हो जाने के बाद, हमारे पास है $\mathbf {S} (x)=\mathbf {d} _{k,p}$, जिसका अर्थ है कि $\mathbf {d} _{k,p}$ वांछित परिणाम है।

डी बूर का एल्गोरिदम बी-स्पलाइन की स्पष्ट गणना से अधिक कुशल है $B_{i,p}(x)$ कॉक्स-डी बूर पुनरावर्तन सूत्र के साथ, क्योंकि यह उन शर्तों की गणना नहीं करता है जो शून्य से गुणा करने की गारंटी हैं।

अनुकूलन

उपरोक्त एल्गोरिदम कंप्यूटर में कार्यान्वयन के लिए अनुकूलित नहीं है। इसके लिए स्मृति की आवश्यकता होती है $(p+1)+p+\dots +1=(p+1)(p+2)/2$ अस्थायी नियंत्रण बिंदु $\mathbf {d} _{i,r}$. प्रत्येक अस्थायी नियंत्रण बिंदु को ठीक एक बार लिखा जाता है और दो बार पढ़ा जाता है। पुनरावृति को उल्टा करके $i$ (ऊपर की बजाय उलटी गिनती), हम एल्गोरिथ्म को केवल मेमोरी के साथ चला सकते हैं $p+1$ अस्थायी नियंत्रण बिंदु, देकर $\mathbf {d} _{i,r}$ के लिए स्मृति का पुन: उपयोग करें $\mathbf {d} _{i,r-1}$. इसी प्रकार, का केवल एक मूल्य है $\alpha$ प्रत्येक चरण में उपयोग किया जाता है, इसलिए हम मेमोरी का भी पुन: उपयोग कर सकते हैं।

इसके अलावा, शून्य-आधारित इंडेक्स का उपयोग करना अधिक सुविधाजनक है $j=0,\dots ,p$ अस्थायी नियंत्रण बिंदुओं के लिए। पिछले सूचकांक से संबंध है $i=j+k-p$. इस प्रकार हम बेहतर एल्गोरिथम प्राप्त करते हैं:

होने देना $\mathbf {d} _{j}:=\mathbf {c} _{j+k-p}$ के लिये $j=0,\dots ,p$. के लिए पुनरावृत्त करें $r=1,\dots ,p$:

$\mathbf {d} _{j}:=(1-\alpha _{j})\mathbf {d} _{j-1}+\alpha _{j}\mathbf {d} _{j};\quad j=p,\dots ,r\quad$ ($j$ नीचे गिना जाना चाहिए)

$\alpha _{j}:={\frac {x-t_{j+k-p}}{t_{j+1+k-r}-t_{j+k-p}}}.$

पुनरावृत्तियों के पूर्ण होने के बाद, परिणाम है $\mathbf {S} (x)=\mathbf {d} _{p}$.

उदाहरण कार्यान्वयन

पायथन (प्रोग्रामिंग भाषा) में निम्नलिखित कोड अनुकूलित एल्गोरिथम का एक सहज कार्यान्वयन है।

<वाक्यविन्यास लैंग = अजगर> डेफ डीबोर (के: इंट, एक्स: इंट, टी, सी, पी: इंट):

      एस (एक्स) का मूल्यांकन करता है।

   बहस
   ---------
   k: गाँठ अंतराल का सूचकांक जिसमें x होता है।
   एक्स: स्थिति।
   टी: गाँठ की स्थिति की सरणी, जैसा कि ऊपर वर्णित है, को गद्देदार करने की आवश्यकता है।
   सी: नियंत्रण बिंदुओं की सरणी।
   पी: बी-स्पलाइन की डिग्री।
      
   d = [c[j + k - p] for j in range(0, p + 1)]

   रेंज में आर के लिए (1, पी + 1):
       जे के लिए सीमा में (पी, आर - 1, -1):
           अल्फा = (एक्स - टी [जे + के - पी]) / (टी [जे + 1 + के - आर] - टी [जे + के - पी])
           डी [जे] = (1.0 - अल्फा) * डी [जे - 1] + अल्फा * डी [जे]

   रिटर्न डी [पी]

</वाक्यविन्यास हाइलाइट>

यह भी देखें

• Casteljau के एल्गोरिथम से
• बेज़ियर वक्र
• NURBS

बाहरी संबंध

• De Boor's Algorithm
• The DeBoor-Cox Calculation

कंप्यूटर कोड

• PPPACK: फोरट्रान में कई स्पलाइन एल्गोरिदम शामिल हैं
• जीएनयू साइंटिफिक लाइब्रेरी: सी-लाइब्रेरी में नेटलिब से पोर्ट की गई स्प्लाइन्स के लिए एक सब-लाइब्रेरी है
• SciPy: पायथन-लाइब्रेरी, में एक सब-लाइब्रेरी शामिल है।
• TinySpline: C++ रैपर के साथ स्प्लिन के लिए C-लाइब्रेरी और C#, Java, Lua, PHP, Python, और Ruby के लिए बाइंडिंग
• Einspline: फोरट्रान रैपर के साथ 1, 2, और 3 आयामों में स्प्लाइन के लिए सी-लाइब्रेरी

संदर्भ

Works cited

• Carl de Boor (2003). A Practical Guide to Splines, Revised Edition. Springer-Verlag. ISBN 0-387-95366-3.