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

रेमेज़ एल्गोरिथ्म या रेमेज़ एक्सचेंज एल्गोरिदम, 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.