निश्चित-बिंदु गणना

From Vigyanwiki
Revision as of 15:49, 14 July 2023 by alpha>Indicwiki (Created page with "{{Short description|Computing the fixed point of a function}} निश्चित-बिंदु गणना किसी दिए गए फ़ंक्शन के...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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

परिभाषाएँ

an example function with three fixed points
तीन निश्चित बिंदुओं वाले एक उदाहरण फ़ंक्शन का ग्राफ़

इकाई अंतराल को निरूपित किया जाता है , और इकाई N-घन|d-आयामी घन को E द्वारा निरूपित किया जाता है. एक सतत फलन f को E पर परिभाषित किया गया है (ई सेस्वयं को)। अक्सर, यह माना जाता है कि f न केवल निरंतर है, बल्कि लिप्सचिट्ज़ निरंतर भी है, अर्थात, कुछ स्थिरांक L के लिए, ई में सभी एक्स, वाई के लिए.

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

  • अवशिष्ट मानदंड: एक सन्निकटन पैरामीटर दिया गया है , एकε-f का अवशिष्ट निश्चित-बिंदु E में एक बिंदु x हैऐसे कि , यहाँ कहाँ |.. अर्थात सभी d निर्देशांक में अंतर है अधिक से अधिक होना चाहिए ε.[3]: 4 
  • पूर्ण मानदंड: एक सन्निकटन पैरामीटर दिया गया है , f का एक δ-पूर्ण निश्चित-बिंदु E में एक बिंदु x हैऐसे कि , कहाँ f का कोई निश्चित बिंदु है।
  • 'सापेक्ष मानदंड': एक सन्निकटन पैरामीटर दिया गया है , f का एक δ-सापेक्ष निश्चित-बिंदु E में एक बिंदु x हैऐसे कि , कहाँ f का कोई निश्चित बिंदु है।

लिप्सचिट्ज़-निरंतर कार्यों के लिए, पूर्ण मानदंड अवशिष्ट मानदंड से अधिक मजबूत है: यदि एफ निरंतर एल के साथ लिप्सचिट्ज़-निरंतर है, तो तात्पर्य . तब से f का एक निश्चित बिंदु है, इसका तात्पर्य है , इसलिए . इसलिए, एक δ-पूर्ण निश्चित-बिंदु भी एक है ε-अवशिष्ट निश्चित-बिंदु के साथ .

निश्चित-बिंदु गणना एल्गोरिदम का सबसे बुनियादी चरण एक मान क्वेरी है: में कोई x दिया गया है, द[sentence fragment]

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

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

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

computing a fixed point using function iteration
फ़ंक्शन पुनरावृत्ति का उपयोग करके एक निश्चित बिंदु की गणना करना

निश्चित-बिंदु गणना के लिए पहला एल्गोरिदम बानाच का निश्चित-बिंदु पुनरावृत्ति एल्गोरिदम था। बानाच निश्चित बिंदु प्रमेय|बानाच का निश्चित-बिंदु प्रमेय का तात्पर्य है कि, जब निश्चित-बिंदु पुनरावृत्ति को संकुचन मानचित्रण पर लागू किया जाता है, तो टी पुनरावृत्ति के बाद त्रुटि होती है . इसलिए, δ-सापेक्ष निश्चित-बिंदु के लिए आवश्यक मूल्यांकनों की संख्या लगभग है . सिकोरस्की और वोज्नियाकोव्स्की[4] दिखाया गया कि जब आयाम बड़ा होता है तो बानाच का एल्गोरिदम इष्टतम होता है। विशेष रूप से, जब , δ-सापेक्ष निश्चित-बिंदु के लिए किसी भी एल्गोरिदम के आवश्यक मूल्यांकन की संख्या पुनरावृत्ति एल्गोरिदम द्वारा आवश्यक मूल्यांकन की संख्या 50% से अधिक है। ध्यान दें कि जब एल 1 के करीब पहुंचता है, तो मूल्यांकन की संख्या अनंत तक पहुंच जाती है। वास्तव में, कोई भी परिमित एल्गोरिथ्म L=1 वाले सभी कार्यों के लिए δ-पूर्ण निश्चित बिंदु की गणना नहीं कर सकता है।[5]

जब एल <1 और डी = 1, इष्टतम एल्गोरिदम सिकोरस्की और वोज्नियाकोव्स्की का 'फिक्स्ड प्वाइंट एनवेलप' (एफपीई) एल्गोरिदम है।[4]इसका उपयोग करके δ-सापेक्ष निश्चित बिंदु पाया जाता है प्रश्न, और एक δ-पूर्ण निश्चित बिंदु का उपयोग करना प्रश्न. यह निश्चित-बिंदु पुनरावृत्ति एल्गोरिथ्म से बहुत तेज़ है।[6] जब d>1 लेकिन बहुत बड़ा नहीं है, और L ≤ 1, इष्टतम एल्गोरिथ्म आंतरिक-दीर्घवृत्ताभ एल्गोरिथ्म (दीर्घवृत्ताभ विधि पर आधारित) है।[7] यह एक पाता है ε-अवशिष्ट निश्चित-बिंदु का उपयोग कर रहा है मूल्यांकन. जब L<1, यह एक δ-निरपेक्ष निश्चित बिंदु का उपयोग करके पाता है मूल्यांकन.

शेलमैन और सिकोरस्की[8] की गणना के लिए बीईफिक्स (बाइसेक्शन लिफाफा फिक्स्ड-पॉइंट) नामक एक एल्गोरिदम प्रस्तुत किया ε-केवल L ≤ 1 का उपयोग करते हुए, द्वि-आयामी फ़ंक्शन का अवशिष्ट निश्चित-बिंदु प्रश्न. वे बाद में[9] समान सबसे खराब स्थिति की गारंटी लेकिन बेहतर अनुभवजन्य प्रदर्शन के साथ, BEDFix (बाइसेक्शन लिफाफा डीप-कट फिक्स्ड-पॉइंट) नामक एक सुधार प्रस्तुत किया। जब L<1, BEDFix का उपयोग करके δ-पूर्ण निश्चित-बिंदु की गणना भी की जा सकती है प्रश्न.

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

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

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


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

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

एक आयाम

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


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

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

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

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

सबसे खराब स्थिति में, इन सभी एल्गोरिदम द्वारा आवश्यक फ़ंक्शन मूल्यांकन की संख्या सटीकता के द्विआधारी प्रतिनिधित्व में घातीय है, अर्थात .

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

हिर्श, क्रिस्टोस पापादिमित्रियोउ और वावसिस ने यह साबित किया[3] फ़ंक्शन मूल्यांकन के आधार पर कोई भी एल्गोरिदम, जो एक पाता है ε-f का अवशिष्ट निश्चित-बिंदु, आवश्यक है फ़ंक्शन मूल्यांकन, जहां फ़ंक्शन का लिप्सचिट्ज़ स्थिरांक है (ध्यान दें कि ). ज्यादा ठीक:

  • 2-आयामी फ़ंक्शन (d=2) के लिए, वे एक टाइट बाउंड साबित होते हैं .
  • किसी भी d ≥ 3 के लिए, an ज्ञात करना ε-डी-आयामी फ़ंक्शन के अवशिष्ट निश्चित-बिंदु की आवश्यकता होती है प्रश्न और प्रश्न.

बाद वाला परिणाम घातांक में एक अंतर छोड़ देता है। चेन और डेंग[18]अंतर को बंद कर दिया. उन्होंने यह साबित कर दिया कि, किसी भी d ≥ 2 और के लिए और , कंप्यूटिंग के लिए आवश्यक प्रश्नों की संख्या ε-अवशिष्ट निश्चित-बिंदु में है .

असतत निश्चित-बिंदु गणना

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

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

चेन और डेंग[19] एक अलग असतत-निश्चित-बिंदु समस्या को परिभाषित करें, जिसे वे 2D-BROUWER कहते हैं। यह एक असतत फलन f पर विचार करता है जैसे कि, ग्रिड पर प्रत्येक x के लिए, f(x) - x या तो (0, 1) या (1, 0) या (-1, -1) है। लक्ष्य ग्रिड में एक वर्ग ढूंढना है, जिसमें सभी तीन लेबल होते हैं। फ़ंक्शन f को वर्ग को मैप करना होगा स्वयं के लिए, इसलिए इसे रेखाओं 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 हैऐसे कि .

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

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

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

संचार जटिलता

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

संदर्भ

  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]
  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.
  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.
  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.
  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.
  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.


अग्रिम पठन