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

From Vigyanwiki
No edit summary
No edit summary
Line 5: Line 5:


==प्रक्रिया==
==प्रक्रिया==
रेमेज़ एल्गोरिदम फ़ंक्शन से शुरू होता है <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> सन्निकटन अंतराल में, सामान्यतः चेबीशेव बहुपद का चरम रैखिक रूप से अंतराल पर मैप किया जाता है। चरण हैं:


* समीकरणों की रैखिक प्रणाली को हल करें
* समीकरणों की रैखिक प्रणाली को हल करें
Line 27: Line 27:


:<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>''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 |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>
Line 70: Line 70:
दिए गए n+2 क्रमित नोड्स पर त्रुटि सकारात्मक और नकारात्मक है क्योंकि
दिए गए n+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 वाले बहुपद के लिए असंभव है।
<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 वाले बहुपद के लिए असंभव है।
Line 95: Line 95:


==वेरिएंट==
==वेरिएंट==
एल्गोरिदम के कुछ संशोधन साहित्य में मौजूद हैं।<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> इसमे सम्मिलित है:


* से अधिक नमूना बिंदु को निकटतम अधिकतम निरपेक्ष अंतर वाले स्थानों से बदलना।
* से अधिक नमूना बिंदु को निकटतम अधिकतम निरपेक्ष अंतर वाले स्थानों से बदलना।

Revision as of 19:31, 7 August 2023

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

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

प्रक्रिया

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

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

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

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

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

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

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

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

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

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

के लिए

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

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

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

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

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

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

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

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

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

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

बहुपद के बीच इसका i-th शून्य है और , और इस प्रकार बीच में कोई और शून्य नहीं है और : और ही चिन्ह है .

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

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

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

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

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

दिए गए n+2 क्रमित नोड्स पर त्रुटि सकारात्मक और नकारात्मक है क्योंकि

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

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

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

'चरण 2' से अंकन बदल जाता है

को .

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

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

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

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

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

चरण 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.


बाहरी संबंध