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

{{Short description|Algorithm to approximate functions}}
'''रेमेज़ एल्गोरिथ्म''' या '''रेमेज़ एक्सचेंज एल्गोरिदम''', सन्न 1934 में [[एवगेनी याकोवलेविच रेमेज़]] द्वारा प्रकाशित, पुनरावृत्त एल्गोरिदम है जिसका उपयोग कार्यों के लिए सरल सन्निकटन खोजने के लिए किया जाता है, विशेष रूप से, चेबीशेव अंतरिक्ष में कार्यों द्वारा सन्निकटन जो समान मानदंड एल<sub>∞</sub> में सर्वश्रेष्ठ होता हैं।<ref>E. Ya. Remez, "Sur la détermination des polynômes d'approximation de degré donnée", Comm. Soc. Math. Kharkov '''10''', 41 (1934);<br/>"Sur un procédé convergent d'approximations successives pour déterminer les polynômes d'approximation, Compt. Rend. Acad. Sc. '''198''', 2063 (1934);<br/>"Sur le calcul effectiv des polynômes d'approximation des Tschebyscheff", Compt. Rend. Acade. Sc. '''199''', 337 (1934).</ref> इसे कभी-कभी '''रेम्स एल्गोरिथम''' या '''रेमे एल्गोरिथम''' के रूप में जाना जाता है।

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

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

* समीकरणों की रैखिक प्रणाली को हल करें
:<math> b_0 + b_1 x_i+ ... +b_n x_i ^ n + (-1)^ i E = f(x_i) </math> (जहाँ <math> i=1, 2, ... n+2 </math>),
:अज्ञात के लिए <math>b_0, b_1...b_n</math> और ई.
* उपयोग <math> b_i </math> बहुपद बनाने के लिए गुणांक के रूप में <math>P_n</math>.
* समुच्चय खोजे <math>M</math> स्थानीय अधिकतम त्रुटि के अंक <math>|P_n(x) - f(x)| </math>.
*यदि त्रुटियाँ प्रत्येक स्थान हैं, तब <math> m \in M </math> समान परिमाण और वैकल्पिक चिह्न के होते हैं <math>P_n</math> न्यूनतम सन्निकटन बहुपद होता है। यदि ऐसा नहीं होता है, तब बदलें <math>X</math> साथ <math>M</math> और उपरोक्त चरणों को दोहराया जाता है।

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

रेमेज़ एल्गोरिदम को क्रियान्वित करने में विधियों की समीक्षा डब्ल्यू फ्रेजर द्वारा दी गई है।<ref>{{cite journal |doi=10.1145/321281.321282 |first=W. |last=Fraser |title=एकल स्वतंत्र चर के कार्यों के लिए मिनिमैक्स और निकट-मिनमैक्स बहुपद अनुमानों की गणना के तरीकों का एक सर्वेक्षण|journal=J. ACM |volume=12 |pages=295–314 |year=1965 |issue=3 |s2cid=2736060 }}</ref>
===आरंभीकरण का विकल्प===
बहुपद प्रक्षेप के सिद्धांत में उनकी भूमिका के कारण चेबीशेव नोड्स प्रारंभिक सन्निकटन के लिए सामान्य पसंद हैं। इस प्रकार लैग्रेंज इंटरपोलेंट एल<sub>एन</sub>(एफ) द्वारा फलन एफ के लिए अनुकूलन समस्या के प्रारंभ के लिए, यह दिखाया जा सकता है कि यह प्रारंभिक सन्निकटन किसके द्वारा सीमित है

:<math>\lVert f - L_n(f)\rVert_\infty \le (1 + \lVert L_n\rVert_\infty) \inf_{p \in P_n} \lVert f - p\rVert</math>
नोड्स का (t<sub>1</sub>, ..., टी<sub>''n''&nbsp;+&nbsp;1</sub>) के लैग्रेंज इंटरपोलेशन ऑपरेटर एल<sub>एन</sub> के मानक या लेबेस्ग स्थिरांक (इंटरपोलेशन) के साथ

:<math>\lVert L_n\rVert_\infty = \overline{\Lambda}_n(T) = \max_{-1 \le x \le 1} \lambda_n(T; x),</math>
टी चेबीशेव बहुपदों का शून्य है, और लेबेस्ग फलन है

:<math>\lambda_n(T; x) = \sum_{j = 1}^{n + 1} \left| l_j(x) \right|, \quad l_j(x) = \prod_{\stackrel{i = 1}{i \ne j}}^{n + 1} \frac{(x - t_i)}{(t_j - t_i)}.</math>
थियोडोर ए. किलगोर,<ref>{{cite journal |doi=10.1016/0021-9045(78)90013-8 |first=T. A. |last=Kilgore |title=न्यूनतम Tchebycheff मानदंड के साथ लैग्रेंज इंटरपोलेटिंग प्रक्षेपण का एक लक्षण वर्णन|journal=J. Approx. Theory |volume=24 |pages=273–288 |year=1978 |issue=4 |doi-access=free }}</ref> कार्ल दे बूर, और अल्लन पिंकस<ref>{{cite journal |doi=10.1016/0021-9045(78)90014-X |first1=C. |last1=de Boor |first2=A. |last2=Pinkus |title=Proof of the conjectures of Bernstein and Erdös concerning the optimal nodes for polynomial interpolation |journal=[[Journal of Approximation Theory]] |volume=24 |pages=289–303 |year=1978 |issue=4 |doi-access=free }}</ref> ने सिद्ध किया है कि प्रत्येक एल<sub>एन</sub> के लिए अद्वितीय टी<sub>आई</sub> उपस्तिथ होता है, चूंकि (साधारण) बहुपदों के लिए स्पष्ट रूप से ज्ञात नहीं होता है। इसी प्रकार, <math>\underline{\Lambda}_n(T) = \min_{-1 \le x \le 1} \lambda_n(T; x)</math>, और नोड्स की पसंद की इष्टतमता को <math>\overline{\Lambda}_n - \underline{\Lambda}_n \ge 0.</math> द्वरा व्यक्त किया जा सकता है।

चेबीशेव नोड्स के लिए, जो उप-इष्टतम, किन्तु विश्लेषणात्मक रूप से स्पष्ट विकल्प प्रदान करता है, जिसे स्पर्शोन्मुख व्यवहार के रूप में जाना जाता है।<ref>{{cite journal |first1=F. W. |last1=Luttmann |first2=T. J. |last2=Rivlin |title=बहुपद प्रक्षेप के सिद्धांत में कुछ संख्यात्मक प्रयोग|journal=IBM J. Res. Dev. |volume=9 |pages=187–191 |year=1965 |issue=3 |doi= 10.1147/rd.93.0187}}</ref>
:<math>\overline{\Lambda}_n(T) = \frac{2}{\pi} \log(n + 1) + \frac{2}{\pi}\left(\gamma + \log\frac{8}{\pi}\right) + \alpha_{n + 1}</math>
({{math|''γ''}} यूलर-माशेरोनी स्थिरांक होने के नाते) के साथ

:<math>0 < \alpha_n < \frac{\pi}{72 n^2}</math> के लिए <math>n \ge 1,</math>
और ऊपरी सीमा<ref>T. Rivlin, "The Lebesgue constants for polynomial interpolation", in ''Proceedings of the Int. Conf. on Functional Analysis and Its Application'', edited by H. G. Garnier ''et al.'' (Springer-Verlag, Berlin, 1974), p. 422; ''The Chebyshev polynomials'' (Wiley-Interscience, New York, 1974).</ref>
:<math>\overline{\Lambda}_n(T) \le \frac{2}{\pi} \log(n + 1) + 1</math>
लेव ब्रूटमैन<ref>{{cite journal |doi=10.1137/0715046 |first=L. |last=Brutman |title=बहुपद अंतर्वेशन के लिए लेबेस्ग फ़ंक्शन पर|journal=SIAM J. Numer. Anal. |volume=15 |pages=694–704 |year=1978 |issue=4 |bibcode=1978SJNA...15..694B }}</ref> के लिए बाध्य प्राप्त किया <math>n \ge 3</math>, और <math>\hat{T}</math> विस्तारित चेबीशेव बहुपदों का शून्य होता है।

:<math>\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.</math>
रुएडिगर गुंटनर<ref>{{cite journal |doi=10.1137/0717043 |first=R. |last=Günttner |title=लेब्सेग स्थिरांक का मूल्यांकन|journal=SIAM J. Numer. Anal. |volume=17 |pages=512–520 |year=1980 |issue=4 |bibcode=1980SJNA...17..512G }}</ref> के लिए तीव्र अनुमान से <math>n \ge 40</math> प्राप्त किया गया है।
:<math>\overline{\Lambda}_n(\hat{T}) - \underline{\Lambda}_n(\hat{T}) < 0.0196.</math>
==विस्तृत चर्चा==
यह अनुभाग ऊपर उल्लिखित चरणों पर अधिक जानकारी प्रदान करता है। इस अनुभाग में, सूचकांक आई 0 से एन+1 तक चलता है।

'''चरण 1''': दिया गया <math>x_0, x_1, ... x_{n+1}</math>, एन+2 समीकरणों की रैखिक प्रणाली को हल करें
:<math> b_0 + b_1 x_i+ ... +b_n x_i ^ n + (-1) ^ i E = f(x_i) </math> (कहाँ <math> i=0, 1, ... n+1 </math>),
:अज्ञात लोगों के लिए <math>b_0, b_1, ...b_n</math> और ई.

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

मानक एन-वें डिग्री इंटरपोलेंट की गणना करें <math>p_1(x)</math> को <math>f(x)</math> पहले एन+1 नोड्स पर और मानक एन-वें डिग्री इंटरपोलेंट पर भी<math>p_2(x)</math> निर्देशांक के लिए <math>(-1)^i</math>
:<math>p_1(x_i) = f(x_i), p_2(x_i) = (-1)^i, i = 0, ..., n.</math>
इस प्रयोजन के लिए, प्रत्येक बार विभाजित अंतरों के साथ न्यूटन के प्रक्षेप सूत्र का उपयोग करके  <math>0, ...,n</math> और <math>O(n^2)</math> अंकगणितीय संक्रियाएँ होती है।

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

रैखिक संयोजन <math>p(x) := p_1 (x) - p_2(x)\!\cdot\!E</math> घात एन का बहुपद भी होता है और
:<math>p(x_i) = p_1(x_i) - p_2(x_i)\!\cdot\! E \ = \ f(x_i) - (-1)^i E,\ \ \ \  i =0, \ldots, n.</math>
यह उपरोक्त समीकरण के समान होता है <math>i = 0, ... ,n</math> और ई के किसी भी विकल्प के लिए आई = एन+1 के लिए भी यही समीकरण होता है
:<math>p(x_{n+1}) \ = \ p_1(x_{n+1}) - p_2(x_{n+1})\!\cdot\!E \ = \ f(x_{n+1}) - (-1)^{n+1} E</math> और विशेष तर्क की आवश्यकता है और चर ई के लिए हल किया गया है, अतः यह ई की परिभाषा है।
:<math>E \ := \ \frac{p_1(x_{n+1}) - f(x_{n+1})}{p_2(x_{n+1}) + (-1)^n}.</math>
जैसा कि ऊपर बताया गया है, प्रत्येक में दो पदों का चिह्न ही है।

ई और इस प्रकार <math>p(x) \equiv b_0 + b_1x + \ldots + b_nx^n</math> सदैव अच्छी प्रकार से परिभाषित होते हैं।

दिए गए एन+2 क्रमित नोड्स पर त्रुटि धनात्मक और ऋणात्मक होते है जिससे कि
:<math>p(x_i) - f(x_i) \ = \ -(-1)^i E,\ \ i = 0, ... , n\!+\!1. </math>
चार्ल्स जीन डी ला वेली पॉसिन के प्रमेय में कहा गया है कि इस स्थिति के अनुसार डिग्री एन का कोई भी बहुपद ई से कम त्रुटि के साथ उपस्तिथ नहीं होता है। वास्तव में, यदि ऐसा कोई बहुपद अस्तित्व में होता है, तब इसे कॉल करें <math>\tilde p(x)</math>, तब अंतर

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

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

'''चरण 2''' से <math>b_0 + b_1x + ... + b_nx^n</math> को <math>p(x)</math> अंकन परिवर्तित जाता है।

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

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

कुछ द्विघात फिटों के साथ मानक पंक्ति खोज पर्याप्त होती है। (देखना<ref>David G. Luenberger: ''Introduction to Linear and Nonlinear Programming'', Addison-Wesley Publishing Company 1973.</ref>)

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

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

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

==रूपांतर==
एल्गोरिदम के कुछ संशोधन साहित्य में उपस्तिथ होता हैं।<ref>{{Citation |last1=Egidi |first1=Nadaniela |title=A New Remez-Type Algorithm for Best Polynomial Approximation |date=2020 |url=http://link.springer.com/10.1007/978-3-030-39081-5_7 |work=Numerical Computations: Theory and Algorithms |volume=11973 |pages=56–69 |editor-last=Sergeyev |editor-first=Yaroslav D. |place=Cham |publisher=Springer International Publishing |language=en |doi=10.1007/978-3-030-39081-5_7 |isbn=978-3-030-39080-8 |access-date=2022-03-19 |last2=Fatone |first2=Lorella |last3=Misici |first3=Luciano |s2cid=211159177 |editor2-last=Kvasov |editor2-first=Dmitri E.}}</ref> इसमे सम्मिलित है।

* अधिक से अधिक नमूना बिंदु को निकटतम अधिकतम निरपेक्ष अंतर वाले स्थानों से परिवर्तित किया जाता है।
* सभी नमूना बिंदुओं को सभी के स्थानों, वैकल्पिक चिह्न, अधिकतम अंतर के साथ ही पुनरावृत्ति में परिवर्तित होता है।<ref name="toobs">Temes, G.C.; Barcilon, V.; Marshall, F.C. (1973). "The optimization of bandlimited systems". ''Proceedings of the IEEE''. '''61''' (2): 196–234. [[Doi (identifier)|doi]]:10.1109/PROC.1973.9004. [[ISSN (identifier)|ISSN]]&nbsp;0018-9219.</ref>
* सन्निकटन और फलन के मध्य अंतर को मापने के लिए सापेक्ष त्रुटि का उपयोग करना, विशेष रूप से यदि सन्निकटन का उपयोग कंप्यूटर पर फलन की गणना करने के लिए किया जाता है जो [[तैरनेवाला स्थल]] अंकगणित का उपयोग करता है।
* शून्य-त्रुटि बिंदु बाधाओं सहित।<ref name="toobs" />
*फ्रेज़र-हार्ट संस्करण, सर्वोत्तम तर्कसंगत चेबीशेव सन्निकटन निर्धारित करने के लिए उपयोग किया जाता है।<ref>{{Cite journal |last=Dunham |first=Charles B. |date=1975 |title=तर्कसंगत चेबीशेव सन्निकटन के लिए फ्रेजर-हार्ट एल्गोरिथ्म का अभिसरण|url=https://www.ams.org/mcom/1975-29-132/S0025-5718-1975-0388732-9/ |journal=Mathematics of Computation |language=en |volume=29 |issue=132 |pages=1078–1082 |doi=10.1090/S0025-5718-1975-0388732-9 |issn=0025-5718|doi-access=free }}</ref>
==यह भी देखें==
*अनुमान सिद्धांत

==संदर्भ==
{{Reflist}}


==बाहरी संबंध==
*[https://www.boost.org/doc/libs/1_47_0/libs/math/doc/sf_and_dist/html/math_toolkit/toolkit/internals2/minimax.html Minimax Approximations and the Remez Algorithm], background chapter in the [[Boost (C++ libraries)|Boost]] Math Tools documentation, with link to an implementation in C++
*[http://www.bores.com/courses/intro/filters/4_equi.htm Intro to DSP]
*{{MathWorld|urlname=RemezAlgorithm|title=Remez Algorithm|author1-link=Ronald Aarts|author=Aarts, Ronald M.|author2=Bond, Charles|author3=Mendelsohn, Phil|author4= Weisstein, Eric W.|name-list-style=amp}}

[[Category:CS1 English-language sources (en)]]
[[Category:Created On 27/07/2023]]
[[Category:Lua-based templates]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Short description with empty Wikidata description]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates that add a tracking category]]
[[Category:Templates that generate short descriptions]]
[[Category:Templates using TemplateData]]
[[Category:बहुपदों]]
[[Category:संख्यात्मक विश्लेषण]]
[[Category:सन्निकटन सिद्धांत]]