निश्चित-बिंदु गणना: Difference between revisions

Revision as of 01:34, 22 July 2023

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

परिभाषाएँ

तीन निश्चित बिंदुओं के साथ एक उदाहरण प्रकार्य का ग्राफ़

इकाई अंतराल को निरूपित किया जाता है $E:=[0,1]$ , और इकाई d-आयामी घन को E^d द्वारा निरूपित किया जाता है। एक सतत फलन f को E^d (E^d से स्वयं तक) पर परिभाषित किया गया है। प्रायः, यह माना जाता है कि f न केवल सतत है, बल्कि लिप्सचिट्ज़ सतत भी है, अर्थात, कुछ स्थिरांक L के लिए, $|f(x)-f(y)|\leq L\cdot |x-y|$ E^d में सभी x,y के लिए।

F का एक 'नियत बिंदु' E^d में एक बिंदु x है जैसे कि f(x) = x । ब्रौवर नियत-बिंदु प्रमेय के अनुसार, E^d से कोई भी सतत कार्य का अपने आप में एक नियत बिंदु होता है। लेकिन सामान्य कार्यों के लिए, एक नियत बिंदु की सटीक गणना करना असंभव है, क्योंकि यह एक मनमानी वास्तविक संख्या हो सकती है। नियत-बिंदु गणना एल्गोरिदम अनुमानित निश्चित बिंदुओं की खोज करते हैं। अनुमानित निश्चित बिंदु के लिए कई मानदंड हैं। कई सामान्य मानदंड हैं:^[2]

अवशिष्ट मानदंड: एक सन्निकटन पैरामीटर दिया गया है $\varepsilon >0$ , f का एक ε-अवशिष्ट निश्चित-बिंदु E^d में एक बिंदु x है जैसे कि $|f(x)-x|\leq \varepsilon$ , यहाँ कहाँ |.| अधिकतम मानदंड को दर्शाता है| अर्थात सभी d निर्देशांक में अंतर है $f(x)-x$ अधिक से अधिक $ε$ होना चाहिए |^[3]^: 4
पूर्ण मानदंड: एक सन्निकटन पैरामीटर दिया गया है $\delta >0$ , f का एक δ-पूर्ण नियत-बिंदु E^d में एक बिंदु x है जैसे कि $|x-x_{0}|\leq \delta$ , कहाँ $x_{0}$ f का कोई निश्चित-बिंदु है।
'सापेक्ष मानदंड': एक सन्निकटन पैरामीटर दिया गया है $\delta >0$ , f का एक δ-सापेक्ष नियत-बिंदु E^d में एक बिंदु x है जैसे कि $|x-x_{0}|/|x_{0}|\leq \delta$ , कहाँ $x_{0}$ f का कोई निश्चित-बिंदु है।

लिप्सचिट्ज़-सतत कार्यों के लिए, पूर्ण मानदंड अवशिष्ट मानदंड से अधिक मजबूत है: यदि f स्थिर L के साथ लिप्सचिट्ज़-सतत है, तो $|x-x_{0}|\leq \delta$ का तात्पर्य है $|f(x)-f(x_{0})|\leq L\cdot \delta$ | तब से $x_{0}$ f का एक नियत बिंदु है, इसका तात्पर्य है $|f(x)-x_{0}|\leq L\cdot \delta$ , इसलिए $|f(x)-x|\leq (1+L)\cdot \delta$ . इसलिए, एक δ-पूर्ण नियत-बिंदु भी एक $ε$ -अवशिष्ट नियत-बिंदु के साथ $\varepsilon =(1+L)\cdot \delta$ है|

नियत-बिंदु गणना एल्गोरिदम का सबसे बुनियादी चरण एक मान क्वेरी है: E^d में कोई भी x दिया गया है,^{[वाक्य खंड]}

प्रकार्य f 'मूल्यांकन' प्रश्नों के माध्यम से सुलभ है: किसी भी x के लिए, एल्गोरिदम f(x) का मूल्यांकन कर सकता है। किसी एल्गोरिदम की रन-टाइम जटिलता समान्यता आवश्यक मूल्यांकनों की संख्या द्वारा दी जाती है।

संविदात्मक कार्य

यदि L < 1 स्थिरांक L के साथ एक लिप्सचिट्ज़-सतत प्रकार्य को 'संविदात्मक' कहा जाता है; यदि L ≤ 1 इसे 'कमजोर-संकुचन' कहा जाता है| ब्रौवर की शर्तों को संतुष्ट करने वाले प्रत्येक संविदात्मक कार्य का एक अद्वितीय नियत बिंदु होता है। इसके अतिरिक्त, संविदात्मक कार्यों के लिए नियत-बिंदु गणना सामान्य कार्यों की तुलना में आसान है।

प्रकार्य पुनरावृत्ति का उपयोग करके एक नियत बिंदु की गणना करना

नियत-बिंदु गणना के लिए पहला एल्गोरिदम बानाच का नियत-बिंदु पुनरावृत्ति एल्गोरिदम था। बानाच का नियत-बिंदु प्रमेय का तात्पर्य है कि, जब नियत-बिंदु पुनरावृत्ति को संकुचन मानचित्रण पर लागू किया जाता है, तो t पुनरावृत्तियों के बाद त्रुटि है $O(L^{t})$ | इसलिए, δ-सापेक्ष नियत-बिंदु के लिए आवश्यक मूल्यांकनों की संख्या लगभग $\log _{L}(\delta )=\log(\delta )/\log(L)=\log(1/\delta )/\log(1/L)$ है| सिकोरस्की और वोज्नियाकोव्स्की^[4] ने दिखाया गया कि जब आयाम बड़ा होता है तो बानाच का एल्गोरिदम इष्टतम होता है। विशेष रूप से, जब $d\geq \log(1/\delta )/\log(1/L)$ , δ-सापेक्ष नियत-बिंदु के लिए किसी भी एल्गोरिदम के आवश्यक मूल्यांकन की संख्या पुनरावृत्ति एल्गोरिदम द्वारा आवश्यक मूल्यांकन की संख्या 50% से अधिक है। ध्यान दें कि जब L 1 के करीब पहुंचता है, तो मूल्यांकन की संख्या अनंत तक पहुंच जाती है। वास्तव में, कोई भी परिमित एल्गोरिथ्म L=1 वाले सभी कार्यों के लिए δ-पूर्ण नियत बिंदु की गणना नहीं कर सकता है।^[5]

जब L <1 और d = 1, इष्टतम एल्गोरिदम सिकोरस्की और वोज्नियाकोव्स्की का 'नियत बिन्दु आवरण' (FPE) एल्गोरिदम है।^[4] इसका उपयोग करके δ-सापेक्ष नियत बिंदु पाया जाता है $O(\log(1/\delta )+\log \log(1/(1-L)))$ क्वेरीज़(प्रश्न), और एक δ-पूर्ण नियत बिंदु $O(\log(1/\delta ))$ का उपयोग करना | यह नियत-बिंदु पुनरावृत्ति एल्गोरिथ्म से बहुत तेज़ है।^[6]

जब d>1 लेकिन बहुत बड़ा नहीं है, और L ≤ 1, इष्टतम एल्गोरिथ्म आंतरिक-दीर्घवृत्ताभ एल्गोरिथ्म (दीर्घवृत्ताभ विधि पर आधारित) है।^[7] यह पाता है कि $ε$ -अवशिष्ट नियत-बिंदु $O(d\cdot \log(1/\varepsilon ))$ मूल्यांकन का उपयोग किया जा रहा है | जब L<1, यह एक δ-निरपेक्ष नियत बिंदु $O(d\cdot [\log(1/\delta )+\log(1/(1-L))])$ मूल्यांकन का उपयोग करके पाता है|

शेलमैन और सिकोरस्की^[8] ने केवल L ≤ 1 के साथ दो-आयामी प्रकार्य के ε-अवशिष्ट निश्चित-बिंदु की गणना के लिए BEFix (बाइसेक्शन लिफाफा फिक्स्ड-पॉइंट) $2\lceil \log _{2}(1/\varepsilon )\rceil +1$ नामक एक एल्गोरिदम प्रस्तुत किया, वे बाद में^[9] समान सबसे खराब स्थिति की गारंटी लेकिन बेहतर अनुभवजन्य प्रदर्शन के साथ, BEDFix (बाइसेक्शन लिफाफा डीप-कट फिक्स्ड-पॉइंट) नामक एक सुधार प्रस्तुत किया। जब L<1, BEDFix का उपयोग करके δ-पूर्ण नियत-बिंदु $O(\log(1/\varepsilon )+\log(1/(1-L)))$ की गणना भी की जा सकती है|

शेलमैन और सिकोरस्की^[2] ने L ≤ 1 के साथ एक d-आयामी प्रकार्य के ε- अवशिष्ट नियत-बिंदुकी गणना के लिए PFix नामक एक एल्गोरिदम $O(\log ^{d}(1/\varepsilon ))$ प्रस्तुत किया, जिसका उपयोग किया गया | जब L <1, PFix को निष्पादित किया जा सकता है $\varepsilon =(1-L)\cdot \delta$ , और उस स्थिति में, यह उपयोग करके δ-पूर्ण नियत-बिंदु $O(\log ^{d}(1/[(1-L)\delta ]))$ की गणना करता है | जब L 1 के करीब होता है तो यह पुनरावृत्ति एल्गोरिथ्म से अधिक कुशल होता है। एल्गोरिदम पुनरावर्ती है: यह (d-1)-आयामी कार्यों पर पुनरावर्ती कॉल द्वारा एक d-आयामी प्रकार्य को संभालता है।

विभिन्न कार्यों के लिए एल्गोरिदम

जब प्रकार्य f अवकलनीय होता है, और एल्गोरिदम इसके व्युत्पन्न (केवल f ही नहीं) का मूल्यांकन कर सकता है, तो अनुकूलन में न्यूटन की विधि का उपयोग किया जा सकता है और यह बहुत तेज़ है।^[10]^[11]

सामान्य कार्य

लिप्सचिट्ज़ स्थिरांक L > 1 वाले कार्यों के लिए, एक नियत-बिंदु की गणना करना बहुत कठिन है।

एक आयाम

1-आयामी प्रकार्य (d = 1) के लिए, एक δ-पूर्ण नियत-बिंदु का उपयोग करके पाया जा सकता है $O(\log(1/\delta ))$ द्विभाजन विधि का उपयोग करते हुए प्रश्न: अंतराल से प्रारंभ करें $E:=[0,1]$ ; प्रत्येक पुनरावृत्ति पर, मान लीजिए कि x वर्तमान अंतराल का केंद्र है, और f(x) की गणना करता है; यदि f(x) > x तो x के दाईं ओर उप-अंतराल पर पुनरावृत्ति करें; अन्यथा, x के बाईं ओर के अंतराल पर पुनरावृत्ति करें। ध्यान दें कि वर्तमान अंतराल में हमेशा एक नियत बिंदु होता है, इसलिए बाद में $O(\log(1/\delta ))$ प्रश्न, शेष अंतराल में कोई भी बिंदु f का δ-पूर्ण नियत-बिंदु है। सेटिंग $\delta :=\varepsilon /(L+1)$ , जहां L लिप्सचिट्ज़ स्थिरांक है, एक देता है $ε$ -अवशिष्ट नियत-बिंदु, का उपयोग करना $O(\log(L/\varepsilon )=\log(L)+\log(1/\varepsilon ))$ प्रश्न.^[3]

दो या दो से अधिक आयाम

दो या दो से अधिक आयामों वाले कार्यों के लिए, समस्या अधिक चुनौतीपूर्ण है। शेलमैन और सिकोरस्की^[2]साबित हुआ कि, किसी भी पूर्णांक d ≥ 2 और L > 1 के लिए, d-आयामी L-लिप्सचिट्ज़ फ़ंक्शंस का δ-पूर्ण नियत-बिंदु खोजने के लिए अनंत-कई मूल्यांकन की आवश्यकता हो सकती है। प्रमाण विचार इस प्रकार है. किसी भी पूर्णांक टी> 1 के लिए, और मूल्यांकन प्रश्नों (संभवतः अनुकूली) के टी के किसी भी अनुक्रम के लिए, कोई दो कार्यों का निर्माण कर सकता है जो सतत L के साथ लिप्सचिट्ज़-सतत हैं, और इन सभी प्रश्नों का एक ही उत्तर दे सकते हैं, लेकिन उनमें से एक के पास है एक अद्वितीय नियत-बिंदु (x, 0) पर है और दूसरे का एक अद्वितीय नियत-बिंदु (x, 1) पर है। टी मूल्यांकन का उपयोग करने वाला कोई भी एल्गोरिदम इन कार्यों के बीच अंतर नहीं कर सकता है, इसलिए δ-पूर्ण नियत-बिंदु नहीं ढूंढ सकता है। यह किसी भी परिमित पूर्णांक T के लिए सत्य है।

इसे खोजने के लिए प्रकार्य मूल्यांकन पर आधारित कई एल्गोरिदम विकसित किए गए हैं $ε$ -अवशिष्ट नियत-बिंदु

किसी सामान्य प्रकार्य के एक नियत बिंदु का अनुमान लगाने वाला पहला एल्गोरिदम 1967 में हर्बर्ट स्कार्फ द्वारा विकसित किया गया था।^[12]^[13] स्कार्फ का एल्गोरिदम एक ढूंढता है $ε$ -स्पर्नर के लेम्मा के समान एक निर्माण में, एक पूर्ण-लेबल वाले आदिम सेट को ढूंढकर अवशिष्ट नियत-बिंदु।
हेरोल्ड डब्ल्यू. कुह्न द्वारा एक बाद का एल्गोरिदम^[14] आदिम सेटों के बजाय सरल और सरल विभाजन का उपयोग किया गया।
सरल दृष्टिकोण को और विकसित करते हुए, ओरिन हैरिसन मेरिल^[15] पुनरारंभ एल्गोरिथ्म प्रस्तुत किया।
बी कर्टिस ईव्स^[16] होमोटॉपी एल्गोरिदम प्रस्तुत किया। एल्गोरिथ्म एक एफ़िन प्रकार्य से शुरू करके काम करता है जो f का अनुमान लगाता है, और नियत बिंदु का पालन करते हुए इसे f की ओर विकृत करता है। माइकल टॉड की एक किताब^[1]1976 तक विकसित विभिन्न एल्गोरिदम का सर्वेक्षण।
डेविड गेल^[17] दिखाया गया है कि एन-डायमेंशनल प्रकार्य (यूनिट d-डायमेंशनल क्यूब पर) के एक नियत बिंदु की गणना करना यह तय करने के बराबर है कि हेक्स (बोर्ड गेम) के d-डायमेंशनल गेम में विजेता कौन है (d खिलाड़ियों वाला एक गेम, प्रत्येक) जिसे d-घन के दो विपरीत फलकों को जोड़ने की आवश्यकता है)। वांछित सटीकता को देखते हुएε
- केडी आकार का एक हेक्स बोर्ड बनाएं, जहां $k>1/\varepsilon$ . प्रत्येक शीर्ष z इकाई n-घन में एक बिंदु z/k से मेल खाता है।
- अंतर की गणना करें f(z/k) - z/k; ध्यान दें कि अंतर एक एन-वेक्टर है।
- शीर्ष z को 1, ..., d में एक लेबल द्वारा लेबल करें, जो अंतर वेक्टर में सबसे बड़े समन्वय को दर्शाता है।
- परिणामी लेबलिंग d खिलाड़ियों के बीच d-आयामी हेक्स गेम के संभावित खेल से मेल खाती है। इस गेम में एक विजेता होना चाहिए, और गेल जीत का रास्ता बनाने के लिए एक एल्गोरिदम प्रस्तुत करता है।
- जीत की राह में, एक बिंदु ऐसा होना चाहिए जिसमें एफ_i(z/k) - z/k सकारात्मक है, और एक आसन्न बिंदु जिसमें f_i(z/k) - z/k नकारात्मक है। इसका मतलब यह है कि इन दोनों बिंदुओं के बीच f का एक नियत बिंदु है।

सबसे खराब स्थिति में, इन सभी एल्गोरिदम द्वारा आवश्यक प्रकार्य मूल्यांकन की संख्या सटीकता के द्विआधारी प्रतिनिधित्व में घातीय है, अर्थात $\Omega (1/\varepsilon )$ .

क्वेरी जटिलता

हिर्श, क्रिस्टोस पापादिमित्रियोउ और वावसिस ने यह साबित किया^[3] प्रकार्य मूल्यांकन के आधार पर कोई भी एल्गोरिदम, जो एक पाता है $ε$ -f का अवशिष्ट नियत-बिंदु, आवश्यक है $\Omega (L'/\varepsilon )$ प्रकार्य मूल्यांकन, जहां $L'$ प्रकार्य का लिप्सचिट्ज़ स्थिरांक है $f(x)-x$ (ध्यान दें कि $L-1\leq L'\leq L+1$ ). ज्यादा ठीक:

2-आयामी प्रकार्य (d=2) के लिए, वे एक टाइट बाउंड साबित होते हैं $\Theta (L'/\varepsilon )$ .
किसी भी d ≥ 3 के लिए, an ज्ञात करना $ε$ -d-आयामी प्रकार्य के अवशिष्ट नियत-बिंदु की आवश्यकता होती है $\Omega ((L'/\varepsilon )^{d-2})$ प्रश्न और $O((L'/\varepsilon )^{d})$ प्रश्न.

बाद वाला परिणाम घातांक में एक अंतर छोड़ देता है। चेन और डेंग^[18]अंतर को बंद कर दिया. उन्होंने यह साबित कर दिया कि, किसी भी d ≥ 2 और के लिए $1/\varepsilon >4d$ और $L'/\varepsilon >192d^{3}$ , कंप्यूटिंग के लिए आवश्यक प्रश्नों की संख्या $ε$ -अवशिष्ट नियत-बिंदु में है $\Theta ((L'/\varepsilon )^{d-1})$ .

असतत नियत-बिंदु गणना

असतत प्रकार्य के उपसमुच्चय पर परिभाषित एक प्रकार्य है $\mathbb {Z} ^{d}$ (d-आयामी पूर्णांक ग्रिड)। कई अलग-अलग नियत-बिंदु प्रमेय हैं, जो उन स्थितियों को बताते हैं जिनके तहत एक अलग प्रकार्य का एक नियत बिंदु होता है। उदाहरण के लिए, 'आईमुरा-मुरोता-तमुरा प्रमेय' बताता है कि (विशेष रूप से) यदि f एक आयत उपसमुच्चय से एक प्रकार्य है $\mathbb {Z} ^{d}$ स्वयं के लिए, और f हाइपरक्यूबिक दिशा-संरक्षण प्रकार्य है|दिशा-संरक्षण, तो f का एक नियत बिंदु है।

मान लीजिए f पूर्णांक घन से एक दिशा-संरक्षण प्रकार्य है $\{1,\dots ,n\}^{d}$ खुद को। चेन और डेंग^[18]साबित करें कि, किसी भी d ≥ 2 और n > 48d के लिए, ऐसे नियत बिंदु की गणना करना आवश्यक है $\Theta (n^{d-1})$ कार्य मूल्यांकन.

चेन और डेंग^[19] एक अलग असतत-नियत-बिंदु समस्या को परिभाषित करें, जिसे वे 2D-BROUWER कहते हैं। यह एक असतत फलन f पर विचार करता है $\{0,\dots ,n\}^{2}$ जैसे कि, ग्रिड पर प्रत्येक x के लिए, f(x) - x या तो (0, 1) या (1, 0) या (-1, -1) है। लक्ष्य ग्रिड में एक वर्ग ढूंढना है, जिसमें सभी तीन लेबल होते हैं। प्रकार्य f को वर्ग को चित्रित(मानचित्र) करना होगा $\{0,\dots ,n\}^{2}$ स्वयं के लिए, इसलिए इसे रेखाओं x = 0 और y = 0 को या तो (0, 1) या (1, 0) पर चित्रित(मानचित्र) करना होगा; रेखा x = n से या तो (-1, -1) या (0, 1); और रेखा y = n से या तो (-1, -1) या (1,0)। समस्या को '2D-SPERNER' तक कम किया जा सकता है (स्पर्नर के लेम्मा की शर्तों को पूरा करने वाले त्रिभुज में एक पूर्ण-लेबल वाले त्रिकोण की गणना करना), और इसलिए यह PPAD-पूर्ण है। इसका तात्पर्य यह है कि अनुमानित नियत-बिंदु की गणना बहुत सरल कार्यों के लिए भी पीपीएडी-पूर्ण है।

नियत-बिंदु गणना और रूट-फाइंडिंग एल्गोरिदम के बीच संबंध

E से एक प्रकार्य g दिया गया है^d से R तक, g का 'मूल' E में एक बिंदु x है^d ऐसा कि g(x)=0. एक ' $ε$ -g का मूल E में एक बिंदु x है^घऐसे कि $g(x)\leq \varepsilon$ .

फिक्स्ड-पॉइंट गणना रूट-फाइंडिंग का एक विशेष मामला है: ई पर एक प्रकार्य f दिया गया है^घ, परिभाषित करें $g(x):=|f(x)-x|$ . स्पष्ट रूप से, x, f का एक नियत-बिंदु है यदि और केवल यदि x, g का मूल है, और x एक है $ε$ -f का अवशिष्ट नियत-बिंदु यदि और केवल यदि x एक है $ε$ -जी की जड़. इसलिए, किसी भी जड़-खोज एल्गोरिदम (एक एल्गोरिदम जो किसी प्रकार्य के अनुमानित रूट की गणना करता है) का उपयोग अनुमानित नियत-बिंदु खोजने के लिए किया जा सकता है।

इसके विपरीत सत्य नहीं है: किसी सामान्य प्रकार्य का अनुमानित मूल ढूँढ़ना किसी अनुमानित नियत बिंदु को ढूँढ़ने से अधिक कठिन हो सकता है। विशेष रूप से, सिकोरस्की^[20] यह साबित कर दिया कि एक खोज $ε$ -रूट की आवश्यकता है $\Omega (1/\varepsilon ^{d})$ कार्य मूल्यांकन. यह एक-आयामी प्रकार्य के लिए भी एक घातीय निचली सीमा देता है (इसके विपरीत, एक $ε$ -एक-आयामी प्रकार्य का अवशिष्ट नियत-बिंदु का उपयोग करके पाया जा सकता है $O(\log(1/\varepsilon ))$ द्विभाजन विधि का उपयोग कर प्रश्न)। यहाँ एक प्रमाण रेखाचित्र है।^[3]^: 35 एक प्रकार्य g बनाएं जो इससे थोड़ा बड़ा हो $ε$ ई में हर जगह^dकुछ बिंदु x के आसपास कुछ छोटे घन को छोड़कर₀, कहां एक्स₀ जी की अद्वितीय जड़ है. यदि g स्थिरांक L के साथ सतत लिप्सचिट्ज़ है, तो x के चारों ओर घन₀ की एक साइड-लंबाई हो सकती है $\varepsilon /L$ . कोई भी एल्गोरिदम जो एक पाता है $ε$ -जी के मूल को घनों के एक सेट की जांच करनी चाहिए जो पूरे ई को कवर करता है^घ; ऐसे घनों की संख्या न्यूनतम है $(L/\varepsilon )^{d}$ .

हालाँकि, फ़ंक्शंस के ऐसे वर्ग हैं जिनके लिए अनुमानित मूल ढूंढना अनुमानित नियत बिंदु खोजने के बराबर है। एक उदाहरण^[18] कार्यों का वर्ग g इस प्रकार है $g(x)+x$ मानचित्र ई^dस्वयं के लिए (अर्थात: $g(x)+x$ ई में है^{ई में सभी एक्स के लिए डी}^घ). ऐसा इसलिए है, क्योंकि ऐसे प्रत्येक प्रकार्य के लिए, function $f(x):=g(x)+x$ ब्रौवर के नियत-बिंदु प्रमेय की शर्तों को संतुष्ट करता है। स्पष्ट रूप से, x, f का एक नियत-बिंदु है यदि और केवल यदि x, g का मूल है, और x एक है $ε$ -f का अवशिष्ट नियत-बिंदु यदि और केवल यदि x एक है $ε$ -जी की जड़. चेन और डेंग^[18]दिखाएँ कि इन समस्याओं के अलग-अलग रूप कम्प्यूटेशनल रूप से समतुल्य हैं: दोनों समस्याओं की आवश्यकता है $\Theta (n^{d-1})$ कार्य मूल्यांकन.

संचार जटिलता

रफ़गार्डन और वीनस्टीन^[21] अनुमानित नियत-बिंदु की गणना की संचार जटिलता का अध्ययन किया। उनके मॉडल में, दो एजेंट हैं: उनमें से एक प्रकार्य f जानता है और दूसरा प्रकार्य g जानता है। दोनों कार्य लिप्सचिट्ज़ सतत हैं और ब्रौवर की शर्तों को पूरा करते हैं। लक्ष्य समग्र प्रकार्य के अनुमानित नियत बिंदु की गणना करना है $g\circ f$ . वे दिखाते हैं कि नियतिवादी संचार जटिलता मौजूद है $\Omega (2^{d})$ .

संदर्भ

↑ ^1.0 ^1.1 निश्चित बिंदुओं और अनुप्रयोगों की गणना. Lecture Notes in Economics and Mathematical Systems. Vol. 124. 1976. doi:10.1007/978-3-642-50327-6. ISBN 978-3-540-07685-8.^{[page needed]}
↑ ^2.0 ^2.1 ^2.2 Shellman, Spencer; Sikorski, K. (December 2003). "अनंत-मानदंड निश्चित बिंदु समस्या के लिए एक पुनरावर्ती एल्गोरिदम". Journal of Complexity. 19 (6): 799–834. doi:10.1016/j.jco.2003.06.001.
↑ ^3.0 ^3.1 ^3.2 ^3.3 Hirsch, Michael D; Papadimitriou, Christos H; Vavasis, Stephen A (December 1989). "ब्रौवर फिक्स पॉइंट खोजने के लिए घातीय निचली सीमाएं". Journal of Complexity. 5 (4): 379–416. doi:10.1016/0885-064X(89)90017-4. S2CID 1727254.
↑ ^4.0 ^4.1 Sikorski, K; Woźniakowski, H (December 1987). "निश्चित बिंदुओं की जटिलता, I". Journal of Complexity. 3 (4): 388–405. doi:10.1016/0885-064X(87)90008-2.
↑ Sikorski, Krzysztof A. (2001). अरेखीय समीकरणों का इष्टतम समाधान. Oxford University Press. ISBN 978-0-19-510690-9.^{[page needed]}
↑ Sikorski, K. (1989). "Fast Algorithms for the Computation of Fixed Points". पहचान एवं नियंत्रण में मजबूती. pp. 49–58. doi:10.1007/978-1-4615-9552-6_4. ISBN 978-1-4615-9554-0.
↑ Huang, Z; Khachiyan, L; Sikorski, K (June 1999). "कमजोर संकुचन मैपिंग के अनुमानित निश्चित बिंदु". Journal of Complexity. 15 (2): 200–213. doi:10.1006/jcom.1999.0504.
↑ Shellman, Spencer; Sikorski, K. (June 2002). "निश्चित बिंदुओं के लिए एक द्वि-आयामी द्विभाजन लिफाफा एल्गोरिदम". Journal of Complexity. 18 (2): 641–659. doi:10.1006/jcom.2001.0625.
↑ Shellman, Spencer; Sikorski, K. (September 2003). "Algorithm 825: A deep-cut bisection envelope algorithm for fixed points". ACM Transactions on Mathematical Software. 29 (3): 309–325. doi:10.1145/838250.838255. S2CID 7786886.
↑ Kellogg, R. B.; Li, T. Y.; Yorke, J. (September 1976). "ब्रौवर फिक्स्ड-पॉइंट प्रमेय और कम्प्यूटेशनल परिणामों का एक रचनात्मक प्रमाण". SIAM Journal on Numerical Analysis. 13 (4): 473–483. doi:10.1137/0713041.
↑ Smale, Steve (July 1976). "मूल्य समायोजन और वैश्विक न्यूटन विधियों की एक अभिसरण प्रक्रिया". Journal of Mathematical Economics. 3 (2): 107–120. doi:10.1016/0304-4068(76)90019-7.
↑ Scarf, Herbert (September 1967). "सतत मानचित्रण के निश्चित बिंदुओं का अनुमान". SIAM Journal on Applied Mathematics. 15 (5): 1328–1343. doi:10.1137/0115116.
↑ H. Scarf found the first algorithmic proof: Voitsekhovskii, M.I. (2001) [1994], "Brouwer theorem", Encyclopedia of Mathematics, EMS Press, ISBN 1-4020-0609-8.
↑ Kuhn, Harold W. (1968). "निश्चित बिंदुओं का सरल अनुमान". Proceedings of the National Academy of Sciences of the United States of America. 61 (4): 1238–1242. doi:10.1073/pnas.61.4.1238. JSTOR 58762. PMC 225246. PMID 16591723.
↑ Merrill, Orin Harrison (1972). एक एल्गोरिदम के अनुप्रयोग और विस्तार जो मैपिंग सेट करने के लिए कुछ ऊपरी अर्ध-निरंतर बिंदु के निश्चित बिंदुओं की गणना करते हैं (Thesis). OCLC 570461463. NAID 10006142329.
↑ Eaves, B. Curtis (December 1972). "निश्चित बिंदुओं की गणना के लिए समरूपताएँ". Mathematical Programming. 3–3 (1): 1–22. doi:10.1007/BF01584975. S2CID 39504380.
↑ Gale, David (1979). "हेक्स और ब्रौवर फिक्स्ड-प्वाइंट प्रमेय का खेल". The American Mathematical Monthly. 86 (10): 818–827. doi:10.2307/2320146. JSTOR 2320146.
↑ ^18.0 ^18.1 ^18.2 ^18.3 Chen, Xi; Deng, Xiaotie (2005). "On algorithms for discrete and approximate brouwer fixed points". कंप्यूटिंग के सिद्धांत पर सैंतीसवीं वार्षिक एसीएम संगोष्ठी की कार्यवाही. pp. 323–330. doi:10.1145/1060590.1060638. ISBN 1581139608. S2CID 16942881.
↑ Chen, Xi; Deng, Xiaotie (October 2009). "On the complexity of 2D discrete fixed point problem". Theoretical Computer Science. 410 (44): 4448–4456. doi:10.1016/j.tcs.2009.07.052. S2CID 2831759.
↑ Sikorski, K. (June 1984). "लिप्सचिट्ज़ स्थिति को संतुष्ट करने वाले अरेखीय समीकरणों का इष्टतम समाधान". Numerische Mathematik. 43 (2): 225–240. doi:10.1007/BF01390124. S2CID 120937024.
↑ Roughgarden, Tim; Weinstein, Omri (2016). "On the Communication Complexity of Approximate Fixed Points". 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS). pp. 229–238. doi:10.1109/FOCS.2016.32. ISBN 978-1-5090-3933-3. S2CID 87553.

अग्रिम पठन

Yannakakis, Mihalis (May 2009). "Equilibria, fixed points, and complexity classes". Computer Science Review. 3 (2): 71–85. doi:10.1016/j.cosrev.2009.03.004.

[:1-1] 1.0 ^1.1 निश्चित बिंदुओं और अनुप्रयोगों की गणना. Lecture Notes in Economics and Mathematical Systems. Vol. 124. 1976. doi:10.1007/978-3-642-50327-6. ISBN 978-3-540-07685-8.^{[page needed]}

[:3-2] 2.0 ^2.1 ^2.2 Shellman, Spencer; Sikorski, K. (December 2003). "अनंत-मानदंड निश्चित बिंदु समस्या के लिए एक पुनरावर्ती एल्गोरिदम". Journal of Complexity. 19 (6): 799–834. doi:10.1016/j.jco.2003.06.001.

[:0-3] 3.0 ^3.1 ^3.2 ^3.3 Hirsch, Michael D; Papadimitriou, Christos H; Vavasis, Stephen A (December 1989). "ब्रौवर फिक्स पॉइंट खोजने के लिए घातीय निचली सीमाएं". Journal of Complexity. 5 (4): 379–416. doi:10.1016/0885-064X(89)90017-4. S2CID 1727254.

[:5-4] 4.0 ^4.1 Sikorski, K; Woźniakowski, H (December 1987). "निश्चित बिंदुओं की जटिलता, I". Journal of Complexity. 3 (4): 388–405. doi:10.1016/0885-064X(87)90008-2.

[:4-5] Sikorski, Krzysztof A. (2001). अरेखीय समीकरणों का इष्टतम समाधान. Oxford University Press. ISBN 978-0-19-510690-9.^{[page needed]}

[6] Sikorski, K. (1989). "Fast Algorithms for the Computation of Fixed Points". पहचान एवं नियंत्रण में मजबूती. pp. 49–58. doi:10.1007/978-1-4615-9552-6_4. ISBN 978-1-4615-9554-0.

[7] Huang, Z; Khachiyan, L; Sikorski, K (June 1999). "कमजोर संकुचन मैपिंग के अनुमानित निश्चित बिंदु". Journal of Complexity. 15 (2): 200–213. doi:10.1006/jcom.1999.0504.

[8] Shellman, Spencer; Sikorski, K. (June 2002). "निश्चित बिंदुओं के लिए एक द्वि-आयामी द्विभाजन लिफाफा एल्गोरिदम". Journal of Complexity. 18 (2): 641–659. doi:10.1006/jcom.2001.0625.

[9] Shellman, Spencer; Sikorski, K. (September 2003). "Algorithm 825: A deep-cut bisection envelope algorithm for fixed points". ACM Transactions on Mathematical Software. 29 (3): 309–325. doi:10.1145/838250.838255. S2CID 7786886.

[10] Kellogg, R. B.; Li, T. Y.; Yorke, J. (September 1976). "ब्रौवर फिक्स्ड-पॉइंट प्रमेय और कम्प्यूटेशनल परिणामों का एक रचनात्मक प्रमाण". SIAM Journal on Numerical Analysis. 13 (4): 473–483. doi:10.1137/0713041.

[11] Smale, Steve (July 1976). "मूल्य समायोजन और वैश्विक न्यूटन विधियों की एक अभिसरण प्रक्रिया". Journal of Mathematical Economics. 3 (2): 107–120. doi:10.1016/0304-4068(76)90019-7.

[12] Scarf, Herbert (September 1967). "सतत मानचित्रण के निश्चित बिंदुओं का अनुमान". SIAM Journal on Applied Mathematics. 15 (5): 1328–1343. doi:10.1137/0115116.

[13] H. Scarf found the first algorithmic proof: Voitsekhovskii, M.I. (2001) [1994], "Brouwer theorem", Encyclopedia of Mathematics, EMS Press, ISBN 1-4020-0609-8.

[14] Kuhn, Harold W. (1968). "निश्चित बिंदुओं का सरल अनुमान". Proceedings of the National Academy of Sciences of the United States of America. 61 (4): 1238–1242. doi:10.1073/pnas.61.4.1238. JSTOR 58762. PMC 225246. PMID 16591723.

[15] Merrill, Orin Harrison (1972). एक एल्गोरिदम के अनुप्रयोग और विस्तार जो मैपिंग सेट करने के लिए कुछ ऊपरी अर्ध-निरंतर बिंदु के निश्चित बिंदुओं की गणना करते हैं (Thesis). OCLC 570461463. NAID 10006142329.

[16] Eaves, B. Curtis (December 1972). "निश्चित बिंदुओं की गणना के लिए समरूपताएँ". Mathematical Programming. 3–3 (1): 1–22. doi:10.1007/BF01584975. S2CID 39504380.

[17] Gale, David (1979). "हेक्स और ब्रौवर फिक्स्ड-प्वाइंट प्रमेय का खेल". The American Mathematical Monthly. 86 (10): 818–827. doi:10.2307/2320146. JSTOR 2320146.

[:2-18] 18.0 ^18.1 ^18.2 ^18.3 Chen, Xi; Deng, Xiaotie (2005). "On algorithms for discrete and approximate brouwer fixed points". कंप्यूटिंग के सिद्धांत पर सैंतीसवीं वार्षिक एसीएम संगोष्ठी की कार्यवाही. pp. 323–330. doi:10.1145/1060590.1060638. ISBN 1581139608. S2CID 16942881.

[19] Chen, Xi; Deng, Xiaotie (October 2009). "On the complexity of 2D discrete fixed point problem". Theoretical Computer Science. 410 (44): 4448–4456. doi:10.1016/j.tcs.2009.07.052. S2CID 2831759.

[20] Sikorski, K. (June 1984). "लिप्सचिट्ज़ स्थिति को संतुष्ट करने वाले अरेखीय समीकरणों का इष्टतम समाधान". Numerische Mathematik. 43 (2): 225–240. doi:10.1007/BF01390124. S2CID 120937024.

[21] Roughgarden, Tim; Weinstein, Omri (2016). "On the Communication Complexity of Approximate Fixed Points". 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS). pp. 229–238. doi:10.1109/FOCS.2016.32. ISBN 978-1-5090-3933-3. S2CID 87553.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

@@ Line 18: / Line 18: @@
 == संविदात्मक कार्य ==
-यदि L < 1 स्थिरांक L के साथ एक लिप्सचिट्ज़-सतत प्रकार्य को 'संविदात्मक' कहा जाता है; यदि L ≤ 1 इसे 'कमजोर-संकुचन' कहा जाता है| ब्रौवर की शर्तों को संतुष्ट करने वाले प्रत्येक संविदात्मक कार्य का एक अद्वितीय नियत बिंदु होता है। इसके अलावा, संविदात्मक कार्यों के लिए नियत-बिंदु गणना सामान्य कार्यों की तुलना में आसान है।
+यदि L < 1 स्थिरांक L के साथ एक लिप्सचिट्ज़-सतत प्रकार्य को 'संविदात्मक' कहा जाता है; यदि L ≤ 1 इसे 'कमजोर-संकुचन' कहा जाता है| ब्रौवर की शर्तों को संतुष्ट करने वाले प्रत्येक संविदात्मक कार्य का एक अद्वितीय नियत बिंदु होता है। इसके अतिरिक्त, संविदात्मक कार्यों के लिए नियत-बिंदु गणना सामान्य कार्यों की तुलना में आसान है।
-  [[File:Fixed point anime.gif|alt=computing a fixed point using function iteration|thumb|प्रकार्य पुनरावृत्ति का उपयोग करके एक नियत बिंदु की गणना करना]]नियत-बिंदु गणना के लिए पहला एल्गोरिदम बानाच का [[निश्चित-बिंदु पुनरावृत्ति|नियत-बिंदु पुनरावृत्ति]] एल्गोरिदम था। बानाच नियत बिंदु प्रमेय|बानाच का नियत-बिंदु प्रमेय का तात्पर्य है कि, जब नियत-बिंदु पुनरावृत्ति को संकुचन मानचित्रण पर लागू किया जाता है, तो ''टी'' पुनरावृत्ति के बाद त्रुटि होती है <math>O(L^t)</math>. इसलिए, δ-सापेक्ष नियत-बिंदु के लिए आवश्यक मूल्यांकनों की संख्या लगभग है <math>\log_L(\delta) = \log(\delta)/\log(L) = \log(1/\delta)/\log(1/L) </math>. सिकोरस्की और वोज्नियाकोव्स्की<ref name=":5">{{cite journal |last1=Sikorski |first1=K |last2=Woźniakowski |first2=H |title=निश्चित बिंदुओं की जटिलता, I|journal=Journal of Complexity |date=December 1987 |volume=3 |issue=4 |pages=388–405 |doi=10.1016/0885-064X(87)90008-2 }}</ref> दिखाया गया कि जब आयाम बड़ा होता है तो बानाच का एल्गोरिदम इष्टतम होता है। विशेष रूप से, जब <math>d\geq  \log(1/\delta)/\log(1/L) </math>, δ-सापेक्ष नियत-बिंदु के लिए किसी भी एल्गोरिदम के आवश्यक मूल्यांकन की संख्या पुनरावृत्ति एल्गोरिदम द्वारा आवश्यक मूल्यांकन की संख्या 50% से अधिक है। ध्यान दें कि जब L 1 के करीब पहुंचता है, तो मूल्यांकन की संख्या अनंत तक पहुंच जाती है। वास्तव में, कोई भी परिमित एल्गोरिथ्म L=1 वाले सभी कार्यों के लिए δ-पूर्ण नियत बिंदु की गणना नहीं कर सकता है।<ref name=":4">{{cite book |last1=Sikorski |first1=Krzysztof A. |title=अरेखीय समीकरणों का इष्टतम समाधान|date=2001 |publisher=Oxford University Press |isbn=978-0-19-510690-9 }}{{page needed|date=April 2023}}</ref>
+  [[File:Fixed point anime.gif|alt=computing a fixed point using function iteration|thumb|प्रकार्य पुनरावृत्ति का उपयोग करके एक नियत बिंदु की गणना करना]]नियत-बिंदु गणना के लिए पहला एल्गोरिदम बानाच का [[निश्चित-बिंदु पुनरावृत्ति|नियत-बिंदु पुनरावृत्ति]] एल्गोरिदम था। बानाच का नियत-बिंदु प्रमेय का तात्पर्य है कि, जब नियत-बिंदु पुनरावृत्ति को संकुचन मानचित्रण पर लागू किया जाता है, तो t पुनरावृत्तियों के बाद त्रुटि है <math>O(L^t)</math>| इसलिए, δ-सापेक्ष नियत-बिंदु के लिए आवश्यक मूल्यांकनों की संख्या लगभग  <math>\log_L(\delta) = \log(\delta)/\log(L) = \log(1/\delta)/\log(1/L) </math> है| सिकोरस्की और वोज्नियाकोव्स्की<ref name=":5">{{cite journal |last1=Sikorski |first1=K |last2=Woźniakowski |first2=H |title=निश्चित बिंदुओं की जटिलता, I|journal=Journal of Complexity |date=December 1987 |volume=3 |issue=4 |pages=388–405 |doi=10.1016/0885-064X(87)90008-2 }}</ref> ने दिखाया गया कि जब आयाम बड़ा होता है तो बानाच का एल्गोरिदम इष्टतम होता है। विशेष रूप से, जब <math>d\geq  \log(1/\delta)/\log(1/L) </math>, δ-सापेक्ष नियत-बिंदु के लिए किसी भी एल्गोरिदम के आवश्यक मूल्यांकन की संख्या पुनरावृत्ति एल्गोरिदम द्वारा आवश्यक मूल्यांकन की संख्या 50% से अधिक है। ध्यान दें कि जब L 1 के करीब पहुंचता है, तो मूल्यांकन की संख्या अनंत तक पहुंच जाती है। वास्तव में, कोई भी परिमित एल्गोरिथ्म L=1 वाले सभी कार्यों के लिए δ-पूर्ण नियत बिंदु की गणना नहीं कर सकता है।<ref name=":4">{{cite book |last1=Sikorski |first1=Krzysztof A. |title=अरेखीय समीकरणों का इष्टतम समाधान|date=2001 |publisher=Oxford University Press |isbn=978-0-19-510690-9 }}{{page needed|date=April 2023}}</ref>
-जब L <1 और डी = 1, इष्टतम एल्गोरिदम सिकोरस्की और वोज्नियाकोव्स्की का 'फिक्स्ड प्वाइंट एनवेलप' (एफपीई) एल्गोरिदम है।<ref name=":5" />इसका उपयोग करके δ-सापेक्ष नियत बिंदु पाया जाता है <math>O(\log(1/\delta) + \log \log(1/(1-L))) </math> प्रश्न, और एक δ-पूर्ण नियत बिंदु का उपयोग करना <math>O(\log(1/\delta)) </math> प्रश्न. यह नियत-बिंदु पुनरावृत्ति एल्गोरिथ्म से बहुत तेज़ है।<ref>{{cite book |doi=10.1007/978-1-4615-9552-6_4 |chapter=Fast Algorithms for the Computation of Fixed Points |title=पहचान एवं नियंत्रण में मजबूती|year=1989 |last1=Sikorski |first1=K. |pages=49–58 |isbn=978-1-4615-9554-0 }}</ref>
+जब L <1 और d = 1, इष्टतम एल्गोरिदम सिकोरस्की और वोज्नियाकोव्स्की का 'नियत बिन्दु आवरण' (FPE) एल्गोरिदम है।<ref name=":5" /> इसका उपयोग करके δ-सापेक्ष नियत बिंदु पाया जाता है <math>O(\log(1/\delta) + \log \log(1/(1-L))) </math> क्वेरीज़(प्रश्न), और एक δ-पूर्ण नियत बिंदु <math>O(\log(1/\delta)) </math> का उपयोग करना | यह नियत-बिंदु पुनरावृत्ति एल्गोरिथ्म से बहुत तेज़ है।<ref>{{cite book |doi=10.1007/978-1-4615-9552-6_4 |chapter=Fast Algorithms for the Computation of Fixed Points |title=पहचान एवं नियंत्रण में मजबूती|year=1989 |last1=Sikorski |first1=K. |pages=49–58 |isbn=978-1-4615-9554-0 }}</ref>
-जब d>1 लेकिन बहुत बड़ा नहीं है, और L ≤ 1, इष्टतम एल्गोरिथ्म आंतरिक-दीर्घवृत्ताभ एल्गोरिथ्म ([[दीर्घवृत्ताभ विधि]] पर आधारित) है।<ref>{{cite journal |last1=Huang |first1=Z |last2=Khachiyan |first2=L |last3=Sikorski |first3=K |title=कमजोर संकुचन मैपिंग के अनुमानित निश्चित बिंदु|journal=Journal of Complexity |date=June 1999 |volume=15 |issue=2 |pages=200–213 |doi=10.1006/jcom.1999.0504 }}</ref> यह एक पाता है {{mvar|ε}}-अवशिष्ट नियत-बिंदु का उपयोग कर रहा है <math>O(d\cdot \log(1/\varepsilon)) </math> मूल्यांकन. जब L<1, यह एक δ-निरपेक्ष नियत बिंदु का उपयोग करके पाता है <math>O(d\cdot [\log(1/\delta) + \log(1/(1-L))]) </math> मूल्यांकन.
-शेलमैन और सिकोरस्की<ref>{{cite journal |last1=Shellman |first1=Spencer |last2=Sikorski |first2=K. |title=निश्चित बिंदुओं के लिए एक द्वि-आयामी द्विभाजन लिफाफा एल्गोरिदम|journal=Journal of Complexity |date=June 2002 |volume=18 |issue=2 |pages=641–659 |doi=10.1006/jcom.2001.0625 }}</ref> की गणना के लिए बीईफिक्स (बाइसेक्शन लिफाफा फिक्स्ड-पॉइंट) नामक एक एल्गोरिदम प्रस्तुत किया {{mvar|ε}}-केवल L ≤ 1 का उपयोग करते हुए, द्वि-आयामी प्रकार्य का अवशिष्ट नियत-बिंदु <math>2 \lceil\log_2(1/\varepsilon)\rceil+1</math> प्रश्न. वे बाद में<ref>{{cite journal |last1=Shellman |first1=Spencer |last2=Sikorski |first2=K. |title=Algorithm 825: A deep-cut bisection envelope algorithm for fixed points |journal=ACM Transactions on Mathematical Software |date=September 2003 |volume=29 |issue=3 |pages=309–325 |doi=10.1145/838250.838255 |s2cid=7786886 }}</ref> समान सबसे खराब स्थिति की गारंटी लेकिन बेहतर अनुभवजन्य प्रदर्शन के साथ, BEDFix (बाइसेक्शन लिफाफा डीप-कट फिक्स्ड-पॉइंट) नामक एक सुधार प्रस्तुत किया। जब ''L''<1, BEDFix का उपयोग करके δ-पूर्ण नियत-बिंदु की गणना भी की जा सकती है <math>O(\log(1/\varepsilon)+\log(1/(1-L)))</math> प्रश्न.
+जब d>1 लेकिन बहुत बड़ा नहीं है, और L ≤ 1, इष्टतम एल्गोरिथ्म आंतरिक-दीर्घवृत्ताभ एल्गोरिथ्म ([[दीर्घवृत्ताभ विधि]] पर आधारित) है।<ref>{{cite journal |last1=Huang |first1=Z |last2=Khachiyan |first2=L |last3=Sikorski |first3=K |title=कमजोर संकुचन मैपिंग के अनुमानित निश्चित बिंदु|journal=Journal of Complexity |date=June 1999 |volume=15 |issue=2 |pages=200–213 |doi=10.1006/jcom.1999.0504 }}</ref> यह पाता है कि {{mvar|ε}}-अवशिष्ट नियत-बिंदु <math>O(d\cdot \log(1/\varepsilon)) </math> मूल्यांकन का उपयोग किया जा रहा है | जब L<1, यह एक δ-निरपेक्ष नियत बिंदु <math>O(d\cdot [\log(1/\delta) + \log(1/(1-L))]) </math> मूल्यांकन का उपयोग करके पाता है|
-शेलमैन और सिकोरस्की<ref name=":3" />की गणना के लिए पीफिक्स नामक एक एल्गोरिदम प्रस्तुत किया {{mvar|ε}}-L ≤ 1 के साथ एक डी-आयामी प्रकार्य का अवशिष्ट नियत-बिंदु, का उपयोग करते हुए <math>O(\log^d(1/\varepsilon))</math> प्रश्न. जब L <1, पीफिक्स को निष्पादित किया जा सकता है <math>\varepsilon = (1-L)\cdot \delta</math>, और उस स्थिति में, यह उपयोग करके δ-पूर्ण नियत-बिंदु की गणना करता है <math>O(\log^d(1/[(1-L)\delta]))</math> प्रश्न. जब L 1 के करीब होता है तो यह पुनरावृत्ति एल्गोरिथ्म से अधिक कुशल होता है। एल्गोरिदम पुनरावर्ती है: यह (d-1)-आयामी कार्यों पर पुनरावर्ती कॉल द्वारा एक d-आयामी प्रकार्य को संभालता है।
+शेलमैन और सिकोरस्की<ref>{{cite journal |last1=Shellman |first1=Spencer |last2=Sikorski |first2=K. |title=निश्चित बिंदुओं के लिए एक द्वि-आयामी द्विभाजन लिफाफा एल्गोरिदम|journal=Journal of Complexity |date=June 2002 |volume=18 |issue=2 |pages=641–659 |doi=10.1006/jcom.2001.0625 }}</ref>  ने केवल L ≤ 1 के साथ दो-आयामी प्रकार्य के ε-अवशिष्ट निश्चित-बिंदु की गणना के लिए BEFix (बाइसेक्शन लिफाफा फिक्स्ड-पॉइंट) <math>2 \lceil\log_2(1/\varepsilon)\rceil+1</math> नामक एक एल्गोरिदम प्रस्तुत किया, वे बाद में<ref>{{cite journal |last1=Shellman |first1=Spencer |last2=Sikorski |first2=K. |title=Algorithm 825: A deep-cut bisection envelope algorithm for fixed points |journal=ACM Transactions on Mathematical Software |date=September 2003 |volume=29 |issue=3 |pages=309–325 |doi=10.1145/838250.838255 |s2cid=7786886 }}</ref> समान सबसे खराब स्थिति की गारंटी लेकिन बेहतर अनुभवजन्य प्रदर्शन के साथ, BEDFix (बाइसेक्शन लिफाफा डीप-कट फिक्स्ड-पॉइंट) नामक एक सुधार प्रस्तुत किया। जब ''L''<1, BEDFix का उपयोग करके δ-पूर्ण नियत-बिंदु <math>O(\log(1/\varepsilon)+\log(1/(1-L)))</math> की गणना भी की जा सकती है|
+शेलमैन और सिकोरस्की<ref name=":3" /> ने L ≤ 1 के साथ एक d-आयामी प्रकार्य के ε- अवशिष्ट नियत-बिंदुकी गणना के लिए PFix नामक एक एल्गोरिदम <math>O(\log^d(1/\varepsilon))</math> प्रस्तुत किया, जिसका उपयोग किया गया | जब L <1, PFix को निष्पादित किया जा सकता है <math>\varepsilon = (1-L)\cdot \delta</math>, और उस स्थिति में, यह उपयोग करके δ-पूर्ण नियत-बिंदु <math>O(\log^d(1/[(1-L)\delta]))</math> की गणना करता है | जब L 1 के करीब होता है तो यह पुनरावृत्ति एल्गोरिथ्म से अधिक कुशल होता है। एल्गोरिदम पुनरावर्ती है: यह (d-1)-आयामी कार्यों पर पुनरावर्ती कॉल द्वारा एक d-आयामी प्रकार्य को संभालता है।
 === विभिन्न कार्यों के लिए एल्गोरिदम ===
@@ Line 35: / Line 36: @@
 === एक आयाम ===
--आयामी प्रकार्य (डी = 1) के लिए, एक δ-पूर्ण नियत-बिंदु का उपयोग करके पाया जा सकता है <math>O(\log(1/\delta))</math> [[द्विभाजन विधि]] का उपयोग करते हुए प्रश्न: अंतराल से प्रारंभ करें <math>E := [0, 1]</math>; प्रत्येक पुनरावृत्ति पर, मान लीजिए कि x वर्तमान अंतराल का केंद्र है, और f(x) की गणना करता है; यदि f(x) > x तो x के दाईं ओर उप-अंतराल पर पुनरावृत्ति करें; अन्यथा, x के बाईं ओर के अंतराल पर पुनरावृत्ति करें। ध्यान दें कि वर्तमान अंतराल में हमेशा एक नियत बिंदु होता है, इसलिए बाद में <math>O(\log(1/\delta))</math> प्रश्न, शेष अंतराल में कोई भी बिंदु f का δ-पूर्ण नियत-बिंदु है। सेटिंग <math>\delta := \varepsilon/(L+1)</math>, जहां L लिप्सचिट्ज़ स्थिरांक है, एक देता है {{mvar|ε}}-अवशिष्ट नियत-बिंदु, का उपयोग करना <math>O(\log(L/\varepsilon) = \log(L) + \log(1/\varepsilon))</math> प्रश्न.<ref name=":0" />
+-आयामी प्रकार्य (d = 1) के लिए, एक δ-पूर्ण नियत-बिंदु का उपयोग करके पाया जा सकता है <math>O(\log(1/\delta))</math> [[द्विभाजन विधि]] का उपयोग करते हुए प्रश्न: अंतराल से प्रारंभ करें <math>E := [0, 1]</math>; प्रत्येक पुनरावृत्ति पर, मान लीजिए कि x वर्तमान अंतराल का केंद्र है, और f(x) की गणना करता है; यदि f(x) > x तो x के दाईं ओर उप-अंतराल पर पुनरावृत्ति करें; अन्यथा, x के बाईं ओर के अंतराल पर पुनरावृत्ति करें। ध्यान दें कि वर्तमान अंतराल में हमेशा एक नियत बिंदु होता है, इसलिए बाद में <math>O(\log(1/\delta))</math> प्रश्न, शेष अंतराल में कोई भी बिंदु f का δ-पूर्ण नियत-बिंदु है। सेटिंग <math>\delta := \varepsilon/(L+1)</math>, जहां L लिप्सचिट्ज़ स्थिरांक है, एक देता है {{mvar|ε}}-अवशिष्ट नियत-बिंदु, का उपयोग करना <math>O(\log(L/\varepsilon) = \log(L) + \log(1/\varepsilon))</math> प्रश्न.<ref name=":0" />
@@ Line 47: / Line 48: @@
 *सरल दृष्टिकोण को और विकसित करते हुए, ओरिन हैरिसन मेरिल<ref>{{cite thesis |last1=Merrill |first1=Orin Harrison |date=1972 |title=एक एल्गोरिदम के अनुप्रयोग और विस्तार जो मैपिंग सेट करने के लिए कुछ ऊपरी अर्ध-निरंतर बिंदु के निश्चित बिंदुओं की गणना करते हैं|id={{NAID|10006142329}} |oclc=570461463 |url=https://www.proquest.com/openview/9bd010ff744833cb3a23ef521046adcb/1 }}</ref> पुनरारंभ एल्गोरिथ्म प्रस्तुत किया।
 * बी कर्टिस ईव्स<ref>{{cite journal |last1=Eaves |first1=B. Curtis |title=निश्चित बिंदुओं की गणना के लिए समरूपताएँ|journal=Mathematical Programming |date=December 1972 |volume=3-3 |issue=1 |pages=1–22 |doi=10.1007/BF01584975 |s2cid=39504380 }}</ref> [[होमोटॉपी]] एल्गोरिदम प्रस्तुत किया। एल्गोरिथ्म एक एफ़िन प्रकार्य से शुरू करके काम करता है जो f का अनुमान लगाता है, और नियत बिंदु का पालन करते हुए इसे f की ओर विकृत करता है। माइकल टॉड की एक किताब<ref name=":1" />1976 तक विकसित विभिन्न एल्गोरिदम का सर्वेक्षण।
-*[[डेविड गेल]]<ref>{{cite journal |first1=David |last1=Gale |year=1979 |title=हेक्स और ब्रौवर फिक्स्ड-प्वाइंट प्रमेय का खेल|journal=The American Mathematical Monthly |volume=86 |issue=10 |pages=818–827 |doi=10.2307/2320146 |jstor=2320146 }}</ref> दिखाया गया है कि एन-डायमेंशनल प्रकार्य (यूनिट डी-डायमेंशनल क्यूब पर) के एक नियत बिंदु की गणना करना यह तय करने के बराबर है कि [[हेक्स (बोर्ड गेम)]] के डी-डायमेंशनल गेम में विजेता कौन है (डी खिलाड़ियों वाला एक गेम, प्रत्येक) जिसे d-घन के दो विपरीत फलकों को जोड़ने की आवश्यकता है)। वांछित सटीकता को देखते हुए{{mvar|ε}}
+*[[डेविड गेल]]<ref>{{cite journal |first1=David |last1=Gale |year=1979 |title=हेक्स और ब्रौवर फिक्स्ड-प्वाइंट प्रमेय का खेल|journal=The American Mathematical Monthly |volume=86 |issue=10 |pages=818–827 |doi=10.2307/2320146 |jstor=2320146 }}</ref> दिखाया गया है कि एन-डायमेंशनल प्रकार्य (यूनिट d-डायमेंशनल क्यूब पर) के एक नियत बिंदु की गणना करना यह तय करने के बराबर है कि [[हेक्स (बोर्ड गेम)]] के d-डायमेंशनल गेम में विजेता कौन है (d खिलाड़ियों वाला एक गेम, प्रत्येक) जिसे d-घन के दो विपरीत फलकों को जोड़ने की आवश्यकता है)। वांछित सटीकता को देखते हुए{{mvar|ε}}
 ** केडी आकार का एक हेक्स बोर्ड बनाएं, जहां <math>k > 1/\varepsilon</math>. प्रत्येक शीर्ष z इकाई n-घन में एक बिंदु z/k से मेल खाता है।
 ** अंतर की गणना करें f(z/k) - z/k; ध्यान दें कि अंतर एक एन-वेक्टर है।
 ** शीर्ष z को 1, ..., d में एक लेबल द्वारा लेबल करें, जो अंतर वेक्टर में सबसे बड़े समन्वय को दर्शाता है।
-** परिणामी लेबलिंग डी खिलाड़ियों के बीच डी-आयामी हेक्स गेम के संभावित खेल से मेल खाती है। इस गेम में एक विजेता होना चाहिए, और गेल जीत का रास्ता बनाने के लिए एक एल्गोरिदम प्रस्तुत करता है।
+** परिणामी लेबलिंग d खिलाड़ियों के बीच d-आयामी हेक्स गेम के संभावित खेल से मेल खाती है। इस गेम में एक विजेता होना चाहिए, और गेल जीत का रास्ता बनाने के लिए एक एल्गोरिदम प्रस्तुत करता है।
 ** जीत की राह में, एक बिंदु ऐसा होना चाहिए जिसमें एफ<sub>i</sub>(z/k) - z/k सकारात्मक है, और एक आसन्न बिंदु जिसमें f<sub>i</sub>(z/k) - z/k नकारात्मक है। इसका मतलब यह है कि इन दोनों बिंदुओं के बीच f का एक नियत बिंदु है।
 सबसे खराब स्थिति में, इन सभी एल्गोरिदम द्वारा आवश्यक प्रकार्य मूल्यांकन की संख्या सटीकता के द्विआधारी प्रतिनिधित्व में घातीय है, अर्थात <math>\Omega(1/\varepsilon)</math>.
@@ Line 59: / Line 60: @@
 * 2-आयामी प्रकार्य (d=2) के लिए, वे एक टाइट बाउंड साबित होते हैं <math>\Theta(L'/\varepsilon)</math>.
-* किसी भी d ≥ 3 के लिए, an ज्ञात करना {{mvar|ε}}-डी-आयामी प्रकार्य के अवशिष्ट नियत-बिंदु की आवश्यकता होती है <math>\Omega((L'/\varepsilon)^{d-2})</math> प्रश्न और  <math>O((L'/\varepsilon)^{d})</math> प्रश्न.
+* किसी भी d ≥ 3 के लिए, an ज्ञात करना {{mvar|ε}}-d-आयामी प्रकार्य के अवशिष्ट नियत-बिंदु की आवश्यकता होती है <math>\Omega((L'/\varepsilon)^{d-2})</math> प्रश्न और  <math>O((L'/\varepsilon)^{d})</math> प्रश्न.
 बाद वाला परिणाम घातांक में एक अंतर छोड़ देता है। चेन और डेंग<ref name=":2" />अंतर को बंद कर दिया. उन्होंने यह साबित कर दिया कि, किसी भी d ≥ 2 और के लिए <math>1/\varepsilon  > 4 d</math> और <math>L'/\varepsilon  > 192 d^3</math>, कंप्यूटिंग के लिए आवश्यक प्रश्नों की संख्या {{mvar|ε}}-अवशिष्ट नियत-बिंदु में है <math>\Theta((L'/\varepsilon)^{d-1})</math>.
 == असतत नियत-बिंदु गणना ==
-असतत प्रकार्य '' के उपसमुच्चय पर परिभाषित एक प्रकार्य है<math>\mathbb{Z}^d</math>(डी-आयामी पूर्णांक ग्रिड)। कई अलग-अलग नियत-बिंदु प्रमेय हैं, जो उन स्थितियों को बताते हैं जिनके तहत एक अलग प्रकार्य का एक नियत बिंदु होता है। उदाहरण के लिए, 'आईमुरा-मुरोता-तमुरा प्रमेय' बताता है कि (विशेष रूप से) यदि f एक आयत उपसमुच्चय से एक प्रकार्य है<math>\mathbb{Z}^d</math>स्वयं के लिए, और f हाइपरक्यूबिक दिशा-संरक्षण प्रकार्य है|दिशा-संरक्षण, तो f का एक नियत बिंदु है।''
+असतत प्रकार्य '' के उपसमुच्चय पर परिभाषित एक प्रकार्य है<math>\mathbb{Z}^d</math>(d-आयामी पूर्णांक ग्रिड)। कई अलग-अलग नियत-बिंदु प्रमेय हैं, जो उन स्थितियों को बताते हैं जिनके तहत एक अलग प्रकार्य का एक नियत बिंदु होता है। उदाहरण के लिए, 'आईमुरा-मुरोता-तमुरा प्रमेय' बताता है कि (विशेष रूप से) यदि f एक आयत उपसमुच्चय से एक प्रकार्य है<math>\mathbb{Z}^d</math>स्वयं के लिए, और f हाइपरक्यूबिक दिशा-संरक्षण प्रकार्य है|दिशा-संरक्षण, तो f का एक नियत बिंदु है।''
 मान लीजिए f पूर्णांक घन से एक दिशा-संरक्षण प्रकार्य है <math>\{1, \dots, n\}^d</math> खुद को। चेन और डेंग<ref name=":2" />साबित करें कि, किसी भी d ≥ 2 और n > 48d के लिए, ऐसे नियत बिंदु की गणना करना आवश्यक है  <math>\Theta(n^{d-1})</math> कार्य मूल्यांकन.

Anonymous

Search

निश्चित-बिंदु गणना: Difference between revisions

Namespaces

More

Page actions

Revision as of 01:34, 22 July 2023

Contents

परिभाषाएँ