रेमेज़ एल्गोरिथ्म

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

चेबीशेव स्पेस का विशिष्ट उदाहरण अंतराल (गणित), सी [ए, बी] पर वास्तविक निरंतर कार्यों के सदिश स्थल में क्रम एन के चेबीशेव बहुपदों का उप-स्थान होता है। इस प्रकार किसी दिए गए उप-स्थान के अंदर सर्वोत्तम सन्निकटन के बहुपद को उस बहुपद के रूप में परिभाषित किया जाता है जो बहुपद और फलन के मध्य अधिकतम पूर्ण अंतर को कम करता है। इस स्थिति में, समाधान का रूप समद्विबाहु प्रमेय द्वारा त्रुटिहीन होता है।

प्रक्रिया

रेमेज़ एल्गोरिदम फलन से प्रारंभ होता है, जिससे कि $f$ का अनुमान लगाया जाता है और समुच्चय बनाया जाता है तब $X$ का $n+2$ नमूना बिंदु $x_{1},x_{2},...,x_{n+2}$ सन्निकटन अंतराल में, सामान्यतः चेबीशेव बहुपद का चरम रैखिक रूप से अंतराल पर मानचित्र किया जाता है। जिसमे निम्नलिखित चरण होते हैं।

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

$b_{0}+b_{1}x_{i}+...+b_{n}x_{i}^{n}+(-1)^{i}E=f(x_{i})$ (जहाँ $i=1,2,...n+2$),

अज्ञात के लिए $b_{0},b_{1}...b_{n}$ और ई.

• उपयोग $b_{i}$ बहुपद बनाने के लिए गुणांक के रूप में $P_{n}$.
• समुच्चय खोजे $M$ स्थानीय अधिकतम त्रुटि के अंक $|P_{n}(x)-f(x)|$.
• यदि त्रुटियाँ प्रत्येक स्थान हैं, तब $m\in M$ समान परिमाण और वैकल्पिक चिह्न के होते हैं $P_{n}$ न्यूनतम सन्निकटन बहुपद होता है। यदि ऐसा नहीं होता है, तब बदलें $X$ साथ $M$ और उपरोक्त चरणों को दोहराया जाता है।

परिणाम को सर्वोत्तम सन्निकटन का बहुपद या न्यूनतम सन्निकटन एल्गोरिथ्म कहा जाता है।

रेमेज़ एल्गोरिदम को क्रियान्वित करने में विधियों की समीक्षा डब्ल्यू फ्रेजर द्वारा दी गई है।

आरंभीकरण का विकल्प

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

$\lVert f-L_{n}(f)\rVert _{\infty }\leq (1+\lVert L_{n}\rVert _{\infty })\inf _{p\in P_{n}}\lVert f-p\rVert$

नोड्स का (t₁, ..., टी_n + 1) के लैग्रेंज इंटरपोलेशन ऑपरेटर एल_एन के मानक या लेबेस्ग स्थिरांक (इंटरपोलेशन) के साथ

$\lVert L_{n}\rVert _{\infty }={\overline {\Lambda }}_{n}(T)=\max _{-1\leq x\leq 1}\lambda _{n}(T;x),$

टी चेबीशेव बहुपदों का शून्य है, और लेबेस्ग फलन है

$\lambda _{n}(T;x)=\sum _{j=1}^{n+1}\left|l_{j}(x)\right|,\quad l_{j}(x)=\prod _{\stackrel {i=1}{i\neq j}}^{n+1}{\frac {(x-t_{i})}{(t_{j}-t_{i})}}.$

थियोडोर ए. किलगोर, कार्ल दे बूर, और अल्लन पिंकस ने सिद्ध किया है कि प्रत्येक एल_एन के लिए अद्वितीय टी_आई उपस्तिथ होता है, चूंकि (साधारण) बहुपदों के लिए स्पष्ट रूप से ज्ञात नहीं होता है। इसी प्रकार, ${\underline {\Lambda }}_{n}(T)=\min _{-1\leq x\leq 1}\lambda _{n}(T;x)$, और नोड्स की पसंद की इष्टतमता को ${\overline {\Lambda }}_{n}-{\underline {\Lambda }}_{n}\geq 0.$ द्वरा व्यक्त किया जा सकता है।

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

${\overline {\Lambda }}_{n}(T)={\frac {2}{\pi }}\log(n+1)+{\frac {2}{\pi }}\left(\gamma +\log {\frac {8}{\pi }}\right)+\alpha _{n+1}$

(γ यूलर-माशेरोनी स्थिरांक होने के नाते) के साथ

$0<\alpha _{n}<{\frac {\pi }{72n^{2}}}$ के लिए $n\geq 1,$

और ऊपरी सीमा

${\overline {\Lambda }}_{n}(T)\leq {\frac {2}{\pi }}\log(n+1)+1$

लेव ब्रूटमैन के लिए बाध्य प्राप्त किया $n\geq 3$, और ${\hat {T}}$ विस्तारित चेबीशेव बहुपदों का शून्य होता है।

${\overline {\Lambda }}_{n}({\hat {T}})-{\underline {\Lambda }}_{n}({\hat {T}})<{\overline {\Lambda }}_{3}-{\frac {1}{6}}\cot {\frac {\pi }{8}}+{\frac {\pi }{64}}{\frac {1}{\sin ^{2}(3\pi /16)}}-{\frac {2}{\pi }}(\gamma -\log \pi )\approx 0.201.$

रुएडिगर गुंटनर के लिए तीव्र अनुमान से $n\geq 40$ प्राप्त किया गया है।

${\overline {\Lambda }}_{n}({\hat {T}})-{\underline {\Lambda }}_{n}({\hat {T}})<0.0196.$

विस्तृत चर्चा

यह अनुभाग ऊपर उल्लिखित चरणों पर अधिक जानकारी प्रदान करता है। इस अनुभाग में, सूचकांक आई 0 से एन+1 तक चलता है।

चरण 1: दिया गया $x_{0},x_{1},...x_{n+1}$, एन+2 समीकरणों की रैखिक प्रणाली को हल करें

$b_{0}+b_{1}x_{i}+...+b_{n}x_{i}^{n}+(-1)^{i}E=f(x_{i})$ (कहाँ $i=0,1,...n+1$),

अज्ञात लोगों के लिए $b_{0},b_{1},...b_{n}$ और ई.

यह स्पष्ट होता है कि $(-1)^{i}E$ इस समीकरण में केवल तभी समझ में आता है जब नोड्स $x_{0},...,x_{n+1}$ या तब सख्ती से बढ़ाने या सख्ती से घटाने का आदेश दिया जाता है। इस प्रकार फिर इस रैखिक प्रणाली का अनोखा समाधान है। (जैसा कि सर्वविदित है, प्रत्येक रैखिक प्रणाली का कोई समाधान नहीं होता है।) साथ ही, समाधान केवल प्राप्त किया जा सकता है $O(n^{2})$ अंकगणित संचालन जबकि पुस्तकालय से मानक सॉल्वर लेगा $O(n^{3})$ परिचालन यहाँ सरल प्रमाण होता है।

मानक एन-वें डिग्री इंटरपोलेंट की गणना करें $p_{1}(x)$ को $f(x)$ पहले एन+1 नोड्स पर और मानक एन-वें डिग्री इंटरपोलेंट पर भी$p_{2}(x)$ निर्देशांक के लिए $(-1)^{i}$

$p_{1}(x_{i})=f(x_{i}),p_{2}(x_{i})=(-1)^{i},i=0,...,n.$

इस प्रयोजन के लिए, प्रत्येक बार विभाजित अंतरों के साथ न्यूटन के प्रक्षेप सूत्र का उपयोग करके $0,...,n$ और $O(n^{2})$ अंकगणितीय संक्रियाएँ होती है।

बहुपद $p_{2}(x)$ के मध्य इसका आई-वाँ शून्य है $x_{i-1}$ और $x_{i},\ i=1,...,n$, और इस प्रकार मध्य में कोई और शून्य नहीं होता है $x_{n}$ और $x_{n+1}$: $p_{2}(x_{n})$ और $p_{2}(x_{n+1})$ ही चिन्ह $(-1)^{n}$ होता है।

रैखिक संयोजन $p(x):=p_{1}(x)-p_{2}(x)\!\cdot \!E$ घात एन का बहुपद भी होता है और

$p(x_{i})=p_{1}(x_{i})-p_{2}(x_{i})\!\cdot \!E\ =\ f(x_{i})-(-1)^{i}E,\ \ \ \ i=0,\ldots ,n.$

यह उपरोक्त समीकरण के समान होता है $i=0,...,n$ और ई के किसी भी विकल्प के लिए आई = एन+1 के लिए भी यही समीकरण होता है

$p(x_{n+1})\ =\ p_{1}(x_{n+1})-p_{2}(x_{n+1})\!\cdot \!E\ =\ f(x_{n+1})-(-1)^{n+1}E$ और विशेष तर्क की आवश्यकता है और चर ई के लिए हल किया गया है, अतः यह ई की परिभाषा है।

$E\ :=\ {\frac {p_{1}(x_{n+1})-f(x_{n+1})}{p_{2}(x_{n+1})+(-1)^{n}}}.$

जैसा कि ऊपर बताया गया है, प्रत्येक में दो पदों का चिह्न ही है।

ई और इस प्रकार $p(x)\equiv b_{0}+b_{1}x+\ldots +b_{n}x^{n}$ सदैव अच्छी प्रकार से परिभाषित होते हैं।

दिए गए एन+2 क्रमित नोड्स पर त्रुटि धनात्मक और ऋणात्मक होते है जिससे कि

$p(x_{i})-f(x_{i})\ =\ -(-1)^{i}E,\ \ i=0,...,n\!+\!1.$

चार्ल्स जीन डी ला वेली पॉसिन के प्रमेय में कहा गया है कि इस स्थिति के अनुसार डिग्री एन का कोई भी बहुपद ई से कम त्रुटि के साथ उपस्तिथ नहीं होता है। वास्तव में, यदि ऐसा कोई बहुपद अस्तित्व में होता है, तब इसे कॉल करें ${\tilde {p}}(x)$, तब अंतर

$p(x)-{\tilde {p}}(x)=(p(x)-f(x))-({\tilde {p}}(x)-f(x))$ एन+2 नोड्स पर अभी भी धनात्मक/ऋणात्मक होता है $x_{i}$ और इसलिए कम से कम एन+1 शून्य होता है जो कि घात एन वाले बहुपद के लिए असंभव होता है।

इस प्रकार, यह ई न्यूनतम त्रुटि के लिए निचली सीमा होती है जिसे डिग्री एन के बहुपदों के साथ प्राप्त किया जा सकता है।

चरण 2 से $b_{0}+b_{1}x+...+b_{n}x^{n}$ को $p(x)$ अंकन परिवर्तित जाता है।

चरण 3 इनपुट नोड्स $x_{0},...,x_{n+1}$ में सुधार करता है और उनकी त्रुटियाँ $\pm E$ के निम्नानुसार होती है।

प्रत्येक पी-क्षेत्र में, वर्तमान नोड $x_{i}$ स्थानीय मैक्सिमाइज़र से परिवर्तित कर दिया गया है ${\bar {x}}_{i}$ और प्रत्येक एन-क्षेत्र में $x_{i}$ इसे स्थानीय न्यूनतम से परिवर्तित कर दिया गया है। (अपेक्षा करना ${\bar {x}}_{0}$ ए पर, द ${\bar {x}}_{i}$ पास में $x_{i}$, और ${\bar {x}}_{n+1}$ बी पर) यहां किसी उच्च परिशुद्धता की आवश्यकता नहीं होती है।

कुछ द्विघात फिटों के साथ मानक पंक्ति खोज पर्याप्त होती है। (देखना)

होने देना $z_{i}:=p({\bar {x}}_{i})-f({\bar {x}}_{i})$ प्रत्येक आयाम $|z_{i}|$ ई से बड़ा या उसके सामान्तर होता है। इस प्रकार डी ला वैली पॉसिन का प्रमेय और इसका प्रमाण भी क्रियान्वित $z_{0},...,z_{n+1}$ साथ $\min\{|z_{i}|\}\geq E$ नये के रूप में घात एन वाले बहुपदों के साथ संभव सर्वोत्तम त्रुटि के लिए निचली सीमा होती है।

इसके अतिरिक्त, $\max\{|z_{i}|\}$ उस सर्वोत्तम संभव त्रुटि के लिए स्पष्ट ऊपरी सीमा के रूप में कार्य में आता है।

चरण 4: के साथ $\min \,\{|z_{i}|\}$ और $\max \,\{|z_{i}|\}$ सर्वोत्तम संभव सन्निकटन त्रुटि के लिए निचली और ऊपरी सीमा के रूप में, किसी के पास विश्वसनीय रोक मानदंड होता है। इस प्रकार चरणों को तब तक दोहराया जाता है जब तक $\max\{|z_{i}|\}-\min\{|z_{i}|\}$ पर्याप्त रूप से छोटा होता है या अब कम नहीं होता है। यह सीमाएँ प्रगति का संकेत देती हैं।

रूपांतर

एल्गोरिदम के कुछ संशोधन साहित्य में उपस्तिथ होता हैं। इसमे सम्मिलित है।

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

यह भी देखें

• अनुमान सिद्धांत

बाहरी संबंध

• Minimax Approximations and the Remez Algorithm, background chapter in the Boost Math Tools documentation, with link to an implementation in C++
• Intro to DSP
• Aarts, Ronald M.; Bond, Charles; Mendelsohn, Phil & Weisstein, Eric W. "Remez Algorithm". MathWorld.