रेमेज़ एल्गोरिथ्म: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
 
(5 intermediate revisions by 3 users not shown)
Line 1: Line 1:
{{Short description|Algorithm to approximate functions}}
{{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> इसे कभी-कभी रेम्स एल्गोरिथम या रेमे एल्गोरिथम के रूप में जाना जाता है।
'''रेमेज़ एल्गोरिथ्म''' या '''रेमेज़ एक्सचेंज एल्गोरिदम''', सन्न 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>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 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_0, b_1...b_n</math> और ई.
* उपयोग <math> b_i </math> बहुपद बनाने के लिए गुणांक के रूप में <math>P_n</math>.
* उपयोग <math> b_i </math> बहुपद बनाने के लिए गुणांक के रूप में <math>P_n</math>.
* सेट ढूंढें <math>M</math> स्थानीय अधिकतम त्रुटि के अंक <math>|P_n(x) - f(x)| </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> और उपरोक्त चरणों को दोहराएँ.
*यदि त्रुटियाँ प्रत्येक स्थान हैं, तब <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>
रेमेज़ एल्गोरिदम को क्रियान्वित करने में विधियों की समीक्षा डब्ल्यू फ्रेजर द्वारा दी गई है।<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>n</sub>(एफ), यह दिखाया जा सकता है कि यह प्रारंभिक सन्निकटन किसके द्वारा सीमित है
बहुपद प्रक्षेप के सिद्धांत में उनकी भूमिका के कारण चेबीशेव नोड्स प्रारंभिक सन्निकटन के लिए सामान्य पसंद हैं। इस प्रकार लैग्रेंज इंटरपोलेंट एल<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>
:<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>
लैग्रेंज इंटरपोलेशन ऑपरेटर एल के मानक या लेबेस्ग स्थिरांक (इंटरपोलेशन) के साथ<sub>''n''</sub> नोड्स का (t<sub>1</sub>, ..., टी<sub>''n''&nbsp;+&nbsp;1</sub>) प्राणी
नोड्स का (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>\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>
:<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>''i''</sub> प्रत्येक एल के लिए<sub>''n''</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 |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>
 
चेबीशेव नोड्स के लिए, जो उप-इष्टतम, किन्तु विश्लेषणात्मक रूप से स्पष्ट विकल्प प्रदान करता है, जिसे स्पर्शोन्मुख व्यवहार के रूप में जाना जाता है।<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>\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|''γ''}} यूलर-माशेरोनी स्थिरांक होने के नाते) के साथ
Line 35: Line 36:
और ऊपरी सीमा<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>
और ऊपरी सीमा<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>
:<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> विस्तारित चेबीशेव बहुपदों का शून्य होना:
लेव ब्रूटमैन<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>
:<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>
रुएडिगर गुंटनर<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>
:<math>\overline{\Lambda}_n(\hat{T}) - \underline{\Lambda}_n(\hat{T}) < 0.0196.</math>
==विस्तृत चर्चा==
==विस्तृत चर्चा==
यह अनुभाग ऊपर उल्लिखित चरणों पर अधिक जानकारी प्रदान करता है। इस अनुभाग में, सूचकांक i 0 से n+1 तक चलता है।
यह अनुभाग ऊपर उल्लिखित चरणों पर अधिक जानकारी प्रदान करता है। इस अनुभाग में, सूचकांक आई 0 से एन+1 तक चलता है।


'चरण 1:' दिया गया <math>x_0, x_1, ... x_{n+1}</math>, n+2 समीकरणों की रैखिक प्रणाली को हल करें
'''चरण 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 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>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>(-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> पहले n+1 नोड्स पर और मानक n-वें डिग्री इंटरपोलेंट पर भी
मानक एन-वें डिग्री इंटरपोलेंट की गणना करें <math>p_1(x)</math> को <math>f(x)</math> पहले एन+1 नोड्स पर और मानक एन-वें डिग्री इंटरपोलेंट पर भी<math>p_2(x)</math> निर्देशांक के लिए <math>(-1)^i</math>
<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>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>0, ...,n</math> और <math>O(n^2)</math> अंकगणितीय आपरेशनस।


बहुपद <math>p_2(x)</math> के बीच इसका i-th शून्य है <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_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) := p_1 (x) - p_2(x)\!\cdot\!E</math> घात n और का बहुपद भी है
:<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>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> और ई के किसी भी विकल्प के लिए.
यह उपरोक्त समीकरण के समान होता है <math>i = 0, ... ,n</math> और ई के किसी भी विकल्प के लिए आई = एन+1 के लिए भी यही समीकरण होता है
i = n+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>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>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> हमेशा अच्छी तरह से परिभाषित होते हैं।
ई और इस प्रकार <math>p(x) \equiv b_0 + b_1x + \ldots + b_nx^n</math> सदैव अच्छी प्रकार से परिभाषित होते हैं।


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


इस प्रकार, यह E न्यूनतम त्रुटि के लिए निचली सीमा है जिसे डिग्री n के बहुपदों के साथ प्राप्त किया जा सकता है।
<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>.
'''चरण 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> निम्नलिखित नुसार।
'''चरण 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> बी पर) यहां किसी उच्च परिशुद्धता की आवश्यकता नहीं है,
प्रत्येक पी-क्षेत्र में, वर्तमान नोड <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>)
कुछ द्विघात फिटों के साथ मानक पंक्ति खोज पर्याप्त होती है। (देखना<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_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>z_0, ... ,z_{n+1}</math> साथ <math>\min\{|z_i|\} \geq E</math> नये के रूप में
घात n वाले बहुपदों के साथ संभव सर्वोत्तम त्रुटि के लिए निचली सीमा।


इसके अतिरिक्त, <math>\max\{|z_i|\}</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> पर्याप्त रूप से छोटा है या अब कम नहीं होता है। ये सीमाएँ प्रगति का संकेत देती हैं।
'''चरण 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>{{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">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>
* शून्य-त्रुटि बिंदु बाधाओं सहित।<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>
==यह भी देखें==
==यह भी देखें==
*अनुमान सिद्धांत
*अनुमान सिद्धांत
Line 112: Line 106:
*[http://www.bores.com/courses/intro/filters/4_equi.htm Intro to DSP]
*[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}}
*{{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: बहुपदों]] [[Category: सन्निकटन सिद्धांत]] [[Category: संख्यात्मक विश्लेषण]]


[[Category: Machine Translated Page]]
[[Category:CS1 English-language sources (en)]]
[[Category:Created On 27/07/2023]]
[[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:सन्निकटन सिद्धांत]]

Latest revision as of 11:53, 12 August 2023

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

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

प्रक्रिया

रेमेज़ एल्गोरिदम फलन से प्रारंभ होता है, जिससे कि का अनुमान लगाया जाता है और समुच्चय बनाया जाता है तब का नमूना बिंदु सन्निकटन अंतराल में, सामान्यतः चेबीशेव बहुपद का चरम रैखिक रूप से अंतराल पर मानचित्र किया जाता है। जिसमे निम्नलिखित चरण होते हैं।

  • समीकरणों की रैखिक प्रणाली को हल करें
(जहाँ ),
अज्ञात के लिए और ई.
  • उपयोग बहुपद बनाने के लिए गुणांक के रूप में .
  • समुच्चय खोजे स्थानीय अधिकतम त्रुटि के अंक .
  • यदि त्रुटियाँ प्रत्येक स्थान हैं, तब समान परिमाण और वैकल्पिक चिह्न के होते हैं न्यूनतम सन्निकटन बहुपद होता है। यदि ऐसा नहीं होता है, तब बदलें साथ और उपरोक्त चरणों को दोहराया जाता है।

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

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

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

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

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

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

थियोडोर ए. किलगोर,[3] कार्ल दे बूर, और अल्लन पिंकस[4] ने सिद्ध किया है कि प्रत्येक एलएन के लिए अद्वितीय टीआई उपस्तिथ होता है, चूंकि (साधारण) बहुपदों के लिए स्पष्ट रूप से ज्ञात नहीं होता है। इसी प्रकार, , और नोड्स की पसंद की इष्टतमता को द्वरा व्यक्त किया जा सकता है।

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

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

के लिए

और ऊपरी सीमा[6]

लेव ब्रूटमैन[7] के लिए बाध्य प्राप्त किया , और विस्तारित चेबीशेव बहुपदों का शून्य होता है।

रुएडिगर गुंटनर[8] के लिए तीव्र अनुमान से प्राप्त किया गया है।

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

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

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

(कहाँ ),
अज्ञात लोगों के लिए और ई.

यह स्पष्ट होता है कि इस समीकरण में केवल तभी समझ में आता है जब नोड्स या तब सख्ती से बढ़ाने या सख्ती से घटाने का आदेश दिया जाता है। इस प्रकार फिर इस रैखिक प्रणाली का अनोखा समाधान है। (जैसा कि सर्वविदित है, प्रत्येक रैखिक प्रणाली का कोई समाधान नहीं होता है।) साथ ही, समाधान केवल प्राप्त किया जा सकता है अंकगणित संचालन जबकि पुस्तकालय से मानक सॉल्वर लेगा परिचालन यहाँ सरल प्रमाण होता है।

मानक एन-वें डिग्री इंटरपोलेंट की गणना करें को पहले एन+1 नोड्स पर और मानक एन-वें डिग्री इंटरपोलेंट पर भी निर्देशांक के लिए

इस प्रयोजन के लिए, प्रत्येक बार विभाजित अंतरों के साथ न्यूटन के प्रक्षेप सूत्र का उपयोग करके और अंकगणितीय संक्रियाएँ होती है।

बहुपद के मध्य इसका आई-वाँ शून्य है और , और इस प्रकार मध्य में कोई और शून्य नहीं होता है और : और ही चिन्ह होता है।

रैखिक संयोजन घात एन का बहुपद भी होता है और

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

और विशेष तर्क की आवश्यकता है और चर ई के लिए हल किया गया है, अतः यह ई की परिभाषा है।

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

ई और इस प्रकार सदैव अच्छी प्रकार से परिभाषित होते हैं।

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

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

एन+2 नोड्स पर अभी भी धनात्मक/ऋणात्मक होता है और इसलिए कम से कम एन+1 शून्य होता है जो कि घात एन वाले बहुपद के लिए असंभव होता है।

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

चरण 2 से को अंकन परिवर्तित जाता है।

चरण 3 इनपुट नोड्स में सुधार करता है और उनकी त्रुटियाँ के निम्नानुसार होती है।

प्रत्येक पी-क्षेत्र में, वर्तमान नोड स्थानीय मैक्सिमाइज़र से परिवर्तित कर दिया गया है और प्रत्येक एन-क्षेत्र में इसे स्थानीय न्यूनतम से परिवर्तित कर दिया गया है। (अपेक्षा करना ए पर, द पास में , और बी पर) यहां किसी उच्च परिशुद्धता की आवश्यकता नहीं होती है।

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

होने देना प्रत्येक आयाम ई से बड़ा या उसके सामान्तर होता है। इस प्रकार डी ला वैली पॉसिन का प्रमेय और इसका प्रमाण भी क्रियान्वित साथ नये के रूप में घात एन वाले बहुपदों के साथ संभव सर्वोत्तम त्रुटि के लिए निचली सीमा होती है।

इसके अतिरिक्त, उस सर्वोत्तम संभव त्रुटि के लिए स्पष्ट ऊपरी सीमा के रूप में कार्य में आता है।

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

रूपांतर

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

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

यह भी देखें

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

संदर्भ

  1. E. Ya. Remez, "Sur la détermination des polynômes d'approximation de degré donnée", Comm. Soc. Math. Kharkov 10, 41 (1934);
    "Sur un procédé convergent d'approximations successives pour déterminer les polynômes d'approximation, Compt. Rend. Acad. Sc. 198, 2063 (1934);
    "Sur le calcul effectiv des polynômes d'approximation des Tschebyscheff", Compt. Rend. Acade. Sc. 199, 337 (1934).
  2. Fraser, W. (1965). "एकल स्वतंत्र चर के कार्यों के लिए मिनिमैक्स और निकट-मिनमैक्स बहुपद अनुमानों की गणना के तरीकों का एक सर्वेक्षण". J. ACM. 12 (3): 295–314. doi:10.1145/321281.321282. S2CID 2736060.
  3. Kilgore, T. A. (1978). "न्यूनतम Tchebycheff मानदंड के साथ लैग्रेंज इंटरपोलेटिंग प्रक्षेपण का एक लक्षण वर्णन". J. Approx. Theory. 24 (4): 273–288. doi:10.1016/0021-9045(78)90013-8.
  4. de Boor, C.; Pinkus, A. (1978). "Proof of the conjectures of Bernstein and Erdös concerning the optimal nodes for polynomial interpolation". Journal of Approximation Theory. 24 (4): 289–303. doi:10.1016/0021-9045(78)90014-X.
  5. Luttmann, F. W.; Rivlin, T. J. (1965). "बहुपद प्रक्षेप के सिद्धांत में कुछ संख्यात्मक प्रयोग". IBM J. Res. Dev. 9 (3): 187–191. doi:10.1147/rd.93.0187.
  6. 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).
  7. Brutman, L. (1978). "बहुपद अंतर्वेशन के लिए लेबेस्ग फ़ंक्शन पर". SIAM J. Numer. Anal. 15 (4): 694–704. Bibcode:1978SJNA...15..694B. doi:10.1137/0715046.
  8. Günttner, R. (1980). "लेब्सेग स्थिरांक का मूल्यांकन". SIAM J. Numer. Anal. 17 (4): 512–520. Bibcode:1980SJNA...17..512G. doi:10.1137/0717043.
  9. David G. Luenberger: Introduction to Linear and Nonlinear Programming, Addison-Wesley Publishing Company 1973.
  10. Egidi, Nadaniela; Fatone, Lorella; Misici, Luciano (2020), Sergeyev, Yaroslav D.; Kvasov, Dmitri E. (eds.), "A New Remez-Type Algorithm for Best Polynomial Approximation", Numerical Computations: Theory and Algorithms (in English), Cham: Springer International Publishing, vol. 11973, pp. 56–69, doi:10.1007/978-3-030-39081-5_7, ISBN 978-3-030-39080-8, S2CID 211159177, retrieved 2022-03-19
  11. 11.0 11.1 Temes, G.C.; Barcilon, V.; Marshall, F.C. (1973). "The optimization of bandlimited systems". Proceedings of the IEEE. 61 (2): 196–234. doi:10.1109/PROC.1973.9004. ISSN 0018-9219.
  12. Dunham, Charles B. (1975). "तर्कसंगत चेबीशेव सन्निकटन के लिए फ्रेजर-हार्ट एल्गोरिथ्म का अभिसरण". Mathematics of Computation (in English). 29 (132): 1078–1082. doi:10.1090/S0025-5718-1975-0388732-9. ISSN 0025-5718.


बाहरी संबंध