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

रेमेज़ एल्गोरिथ्म या रेमेज़ एक्सचेंज एल्गोरिदम, सन्न 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$ और उपरोक्त चरणों को दोहराया जाता है।

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

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

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

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

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

लैग्रेंज इंटरपोलेशन ऑपरेटर एल के मानक या लेबेस्ग स्थिरांक (इंटरपोलेशन) के साथ_n नोड्स का (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})}}.$

थियोडोर ए. किलगोर, कार्ल दे बूर, एंड अल्लन पिंकस सिद्ध कर दिया कि अद्वितीय टी उपस्तिथ है_i प्रत्येक एल के लिए_n, चूंकि (साधारण) बहुपदों के लिए स्पष्ट रूप से ज्ञात नहीं है। इसी प्रकार, ${\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.$

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

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

'चरण 1:' दिया गया $x_{0},x_{1},...x_{n+1}$, n+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)$ पहले n+1 नोड्स पर और मानक n-वें डिग्री इंटरपोलेंट पर भी $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)$ के मध्य इसका i-th शून्य है $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$ घात n और का बहुपद भी है

$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$ और ई के किसी भी विकल्प के लिए. i = 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}$ सदैव अच्छी तरह से परिभाषित होते हैं।

दिए गए 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))$ n+2 नोड्स पर अभी भी धनात्मक/ऋणात्मक होगा $x_{i}$ और इसलिए कम से कम n+1 शून्य होना चाहिए जो कि घात n वाले बहुपद के लिए असंभव है।

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

'चरण 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$ नये के रूप में घात n वाले बहुपदों के साथ संभव सर्वोत्तम त्रुटि के लिए निचली सीमा।

इसके अतिरिक्त, $\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.