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

Revision as of 00:42, 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 इसे 'कमजोर-संकुचन' कहा जाता है| ब्रौवर की शर्तों को संतुष्ट करने वाले प्रत्येक संविदात्मक कार्य का एक अद्वितीय नियत बिंदु होता है। इसके अलावा, संविदात्मक कार्यों के लिए नियत-बिंदु गणना सामान्य कार्यों की तुलना में आसान है।

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

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

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

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

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

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

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

एक आयाम

1-आयामी प्रकार्य (डी = 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-घन के दो विपरीत फलकों को जोड़ने की आवश्यकता है)। वांछित सटीकता को देखते हुएε
- केडी आकार का एक हेक्स बोर्ड बनाएं, जहां $k>1/\varepsilon$ . प्रत्येक शीर्ष z इकाई n-घन में एक बिंदु z/k से मेल खाता है।
- अंतर की गणना करें f(z/k) - z/k; ध्यान दें कि अंतर एक एन-वेक्टर है।
- शीर्ष z को 1, ..., 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 ज्ञात करना $ε$ -डी-आयामी प्रकार्य के अवशिष्ट नियत-बिंदु की आवश्यकता होती है $\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}$ (डी-आयामी पूर्णांक ग्रिड)। कई अलग-अलग नियत-बिंदु प्रमेय हैं, जो उन स्थितियों को बताते हैं जिनके तहत एक अलग प्रकार्य का एक नियत बिंदु होता है। उदाहरण के लिए, 'आईमुरा-मुरोता-तमुरा प्रमेय' बताता है कि (विशेष रूप से) यदि 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 1: / Line 1: @@
 {{Short description|Computing the fixed point of a function}}
-निश्चित-बिंदु गणना किसी दिए गए फ़ंक्शन के सटीक या अनुमानित [[निश्चित बिंदु (गणित)]] की गणना करने की प्रक्रिया को संदर्भित करती है।<ref name=":1">{{cite book |doi=10.1007/978-3-642-50327-6 |title=निश्चित बिंदुओं और अनुप्रयोगों की गणना|series=Lecture Notes in Economics and Mathematical Systems |year=1976 |volume=124 |isbn=978-3-540-07685-8 }}{{page needed|date=April 2023}}</ref> इसके सबसे सामान्य रूप में, हमें एक फ़ंक्शन f दिया गया है जो [[ब्रौवर निश्चित-बिंदु प्रमेय]] की स्थिति को संतुष्ट करता है, अर्थात: f निरंतर है और इकाई N-cube|d-cube को स्वयं मैप करता है। ब्रौवर निश्चित-बिंदु प्रमेय गारंटी देता है कि f का एक निश्चित बिंदु है, लेकिन प्रमाण रचनात्मक नहीं है। अनुमानित निश्चित बिंदु की गणना के लिए विभिन्न एल्गोरिदम तैयार किए गए हैं। ऐसे एल्गोरिदम का उपयोग अर्थशास्त्र में [[बाजार संतुलन]] की गणना के लिए, गेम थ्योरी में [[नैश संतुलन]] की गणना के लिए और गतिशील सिस्टम विश्लेषण में किया जाता है।
+नियत-बिंदु गणना किसी दिए गए प्रकार्य के सटीक या अनुमानित [[निश्चित बिंदु (गणित)|नियत बिंदु (गणित)]] की गणना करने की प्रक्रिया को संदर्भित करती है।<ref name=":1">{{cite book |doi=10.1007/978-3-642-50327-6 |title=निश्चित बिंदुओं और अनुप्रयोगों की गणना|series=Lecture Notes in Economics and Mathematical Systems |year=1976 |volume=124 |isbn=978-3-540-07685-8 }}{{page needed|date=April 2023}}</ref> इसके सबसे सामान्य रूप में, हमें एक प्रकार्य f दिया गया है जो [[ब्रौवर निश्चित-बिंदु प्रमेय|ब्रौवर नियत-बिंदु प्रमेय]] की स्थिति को संतुष्ट करता है, अर्थात: f सतत है और इकाई d-क्यूब को अपने आप में चित्रित(मानचित्र) करता है। ब्रौवर नियत-बिंदु प्रमेय गारंटी देता है कि f का एक नियत बिंदु है, लेकिन प्रमाण रचनात्मक नहीं है। अनुमानित नियत बिंदु की गणना के लिए विभिन्न एल्गोरिदम तैयार किए गए हैं। ऐसे एल्गोरिदम का उपयोग अर्थशास्त्र में [[बाजार संतुलन]] की गणना के लिए, गेम थ्योरी(खेल सिद्धांत) में [[नैश संतुलन]] की गणना के लिए और गतिशील प्रणाली विश्लेषण में उपयोग किया जाता है।
 == परिभाषाएँ ==
-[[File:Fixed point example.svg|alt=an example function with three fixed points|thumb|तीन निश्चित बिंदुओं वाले एक उदाहरण फ़ंक्शन का ग्राफ़]]इकाई अंतराल को निरूपित किया जाता है <math>E := [0, 1]</math>, और इकाई N-घन|d-आयामी घन को E द्वारा निरूपित किया जाता है<sup>घ</sup>. एक सतत फलन f को E पर परिभाषित किया गया है<sup>घ</sup> (ई से<sup>घ</sup>स्वयं को)। अक्सर, यह माना जाता है कि f न केवल निरंतर है, बल्कि [[लिप्सचिट्ज़ निरंतर]] भी है, अर्थात, कुछ स्थिरांक L के लिए,  <math>|f(x)-f(y)| \leq L\cdot |x-y|</math> ई में सभी एक्स, वाई के लिए<sup>घ</sup>.
+[[File:Fixed point example.svg|alt=an example function with three fixed points|thumb|तीन निश्चित बिंदुओं के साथ एक उदाहरण प्रकार्य का ग्राफ़]]इकाई अंतराल को निरूपित किया जाता है <math>E := [0, 1]</math>, और इकाई d-आयामी घन को ''E<sup>d</sup>'' द्वारा निरूपित किया जाता है। एक सतत फलन f को ''E<sup>d</sup>'' (''E<sup>d</sup>'' से स्वयं तक) पर परिभाषित किया गया है। प्रायः, यह माना जाता है कि f न केवल सतत है, बल्कि [[लिप्सचिट्ज़ निरंतर|लिप्सचिट्ज़ सतत]] भी है, अर्थात, कुछ स्थिरांक L के लिए,  <math>|f(x)-f(y)| \leq L\cdot |x-y|</math> ''E<sup>d</sup>'' में सभी x,y के लिए।
-F का एक 'निश्चित बिंदु' E में एक बिंदु x है<sup>d</sup> ऐसा कि f(x) = x. ब्रौवर निश्चित-बिंदु प्रमेय द्वारा, ई से कोई भी निरंतर कार्य<sup>d</sup> का अपने आप में एक निश्चित बिंदु होता है। लेकिन सामान्य कार्यों के लिए, एक निश्चित बिंदु की सटीक गणना करना असंभव है, क्योंकि यह एक मनमाना वास्तविक संख्या हो सकता है। निश्चित-बिंदु गणना एल्गोरिदम अनुमानित निश्चित बिंदुओं की तलाश करते हैं। अनुमानित निश्चित बिंदु के लिए कई मानदंड हैं। कई सामान्य मानदंड हैं:<ref name=":3">{{cite journal |last1=Shellman |first1=Spencer |last2=Sikorski |first2=K. |title=अनंत-मानदंड निश्चित बिंदु समस्या के लिए एक पुनरावर्ती एल्गोरिदम|journal=Journal of Complexity |date=December 2003 |volume=19 |issue=6 |pages=799–834 |doi=10.1016/j.jco.2003.06.001 }}</ref>
+F का एक 'नियत बिंदु' E<sup>d</sup> में एक बिंदु x है जैसे कि f(x) = x । ब्रौवर नियत-बिंदु प्रमेय के अनुसार, E<sup>d</sup> से कोई भी सतत कार्य का अपने आप में एक नियत बिंदु होता है। लेकिन सामान्य कार्यों के लिए, एक नियत बिंदु की सटीक गणना करना असंभव है, क्योंकि यह एक मनमानी वास्तविक संख्या हो सकती है। नियत-बिंदु गणना एल्गोरिदम अनुमानित निश्चित बिंदुओं की खोज करते हैं। अनुमानित निश्चित बिंदु के लिए कई मानदंड हैं। कई सामान्य मानदंड हैं:<ref name=":3">{{cite journal |last1=Shellman |first1=Spencer |last2=Sikorski |first2=K. |title=अनंत-मानदंड निश्चित बिंदु समस्या के लिए एक पुनरावर्ती एल्गोरिदम|journal=Journal of Complexity |date=December 2003 |volume=19 |issue=6 |pages=799–834 |doi=10.1016/j.jco.2003.06.001 }}</ref>
-* अवशिष्ट मानदंड: एक सन्निकटन पैरामीटर दिया गया है <math>\varepsilon>0</math> , एक{{mvar|ε}}-''f'' का अवशिष्ट निश्चित-बिंदु ''E'' में एक बिंदु ''x'' है<sup>घ</sup>ऐसे कि <math>|f(x)-x|\leq \varepsilon</math>, यहाँ कहाँ |.. अर्थात सभी d निर्देशांक में अंतर है <math>f(x)-x</math> अधिक से अधिक होना चाहिए {{mvar|ε}}.<ref name=":0" />{{Rp|page=4}}
+* अवशिष्ट मानदंड: एक सन्निकटन पैरामीटर दिया गया है <math>\varepsilon>0</math> , f का एक ε-अवशिष्ट निश्चित-बिंदु ''E<sup>d</sup>'' में एक बिंदु x है जैसे कि <math>|f(x)-x|\leq \varepsilon</math>, यहाँ कहाँ |.| अधिकतम मानदंड को दर्शाता है| अर्थात सभी d निर्देशांक में अंतर है <math>f(x)-x</math> अधिक से अधिक {{mvar|ε}} होना चाहिए |<ref name=":0" />{{Rp|page=4}}
-* पूर्ण मानदंड: एक सन्निकटन पैरामीटर दिया गया है <math>\delta>0</math>, ''f'' का एक δ-पूर्ण निश्चित-बिंदु ''E'' में एक बिंदु ''x'' है<sup>घ</sup>ऐसे कि <math>|x-x_0|\leq \delta</math>, कहाँ <math>x_0</math> f का कोई निश्चित बिंदु है।
+* पूर्ण मानदंड: एक सन्निकटन पैरामीटर दिया गया है <math>\delta>0</math>, ''f'' का एक δ-पूर्ण नियत-बिंदु ''E<sup>d</sup>'' में एक बिंदु ''x'' है जैसे कि <math>|x-x_0|\leq \delta</math>, कहाँ <math>x_0</math> f का कोई निश्चित-बिंदु है।
-* 'सापेक्ष मानदंड': एक सन्निकटन पैरामीटर दिया गया है <math>\delta>0</math>, ''f'' का एक δ-सापेक्ष निश्चित-बिंदु ''E'' में एक बिंदु ''x'' है<sup>घ</sup>ऐसे कि <math>|x-x_0|/|x_0|\leq \delta</math>, कहाँ <math>x_0</math> f का कोई निश्चित बिंदु है।
+* 'सापेक्ष मानदंड': एक सन्निकटन पैरामीटर दिया गया है <math>\delta>0</math>, ''f'' का एक δ-सापेक्ष नियत-बिंदु ''E<sup>d</sup>'' में एक बिंदु ''x'' है जैसे कि <math>|x-x_0|/|x_0|\leq \delta</math>, कहाँ <math>x_0</math> f का कोई निश्चित-बिंदु है।
-लिप्सचिट्ज़-निरंतर कार्यों के लिए, पूर्ण मानदंड अवशिष्ट मानदंड से अधिक मजबूत है: यदि एफ निरंतर एल के साथ लिप्सचिट्ज़-निरंतर है, तो <math>|x-x_0|\leq \delta</math> तात्पर्य <math>|f(x)-f(x_0)|\leq L\cdot \delta</math>. तब से <math>x_0</math> f का एक निश्चित बिंदु है, इसका तात्पर्य है <math>|f(x)-x_0|\leq L\cdot \delta</math>, इसलिए <math>|f(x)-x|\leq (1+L)\cdot \delta</math>. इसलिए, एक δ-पूर्ण निश्चित-बिंदु भी एक है {{mvar|ε}}-अवशिष्ट निश्चित-बिंदु के साथ <math>\varepsilon = (1+L)\cdot \delta</math>.
+लिप्सचिट्ज़-सतत कार्यों के लिए, पूर्ण मानदंड अवशिष्ट मानदंड से अधिक मजबूत है: यदि f स्थिर L के साथ लिप्सचिट्ज़-सतत है, तो <math>|x-x_0|\leq \delta</math> का तात्पर्य है <math>|f(x)-f(x_0)|\leq L\cdot \delta</math> | तब से <math>x_0</math> f का एक नियत बिंदु है, इसका तात्पर्य है <math>|f(x)-x_0|\leq L\cdot \delta</math>, इसलिए <math>|f(x)-x|\leq (1+L)\cdot \delta</math>. इसलिए, एक δ-पूर्ण नियत-बिंदु भी एक {{mvar|ε}}-अवशिष्ट नियत-बिंदु के साथ <math>\varepsilon = (1+L)\cdot \delta</math> है|
-निश्चित-बिंदु गणना एल्गोरिदम का सबसे बुनियादी चरण एक मान क्वेरी है: ''ई'' में कोई ''x'' दिया गया है<sup>घ</sup>, द{{Sentence fragment|date=April 2023}}
+नियत-बिंदु गणना एल्गोरिदम का सबसे बुनियादी चरण एक मान क्वेरी है: ''E<sup>d</sup>'' में कोई भी x दिया गया है,<sup>[वाक्य खंड]</sup>
-फ़ंक्शन f 'मूल्यांकन' प्रश्नों के माध्यम से पहुंच योग्य है: किसी भी x के लिए, एल्गोरिदम f(x) का मूल्यांकन कर सकता है। किसी एल्गोरिदम की रन-टाइम जटिलता आमतौर पर आवश्यक मूल्यांकनों की संख्या द्वारा दी जाती है।
+प्रकार्य f 'मूल्यांकन' प्रश्नों के माध्यम से सुलभ है: किसी भी x के लिए, एल्गोरिदम f(x) का मूल्यांकन कर सकता है। किसी एल्गोरिदम की रन-टाइम जटिलता समान्यता आवश्यक मूल्यांकनों की संख्या द्वारा दी जाती है।
 == संविदात्मक कार्य ==
-स्थिरांक L के साथ एक लिप्सचिट्ज़-निरंतर फ़ंक्शन को 'संकुचनात्मक' कहा जाता है यदि L < 1; इसे 'कमजोर-संकुचन' कहा जाता है यदि 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% से अधिक है। ध्यान दें कि जब एल 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|प्रकार्य पुनरावृत्ति का उपयोग करके एक नियत बिंदु की गणना करना]]नियत-बिंदु गणना के लिए पहला एल्गोरिदम बानाच का [[निश्चित-बिंदु पुनरावृत्ति|नियत-बिंदु पुनरावृत्ति]] एल्गोरिदम था। बानाच नियत बिंदु प्रमेय|बानाच का नियत-बिंदु प्रमेय का तात्पर्य है कि, जब नियत-बिंदु पुनरावृत्ति को संकुचन मानचित्रण पर लागू किया जाता है, तो ''टी'' पुनरावृत्ति के बाद त्रुटि होती है <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>
-जब एल <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 और डी = 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>
-जब 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> मूल्यांकन.
+जब 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> प्रश्न.
+शेलमैन और सिकोरस्की<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> प्रश्न.
-शेलमैन और सिकोरस्की<ref name=":3" />की गणना के लिए पीफिक्स नामक एक एल्गोरिदम प्रस्तुत किया {{mvar|ε}}-एल ≤ 1 के साथ एक डी-आयामी फ़ंक्शन का अवशिष्ट निश्चित-बिंदु, का उपयोग करते हुए <math>O(\log^d(1/\varepsilon))</math> प्रश्न. जब एल <1, पीफिक्स को निष्पादित किया जा सकता है <math>\varepsilon = (1-L)\cdot \delta</math>, और उस स्थिति में, यह उपयोग करके δ-पूर्ण निश्चित-बिंदु की गणना करता है <math>O(\log^d(1/[(1-L)\delta]))</math> प्रश्न. जब L 1 के करीब होता है तो यह पुनरावृत्ति एल्गोरिथ्म से अधिक कुशल होता है। एल्गोरिदम पुनरावर्ती है: यह (d-1)-आयामी कार्यों पर पुनरावर्ती कॉल द्वारा एक d-आयामी फ़ंक्शन को संभालता है।
+शेलमैन और सिकोरस्की<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-आयामी प्रकार्य को संभालता है।
 === विभिन्न कार्यों के लिए एल्गोरिदम ===
-जब फ़ंक्शन f अवकलनीय होता है, और एल्गोरिदम इसके व्युत्पन्न (केवल f ही नहीं) का मूल्यांकन कर सकता है, तो अनुकूलन में न्यूटन की विधि का उपयोग किया जा सकता है और यह बहुत तेज़ है।<ref>{{cite journal |last1=Kellogg |first1=R. B. |last2=Li |first2=T. Y. |last3=Yorke |first3=J. |title=ब्रौवर फिक्स्ड-पॉइंट प्रमेय और कम्प्यूटेशनल परिणामों का एक रचनात्मक प्रमाण|journal=SIAM Journal on Numerical Analysis |date=September 1976 |volume=13 |issue=4 |pages=473–483 |doi=10.1137/0713041 }}</ref><ref>{{cite journal |last1=Smale |first1=Steve |title=मूल्य समायोजन और वैश्विक न्यूटन विधियों की एक अभिसरण प्रक्रिया|journal=Journal of Mathematical Economics |date=July 1976 |volume=3 |issue=2 |pages=107–120 |doi=10.1016/0304-4068(76)90019-7 }}</ref>
+जब प्रकार्य f अवकलनीय होता है, और एल्गोरिदम इसके व्युत्पन्न (केवल f ही नहीं) का मूल्यांकन कर सकता है, तो अनुकूलन में न्यूटन की विधि का उपयोग किया जा सकता है और यह बहुत तेज़ है।<ref>{{cite journal |last1=Kellogg |first1=R. B. |last2=Li |first2=T. Y. |last3=Yorke |first3=J. |title=ब्रौवर फिक्स्ड-पॉइंट प्रमेय और कम्प्यूटेशनल परिणामों का एक रचनात्मक प्रमाण|journal=SIAM Journal on Numerical Analysis |date=September 1976 |volume=13 |issue=4 |pages=473–483 |doi=10.1137/0713041 }}</ref><ref>{{cite journal |last1=Smale |first1=Steve |title=मूल्य समायोजन और वैश्विक न्यूटन विधियों की एक अभिसरण प्रक्रिया|journal=Journal of Mathematical Economics |date=July 1976 |volume=3 |issue=2 |pages=107–120 |doi=10.1016/0304-4068(76)90019-7 }}</ref>
 == सामान्य कार्य ==
-लिप्सचिट्ज़ स्थिरांक L > 1 वाले कार्यों के लिए, एक निश्चित-बिंदु की गणना करना बहुत कठिन है।
+लिप्सचिट्ज़ स्थिरांक L > 1 वाले कार्यों के लिए, एक नियत-बिंदु की गणना करना बहुत कठिन है।
 === एक आयाम ===
--आयामी फ़ंक्शन (डी = 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" />
+-आयामी प्रकार्य (डी = 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" />
 === दो या दो से अधिक आयाम ===
-दो या दो से अधिक आयामों वाले कार्यों के लिए, समस्या अधिक चुनौतीपूर्ण है। शेलमैन और सिकोरस्की<ref name=":3" />साबित हुआ कि, किसी भी पूर्णांक d ≥ 2 और L > 1 के लिए, d-आयामी L-लिप्सचिट्ज़ फ़ंक्शंस का δ-पूर्ण निश्चित-बिंदु खोजने के लिए अनंत-कई मूल्यांकन की आवश्यकता हो सकती है। प्रमाण विचार इस प्रकार है. किसी भी पूर्णांक टी> 1 के लिए, और मूल्यांकन प्रश्नों (संभवतः अनुकूली) के टी के किसी भी अनुक्रम के लिए, कोई दो कार्यों का निर्माण कर सकता है जो निरंतर एल के साथ लिप्सचिट्ज़-निरंतर हैं, और इन सभी प्रश्नों का एक ही उत्तर दे सकते हैं, लेकिन उनमें से एक के पास है एक अद्वितीय निश्चित-बिंदु (x, 0) पर है और दूसरे का एक अद्वितीय निश्चित-बिंदु (x, 1) पर है। टी मूल्यांकन का उपयोग करने वाला कोई भी एल्गोरिदम इन कार्यों के बीच अंतर नहीं कर सकता है, इसलिए δ-पूर्ण निश्चित-बिंदु नहीं ढूंढ सकता है। यह किसी भी परिमित पूर्णांक T के लिए सत्य है।
+दो या दो से अधिक आयामों वाले कार्यों के लिए, समस्या अधिक चुनौतीपूर्ण है। शेलमैन और सिकोरस्की<ref name=":3" />साबित हुआ कि, किसी भी पूर्णांक d ≥ 2 और L > 1 के लिए, d-आयामी L-लिप्सचिट्ज़ फ़ंक्शंस का δ-पूर्ण नियत-बिंदु खोजने के लिए अनंत-कई मूल्यांकन की आवश्यकता हो सकती है। प्रमाण विचार इस प्रकार है. किसी भी पूर्णांक टी> 1 के लिए, और मूल्यांकन प्रश्नों (संभवतः अनुकूली) के टी के किसी भी अनुक्रम के लिए, कोई दो कार्यों का निर्माण कर सकता है जो सतत L के साथ लिप्सचिट्ज़-सतत हैं, और इन सभी प्रश्नों का एक ही उत्तर दे सकते हैं, लेकिन उनमें से एक के पास है एक अद्वितीय नियत-बिंदु (x, 0) पर है और दूसरे का एक अद्वितीय नियत-बिंदु (x, 1) पर है। टी मूल्यांकन का उपयोग करने वाला कोई भी एल्गोरिदम इन कार्यों के बीच अंतर नहीं कर सकता है, इसलिए δ-पूर्ण नियत-बिंदु नहीं ढूंढ सकता है। यह किसी भी परिमित पूर्णांक T के लिए सत्य है।
-इसे खोजने के लिए फ़ंक्शन मूल्यांकन पर आधारित कई एल्गोरिदम विकसित किए गए हैं {{mvar|ε}}-अवशिष्ट निश्चित-बिंदु
+इसे खोजने के लिए प्रकार्य मूल्यांकन पर आधारित कई एल्गोरिदम विकसित किए गए हैं {{mvar|ε}}-अवशिष्ट नियत-बिंदु
-* किसी सामान्य फ़ंक्शन के एक निश्चित बिंदु का अनुमान लगाने वाला पहला एल्गोरिदम 1967 में [[हर्बर्ट स्कार्फ]] द्वारा विकसित किया गया था।<ref>{{cite journal |last1=Scarf |first1=Herbert |title=सतत मानचित्रण के निश्चित बिंदुओं का अनुमान|journal=SIAM Journal on Applied Mathematics |date=September 1967 |volume=15 |issue=5 |pages=1328–1343 |doi=10.1137/0115116 }}</ref><ref>H. Scarf found the first algorithmic proof: {{SpringerEOM|title=Brouwer theorem|first=M.I.|last=Voitsekhovskii|isbn=1-4020-0609-8}}.</ref> स्कार्फ का एल्गोरिदम एक ढूंढता है {{mvar|ε}}-स्पर्नर के लेम्मा के समान एक निर्माण में, एक पूर्ण-लेबल वाले आदिम सेट को ढूंढकर अवशिष्ट निश्चित-बिंदु।
+* किसी सामान्य प्रकार्य के एक नियत बिंदु का अनुमान लगाने वाला पहला एल्गोरिदम 1967 में [[हर्बर्ट स्कार्फ]] द्वारा विकसित किया गया था।<ref>{{cite journal |last1=Scarf |first1=Herbert |title=सतत मानचित्रण के निश्चित बिंदुओं का अनुमान|journal=SIAM Journal on Applied Mathematics |date=September 1967 |volume=15 |issue=5 |pages=1328–1343 |doi=10.1137/0115116 }}</ref><ref>H. Scarf found the first algorithmic proof: {{SpringerEOM|title=Brouwer theorem|first=M.I.|last=Voitsekhovskii|isbn=1-4020-0609-8}}.</ref> स्कार्फ का एल्गोरिदम एक ढूंढता है {{mvar|ε}}-स्पर्नर के लेम्मा के समान एक निर्माण में, एक पूर्ण-लेबल वाले आदिम सेट को ढूंढकर अवशिष्ट नियत-बिंदु।
 * हेरोल्ड डब्ल्यू. कुह्न द्वारा एक बाद का एल्गोरिदम<ref>{{Cite journal |last=Kuhn |first=Harold W. |date=1968 |title=निश्चित बिंदुओं का सरल अनुमान|jstor=58762 |journal=Proceedings of the National Academy of Sciences of the United States of America |volume=61 |issue=4 |pages=1238–1242 |doi=10.1073/pnas.61.4.1238 |pmid=16591723 |pmc=225246 |doi-access=free }}</ref> आदिम सेटों के बजाय सरल और सरल विभाजन का उपयोग किया गया।
 *सरल दृष्टिकोण को और विकसित करते हुए, ओरिन हैरिसन मेरिल<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> [[होमोटॉपी]] एल्गोरिदम प्रस्तुत किया। एल्गोरिथ्म एक एफ़िन फ़ंक्शन से शुरू करके काम करता है जो एफ का अनुमान लगाता है, और निश्चित बिंदु का पालन करते हुए इसे एफ की ओर विकृत करता है। माइकल टॉड की एक किताब<ref name=":1" />1976 तक विकसित विभिन्न एल्गोरिदम का सर्वेक्षण।
+* बी कर्टिस ईव्स<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-घन के दो विपरीत फलकों को जोड़ने की आवश्यकता है)। वांछित सटीकता को देखते हुए{{mvar|ε}}
 ** केडी आकार का एक हेक्स बोर्ड बनाएं, जहां <math>k > 1/\varepsilon</math>. प्रत्येक शीर्ष z इकाई n-घन में एक बिंदु z/k से मेल खाता है।
 ** अंतर की गणना करें f(z/k) - z/k; ध्यान दें कि अंतर एक एन-वेक्टर है।
 ** शीर्ष z को 1, ..., d में एक लेबल द्वारा लेबल करें, जो अंतर वेक्टर में सबसे बड़े समन्वय को दर्शाता है।
 ** परिणामी लेबलिंग डी खिलाड़ियों के बीच डी-आयामी हेक्स गेम के संभावित खेल से मेल खाती है। इस गेम में एक विजेता होना चाहिए, और गेल जीत का रास्ता बनाने के लिए एक एल्गोरिदम प्रस्तुत करता है।
-** जीत की राह में, एक बिंदु ऐसा होना चाहिए जिसमें एफ<sub>i</sub>(z/k) - z/k सकारात्मक है, और एक आसन्न बिंदु जिसमें f<sub>i</sub>(z/k) - z/k नकारात्मक है। इसका मतलब यह है कि इन दोनों बिंदुओं के बीच f का एक निश्चित बिंदु है।
+** जीत की राह में, एक बिंदु ऐसा होना चाहिए जिसमें एफ<sub>i</sub>(z/k) - z/k सकारात्मक है, और एक आसन्न बिंदु जिसमें f<sub>i</sub>(z/k) - z/k नकारात्मक है। इसका मतलब यह है कि इन दोनों बिंदुओं के बीच f का एक नियत बिंदु है।
-सबसे खराब स्थिति में, इन सभी एल्गोरिदम द्वारा आवश्यक फ़ंक्शन मूल्यांकन की संख्या सटीकता के द्विआधारी प्रतिनिधित्व में घातीय है, अर्थात <math>\Omega(1/\varepsilon)</math>.
+सबसे खराब स्थिति में, इन सभी एल्गोरिदम द्वारा आवश्यक प्रकार्य मूल्यांकन की संख्या सटीकता के द्विआधारी प्रतिनिधित्व में घातीय है, अर्थात <math>\Omega(1/\varepsilon)</math>.
 ==== क्वेरी जटिलता ====
-हिर्श, [[क्रिस्टोस पापादिमित्रियोउ]] और वावसिस ने यह साबित किया<ref name=":0">{{cite journal |last1=Hirsch |first1=Michael D |last2=Papadimitriou |first2=Christos H |last3=Vavasis |first3=Stephen A |title=ब्रौवर फिक्स पॉइंट खोजने के लिए घातीय निचली सीमाएं|journal=Journal of Complexity |date=December 1989 |volume=5 |issue=4 |pages=379–416 |doi=10.1016/0885-064X(89)90017-4 |s2cid=1727254 }}</ref> फ़ंक्शन मूल्यांकन के आधार पर कोई भी एल्गोरिदम, जो एक पाता है {{mvar|ε}}-f का अवशिष्ट निश्चित-बिंदु, आवश्यक है <math>\Omega(L'/\varepsilon)</math> फ़ंक्शन मूल्यांकन, जहां <math>L'</math> फ़ंक्शन का लिप्सचिट्ज़ स्थिरांक है <math>f(x)-x</math> (ध्यान दें कि <math>L-1 \leq L' \leq L+1</math>). ज्यादा ठीक:
+हिर्श, [[क्रिस्टोस पापादिमित्रियोउ]] और वावसिस ने यह साबित किया<ref name=":0">{{cite journal |last1=Hirsch |first1=Michael D |last2=Papadimitriou |first2=Christos H |last3=Vavasis |first3=Stephen A |title=ब्रौवर फिक्स पॉइंट खोजने के लिए घातीय निचली सीमाएं|journal=Journal of Complexity |date=December 1989 |volume=5 |issue=4 |pages=379–416 |doi=10.1016/0885-064X(89)90017-4 |s2cid=1727254 }}</ref> प्रकार्य मूल्यांकन के आधार पर कोई भी एल्गोरिदम, जो एक पाता है {{mvar|ε}}-f का अवशिष्ट नियत-बिंदु, आवश्यक है <math>\Omega(L'/\varepsilon)</math> प्रकार्य मूल्यांकन, जहां <math>L'</math> प्रकार्य का लिप्सचिट्ज़ स्थिरांक है <math>f(x)-x</math> (ध्यान दें कि <math>L-1 \leq L' \leq L+1</math>). ज्यादा ठीक:
-* 2-आयामी फ़ंक्शन (d=2) के लिए, वे एक टाइट बाउंड साबित होते हैं <math>\Theta(L'/\varepsilon)</math>.
+* 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|ε}}-डी-आयामी प्रकार्य के अवशिष्ट नियत-बिंदु की आवश्यकता होती है <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>.
+बाद वाला परिणाम घातांक में एक अंतर छोड़ देता है। चेन और डेंग<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>(डी-आयामी पूर्णांक ग्रिड)। कई अलग-अलग निश्चित-बिंदु प्रमेय हैं, जो उन स्थितियों को बताते हैं जिनके तहत एक अलग फ़ंक्शन का एक निश्चित बिंदु होता है। उदाहरण के लिए, 'आईमुरा-मुरोता-तमुरा प्रमेय' बताता है कि (विशेष रूप से) यदि एफ एक आयत उपसमुच्चय से एक फ़ंक्शन है<math>\mathbb{Z}^d</math>स्वयं के लिए, और f हाइपरक्यूबिक दिशा-संरक्षण फ़ंक्शन है|दिशा-संरक्षण, तो f का एक निश्चित बिंदु है।
+असतत प्रकार्य '' के उपसमुच्चय पर परिभाषित एक प्रकार्य है<math>\mathbb{Z}^d</math>(डी-आयामी पूर्णांक ग्रिड)। कई अलग-अलग नियत-बिंदु प्रमेय हैं, जो उन स्थितियों को बताते हैं जिनके तहत एक अलग प्रकार्य का एक नियत बिंदु होता है। उदाहरण के लिए, 'आईमुरा-मुरोता-तमुरा प्रमेय' बताता है कि (विशेष रूप से) यदि 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> कार्य मूल्यांकन.
+मान लीजिए f पूर्णांक घन से एक दिशा-संरक्षण प्रकार्य है <math>\{1, \dots, n\}^d</math> खुद को। चेन और डेंग<ref name=":2" />साबित करें कि, किसी भी d ≥ 2 और n > 48d के लिए, ऐसे नियत बिंदु की गणना करना आवश्यक है  <math>\Theta(n^{d-1})</math> कार्य मूल्यांकन.
-चेन और डेंग<ref>{{cite journal |last1=Chen |first1=Xi |last2=Deng |first2=Xiaotie |title=On the complexity of 2D discrete fixed point problem |journal=Theoretical Computer Science |date=October 2009 |volume=410 |issue=44 |pages=4448–4456 |doi=10.1016/j.tcs.2009.07.052 |s2cid=2831759 }}</ref> एक अलग असतत-निश्चित-बिंदु समस्या को परिभाषित करें, जिसे वे 2D-BROUWER कहते हैं। यह एक असतत फलन ''f'' पर विचार करता है <math>\{0,\dots, n\}^2</math> जैसे कि, ग्रिड पर प्रत्येक x के लिए, f(x) - x या तो (0, 1) या (1, 0) या (-1, -1) है। लक्ष्य ग्रिड में एक वर्ग ढूंढना है, जिसमें सभी तीन लेबल होते हैं। फ़ंक्शन f को वर्ग को मैप करना होगा <math>\{0,\dots, n\}^2</math>स्वयं के लिए, इसलिए इसे रेखाओं x = 0 और y = 0 को या तो (0, 1) या (1, 0) पर मैप करना होगा; रेखा x = n से या तो (-1, -1) या (0, 1); और रेखा y = n से या तो (-1, -1) या (1,0)। समस्या को '2D-SPERNER' तक कम किया जा सकता है (स्पर्नर के लेम्मा की शर्तों को पूरा करने वाले त्रिभुज में एक पूर्ण-लेबल वाले त्रिकोण की गणना करना), और इसलिए यह PPAD-पूर्ण है। इसका तात्पर्य यह है कि अनुमानित निश्चित-बिंदु की गणना बहुत सरल कार्यों के लिए भी [[पीपीएडी-पूर्ण]] है।
+चेन और डेंग<ref>{{cite journal |last1=Chen |first1=Xi |last2=Deng |first2=Xiaotie |title=On the complexity of 2D discrete fixed point problem |journal=Theoretical Computer Science |date=October 2009 |volume=410 |issue=44 |pages=4448–4456 |doi=10.1016/j.tcs.2009.07.052 |s2cid=2831759 }}</ref> एक अलग असतत-नियत-बिंदु समस्या को परिभाषित करें, जिसे वे 2D-BROUWER कहते हैं। यह एक असतत फलन ''f'' पर विचार करता है <math>\{0,\dots, n\}^2</math> जैसे कि, ग्रिड पर प्रत्येक x के लिए, f(x) - x या तो (0, 1) या (1, 0) या (-1, -1) है। लक्ष्य ग्रिड में एक वर्ग ढूंढना है, जिसमें सभी तीन लेबल होते हैं। प्रकार्य f को वर्ग को चित्रित(मानचित्र) करना होगा <math>\{0,\dots, n\}^2</math>स्वयं के लिए, इसलिए इसे रेखाओं 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 दिया गया है<sup>d</sup> से R तक, g का 'मूल' E में एक बिंदु x है<sup>d</sup> ऐसा कि g(x)=0. एक '{{mvar|ε}}-g का मूल ''E'' में एक बिंदु ''x'' है<sup>घ</sup>ऐसे कि <math>g(x)\leq \varepsilon</math>.
+E से एक प्रकार्य g दिया गया है<sup>d</sup> से R तक, g का 'मूल' E में एक बिंदु x है<sup>d</sup> ऐसा कि g(x)=0. एक '{{mvar|ε}}-g का मूल ''E'' में एक बिंदु ''x'' है<sup>घ</sup>ऐसे कि <math>g(x)\leq \varepsilon</math>.
-फिक्स्ड-पॉइंट गणना रूट-फाइंडिंग का एक विशेष मामला है: ई पर एक फ़ंक्शन एफ दिया गया है<sup>घ</sup>, परिभाषित करें <math>g(x) := |f(x)-x|</math>. स्पष्ट रूप से, x, f का एक निश्चित-बिंदु है यदि और केवल यदि x, g का मूल है, और x एक है {{mvar|ε}}-f का अवशिष्ट निश्चित-बिंदु यदि और केवल यदि x एक है {{mvar|ε}}-जी की जड़. इसलिए, किसी भी [[जड़-खोज एल्गोरिदम]] (एक एल्गोरिदम जो किसी फ़ंक्शन के अनुमानित रूट की गणना करता है) का उपयोग अनुमानित निश्चित-बिंदु खोजने के लिए किया जा सकता है।
+फिक्स्ड-पॉइंट गणना रूट-फाइंडिंग का एक विशेष मामला है: ई पर एक प्रकार्य f दिया गया है<sup>घ</sup>, परिभाषित करें <math>g(x) := |f(x)-x|</math>. स्पष्ट रूप से, x, f का एक नियत-बिंदु है यदि और केवल यदि x, g का मूल है, और x एक है {{mvar|ε}}-f का अवशिष्ट नियत-बिंदु यदि और केवल यदि x एक है {{mvar|ε}}-जी की जड़. इसलिए, किसी भी [[जड़-खोज एल्गोरिदम]] (एक एल्गोरिदम जो किसी प्रकार्य के अनुमानित रूट की गणना करता है) का उपयोग अनुमानित नियत-बिंदु खोजने के लिए किया जा सकता है।
-इसके विपरीत सत्य नहीं है: किसी सामान्य फ़ंक्शन का अनुमानित मूल ढूँढ़ना किसी अनुमानित निश्चित बिंदु को ढूँढ़ने से अधिक कठिन हो सकता है। विशेष रूप से, सिकोरस्की<ref>{{cite journal |last1=Sikorski |first1=K. |title=लिप्सचिट्ज़ स्थिति को संतुष्ट करने वाले अरेखीय समीकरणों का इष्टतम समाधान|journal=Numerische Mathematik |date=June 1984 |volume=43 |issue=2 |pages=225–240 |doi=10.1007/BF01390124 |s2cid=120937024 }}</ref> यह साबित कर दिया कि एक खोज {{mvar|ε}}-रूट की आवश्यकता है <math>\Omega(1/\varepsilon^d)</math> कार्य मूल्यांकन. यह एक-आयामी फ़ंक्शन के लिए भी एक घातीय निचली सीमा देता है (इसके विपरीत, एक {{mvar|ε}}-एक-आयामी फ़ंक्शन का अवशिष्ट निश्चित-बिंदु का उपयोग करके पाया जा सकता है <math>O(\log(1/\varepsilon))</math> द्विभाजन विधि का उपयोग कर प्रश्न)। यहाँ एक प्रमाण रेखाचित्र है।<ref name=":0" />{{Rp|page=35}} एक फ़ंक्शन g बनाएं जो इससे थोड़ा बड़ा हो {{mvar|ε}} ई में हर जगह<sup>d</sup>कुछ बिंदु x के आसपास कुछ छोटे घन को छोड़कर<sub>0</sub>, कहां एक्स<sub>0</sub> जी की अद्वितीय जड़ है. यदि g स्थिरांक L के साथ निरंतर लिप्सचिट्ज़ है, तो x के चारों ओर घन<sub>0</sub> की एक साइड-लंबाई हो सकती है <math>\varepsilon/L</math>. कोई भी एल्गोरिदम जो एक पाता है {{mvar|ε}}-जी के मूल को घनों के एक सेट की जांच करनी चाहिए जो पूरे ई को कवर करता है<sup>घ</sup>; ऐसे घनों की संख्या न्यूनतम है <math>(L/\varepsilon)^d</math>.
+इसके विपरीत सत्य नहीं है: किसी सामान्य प्रकार्य का अनुमानित मूल ढूँढ़ना किसी अनुमानित नियत बिंदु को ढूँढ़ने से अधिक कठिन हो सकता है। विशेष रूप से, सिकोरस्की<ref>{{cite journal |last1=Sikorski |first1=K. |title=लिप्सचिट्ज़ स्थिति को संतुष्ट करने वाले अरेखीय समीकरणों का इष्टतम समाधान|journal=Numerische Mathematik |date=June 1984 |volume=43 |issue=2 |pages=225–240 |doi=10.1007/BF01390124 |s2cid=120937024 }}</ref> यह साबित कर दिया कि एक खोज {{mvar|ε}}-रूट की आवश्यकता है <math>\Omega(1/\varepsilon^d)</math> कार्य मूल्यांकन. यह एक-आयामी प्रकार्य के लिए भी एक घातीय निचली सीमा देता है (इसके विपरीत, एक {{mvar|ε}}-एक-आयामी प्रकार्य का अवशिष्ट नियत-बिंदु का उपयोग करके पाया जा सकता है <math>O(\log(1/\varepsilon))</math> द्विभाजन विधि का उपयोग कर प्रश्न)। यहाँ एक प्रमाण रेखाचित्र है।<ref name=":0" />{{Rp|page=35}} एक प्रकार्य g बनाएं जो इससे थोड़ा बड़ा हो {{mvar|ε}} ई में हर जगह<sup>d</sup>कुछ बिंदु x के आसपास कुछ छोटे घन को छोड़कर<sub>0</sub>, कहां एक्स<sub>0</sub> जी की अद्वितीय जड़ है. यदि g स्थिरांक L के साथ सतत लिप्सचिट्ज़ है, तो x के चारों ओर घन<sub>0</sub> की एक साइड-लंबाई हो सकती है <math>\varepsilon/L</math>. कोई भी एल्गोरिदम जो एक पाता है {{mvar|ε}}-जी के मूल को घनों के एक सेट की जांच करनी चाहिए जो पूरे ई को कवर करता है<sup>घ</sup>; ऐसे घनों की संख्या न्यूनतम है <math>(L/\varepsilon)^d</math>.
-हालाँकि, फ़ंक्शंस के ऐसे वर्ग हैं जिनके लिए अनुमानित मूल ढूंढना अनुमानित निश्चित बिंदु खोजने के बराबर है। एक उदाहरण<ref name=":2">{{cite book |doi=10.1145/1060590.1060638 |chapter=On algorithms for discrete and approximate brouwer fixed points |title=कंप्यूटिंग के सिद्धांत पर सैंतीसवीं वार्षिक एसीएम संगोष्ठी की कार्यवाही|year=2005 |last1=Chen |first1=Xi |last2=Deng |first2=Xiaotie |pages=323–330 |isbn=1581139608 |s2cid=16942881 }}</ref> कार्यों का वर्ग g इस प्रकार है <math>g(x)+x</math> मानचित्र ई<sup>d</sup>स्वयं के लिए (अर्थात: <math>g(x)+x</math> ई में है<sup>ई में सभी एक्स के लिए डी</sup><sup>घ</sup>). ऐसा इसलिए है, क्योंकि ऐसे प्रत्येक फ़ंक्शन के लिए, function <math>f(x) := g(x)+x</math> ब्रौवर के निश्चित-बिंदु प्रमेय की शर्तों को संतुष्ट करता है। स्पष्ट रूप से, x, f का एक निश्चित-बिंदु है यदि और केवल यदि x, g का मूल है, और x एक है {{mvar|ε}}-f का अवशिष्ट निश्चित-बिंदु यदि और केवल यदि x एक है {{mvar|ε}}-जी की जड़. चेन और डेंग<ref name=":2" />दिखाएँ कि इन समस्याओं के अलग-अलग रूप कम्प्यूटेशनल रूप से समतुल्य हैं: दोनों समस्याओं की आवश्यकता है  <math>\Theta(n^{d-1})</math> कार्य मूल्यांकन.
+हालाँकि, फ़ंक्शंस के ऐसे वर्ग हैं जिनके लिए अनुमानित मूल ढूंढना अनुमानित नियत बिंदु खोजने के बराबर है। एक उदाहरण<ref name=":2">{{cite book |doi=10.1145/1060590.1060638 |chapter=On algorithms for discrete and approximate brouwer fixed points |title=कंप्यूटिंग के सिद्धांत पर सैंतीसवीं वार्षिक एसीएम संगोष्ठी की कार्यवाही|year=2005 |last1=Chen |first1=Xi |last2=Deng |first2=Xiaotie |pages=323–330 |isbn=1581139608 |s2cid=16942881 }}</ref> कार्यों का वर्ग g इस प्रकार है <math>g(x)+x</math> मानचित्र ई<sup>d</sup>स्वयं के लिए (अर्थात: <math>g(x)+x</math> ई में है<sup>ई में सभी एक्स के लिए डी</sup><sup>घ</sup>). ऐसा इसलिए है, क्योंकि ऐसे प्रत्येक प्रकार्य के लिए, function <math>f(x) := g(x)+x</math> ब्रौवर के नियत-बिंदु प्रमेय की शर्तों को संतुष्ट करता है। स्पष्ट रूप से, x, f का एक नियत-बिंदु है यदि और केवल यदि x, g का मूल है, और x एक है {{mvar|ε}}-f का अवशिष्ट नियत-बिंदु यदि और केवल यदि x एक है {{mvar|ε}}-जी की जड़. चेन और डेंग<ref name=":2" />दिखाएँ कि इन समस्याओं के अलग-अलग रूप कम्प्यूटेशनल रूप से समतुल्य हैं: दोनों समस्याओं की आवश्यकता है  <math>\Theta(n^{d-1})</math> कार्य मूल्यांकन.
 == संचार जटिलता ==
-रफ़गार्डन और वीनस्टीन<ref>{{cite book |doi=10.1109/FOCS.2016.32 |chapter=On the Communication Complexity of Approximate Fixed Points |title=2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) |year=2016 |last1=Roughgarden |first1=Tim |last2=Weinstein |first2=Omri |pages=229–238 |isbn=978-1-5090-3933-3 |s2cid=87553 }}</ref> अनुमानित निश्चित-बिंदु की गणना की [[संचार जटिलता]] का अध्ययन किया। उनके मॉडल में, दो एजेंट हैं: उनमें से एक फ़ंक्शन f जानता है और दूसरा फ़ंक्शन g जानता है। दोनों कार्य लिप्सचिट्ज़ निरंतर हैं और ब्रौवर की शर्तों को पूरा करते हैं। लक्ष्य समग्र फ़ंक्शन के अनुमानित निश्चित बिंदु की गणना करना है <math>g\circ f</math>. वे दिखाते हैं कि नियतिवादी संचार जटिलता मौजूद है <math>\Omega(2^d)</math>.
+रफ़गार्डन और वीनस्टीन<ref>{{cite book |doi=10.1109/FOCS.2016.32 |chapter=On the Communication Complexity of Approximate Fixed Points |title=2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) |year=2016 |last1=Roughgarden |first1=Tim |last2=Weinstein |first2=Omri |pages=229–238 |isbn=978-1-5090-3933-3 |s2cid=87553 }}</ref> अनुमानित नियत-बिंदु की गणना की [[संचार जटिलता]] का अध्ययन किया। उनके मॉडल में, दो एजेंट हैं: उनमें से एक प्रकार्य f जानता है और दूसरा प्रकार्य g जानता है। दोनों कार्य लिप्सचिट्ज़ सतत हैं और ब्रौवर की शर्तों को पूरा करते हैं। लक्ष्य समग्र प्रकार्य के अनुमानित नियत बिंदु की गणना करना है <math>g\circ f</math>. वे दिखाते हैं कि नियतिवादी संचार जटिलता मौजूद है <math>\Omega(2^d)</math>.
 == संदर्भ ==

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 00:42, 22 July 2023

Contents

परिभाषाएँ