حسابات النقطة الثابتة

يشير حساب النقطة الثابتة إلى عملية حساب نقطة ثابتة دقيقة أو تقريبية لدالة معينة. ^{[ 1 ]} في أكثر أشكالها شيوعًا، الدالة المعطاة${\displaystyle f}$يفي بشرط نظرية النقطة الثابتة لبروير : أي،${\displaystyle f}$دالة متصلة، وتُسقط المكعب ذي البعد d على نفسه. تضمن نظرية النقطة الثابتة لبروير أن${\displaystyle f}$للمسألة نقطة ثابتة، لكن البرهان ليس بنائيًا . وقد طُورت خوارزميات متنوعة لحساب نقطة ثابتة تقريبية. تُستخدم هذه الخوارزميات في مهام مختلفة، مثل:

• حساب توازن ناش ،
• حساب توازن السوق ،
• تحليل الأنظمة الديناميكية .

يُرمز إلى الفترة 1 بالرمز${\displaystyle E:=[0,1]}$ويُرمز إلى المكعب ذي البعد d بوحدة واحدة بـ${\displaystyle E^{d}}$دالة متصلة${\displaystyle f}$يتم تعريفها على${\displaystyle E^{d}}$(من${\displaystyle E^{d}}$(لنفسه) . غالبًا ما يُفترض أن${\displaystyle f}$ليست متصلة فحسب، بل متصلة أيضًا وفقًا لشرط ليبشيتز ، أي بالنسبة لبعض الثوابت${\displaystyle L}$، ${\displaystyle |f(x)-f(y)|\leq L\cdot |xy|}$للجميع${\displaystyle x,y}$في${\displaystyle E^{d}}$.

نقطة ثابتة من${\displaystyle f}$هذه نقطة${\displaystyle x}$في${\displaystyle E^{d}}$بحيث${\displaystyle f(x)=x}$بحسب نظرية النقطة الثابتة لبروير ، فإن أي دالة متصلة من${\displaystyle E^{d}}$ للدالة نفسها نقطة ثابتة. لكن بالنسبة للدوال العامة، يستحيل حساب النقطة الثابتة بدقة، لأنها قد تكون عددًا حقيقيًا عشوائيًا . تبحث خوارزميات حساب النقطة الثابتة عن نقاط ثابتة تقريبية . هناك عدة معايير للنقطة الثابتة التقريبية، ومن المعايير الشائعة ما يلي: ^{[ 2 ]}

• معيار الباقي : بالنظر إلى معلمة التقريب${\displaystyle \varepsilon >0}$، نقطة ثابتة متبقية من نوع ε${\displaystyle f}$هذه نقطة${\displaystyle x}$في${\displaystyle E^{d}}$بحيث${\displaystyle |f(x)-x|\leq \varepsilon }$أين هنا${\displaystyle |\cdot |}$يرمز إلى المعيار الأقصى . أي أن جميع${\displaystyle d}$إحداثيات الفرق${\displaystyle f(x)-x}$ينبغي ألا تتجاوز ε . ^{[ 3 ] : 4}
• المعيار المطلق : بالنظر إلى معلمة التقريب${\displaystyle \delta >0}$، نقطة ثابتة مطلقة من نوع دلتا${\displaystyle f}$هذه نقطة${\displaystyle x}$في${\displaystyle E^{d}}$بحيث${\displaystyle |x-x_{0}|\leq \delta }$، أين${\displaystyle x_{0}}$أي نقطة ثابتة من${\displaystyle f}$.
• المعيار النسبي : بالنظر إلى معلمة تقريبية${\displaystyle \delta >0}$، نقطة ثابتة نسبية من نوع دلتا${\displaystyle f}$هي نقطة x في${\displaystyle E^{d}}$بحيث${\displaystyle |x-x_{0}|/|x_{0}|\leq \delta }$، أين${\displaystyle x_{0}}$أي نقطة ثابتة من${\displaystyle f}$.

بالنسبة للدوال المتصلة وفقًا لشرط ليبشيتز، يكون المعيار المطلق أقوى من معيار الباقي: إذا${\displaystyle f}$هي دالة متصلة ليبشيتز ذات ثابت${\displaystyle L}$، ثم${\displaystyle |x-x_{0}|\leq \delta }$يشير إلى${\displaystyle |f(x)-f(x_{0})|\leq L\cdot \delta }$. منذ${\displaystyle x_{0}}$هي نقطة ثابتة لـ${\displaystyle f}$وهذا يعني${\displaystyle |f(x)-x_{0}|\leq L\cdot \delta }$، لذا${\displaystyle |f(x)-x|\leq (1+L)\cdot \delta }$لذلك، فإن النقطة الثابتة المطلقة من النوع δ هي أيضًا نقطة ثابتة متبقية من النوع ε مع${\displaystyle \varepsilon =(1+L)\cdot \delta }$.

تتمثل الخطوة الأساسية في خوارزمية حساب النقطة الثابتة في استعلام القيمة : بالنظر إلى أي${\displaystyle x}$في${\displaystyle E^{d}}$يتم تزويد الخوارزمية بأداة وسيطة.${\displaystyle {\tilde {f}}}$ل${\displaystyle f}$التي تُعيد القيمة${\displaystyle f(x)}$تعتمد دقة النقطة الثابتة التقريبية على الخطأ في أوراكل${\displaystyle {\tilde {f}}(x)}$.

الوظيفة${\displaystyle f}$يمكن الوصول إليه عبر استعلامات التقييم : لأي${\displaystyle x}$يمكن للخوارزمية أن تقيّم${\displaystyle f(x)}$. عادةً ما يتم تحديد تعقيد وقت التشغيل للخوارزمية من خلال عدد عمليات التقييم المطلوبة.

دالة متصلة ليبشيتز ذات ثابت${\displaystyle L}$يُطلق عليه اسم انكماشي إذا${\displaystyle L<1}$يُطلق عليه اسم "ضعيف الانكماش" إذا${\displaystyle L\leq 1}$لكل دالة انكماشية تحقق شروط براور نقطة ثابتة فريدة . علاوة على ذلك، فإن حساب النقطة الثابتة للدوال الانكماشية أسهل منه للدوال العامة.

كانت خوارزمية التكرار ذات النقطة الثابتة لباناش أول خوارزمية لحساب النقطة الثابتة . تنص نظرية النقطة الثابتة لباناش على أنه عند تطبيق التكرار ذي النقطة الثابتة على دالة انكماش، فإن الخطأ بعد${\displaystyle t}$التكرارات موجودة في${\displaystyle O(L^{t})}$لذلك، فإن عدد التقييمات المطلوبة لـ${\displaystyle \delta }$النقطة الثابتة النسبية تقريبًا${\displaystyle \log _{L}(\delta )=\log(\delta )/\log(L)=\log(1/\delta )/\log(1/L)}$أظهر سيكورسكي ووزنياكوفسكي ^{[ 4 ]} أن خوارزمية باناش تكون مثالية عندما يكون البُعد كبيرًا. تحديدًا، عندما${\displaystyle d\geq \log(1/\delta )/\log(1/L)}$عدد التقييمات المطلوبة لأي خوارزمية لـ${\displaystyle \delta }$تكون قيمة النقطة الثابتة النسبية أكبر من 50% من عدد عمليات التقييم المطلوبة بواسطة خوارزمية التكرار. لاحظ أنه عندما${\displaystyle L}$عندما يقترب العدد من 1، يقترب عدد التقييمات من اللانهاية. لا يمكن لأي خوارزمية محدودة حساب${\displaystyle \delta }$- نقطة ثابتة مطلقة لجميع الدوال ذات${\displaystyle L=1}$[ ^{5 ]​}

متى${\displaystyle L}$عندما تكون قيمة δ أقل من 1 و d = 1، فإن الخوارزمية المثلى هي خوارزمية غلاف النقطة الثابتة (FPE) لسيكورسكي ووزنياكوفسكي. ^{[ 4 ]} تجد هذه الخوارزمية نقطة ثابتة نسبية لـ δ باستخدام${\displaystyle O(\log(1/\delta )+\log \log(1/(1-L)))}$الاستعلامات، ونقطة ثابتة مطلقة من نوع δ باستخدام${\displaystyle O(\log(1/\delta )))}$الاستعلامات. هذا أسرع من خوارزمية التكرار ذات النقطة الثابتة. ^{[ 6 ]}

متى${\displaystyle d>1}$لكن ليس كبيرًا جدًا، و${\displaystyle L\leq 1}$الخوارزمية المثلى هي خوارزمية القطع الناقص الداخلي (المبنية على طريقة القطع الناقص ). ^{[ 7 ]} وهي تجد نقطة ثابتة متبقية من النوع ε باستخدام${\displaystyle O(d\cdot \log(1/\varepsilon ))}$التقييمات. متى${\displaystyle L<1}$، يجد${\displaystyle \delta }$- نقطة ثابتة مطلقة باستخدام${\displaystyle O(d\cdot [\log(1/\delta )+\log(1/(1-L))])}$التقييمات.

قدم شيلمان وسيكورسكي ^{[ 8 ]} خوارزمية تسمى BEFix (نقطة ثابتة لغلاف التنصيف) لحساب نقطة ثابتة متبقية ε لدالة ثنائية الأبعاد مع '${\displaystyle L\leq 1}$باستخدام فقط${\displaystyle 2\lceil \log _{2}(1/\varepsilon )\rceil +1}$استعلامات. ثم قدموا لاحقًا ^{[ 9 ]} تحسينًا يُسمى BEDFix (نقطة ثابتة ذات قطع عميق في غلاف التنصيف)، مع نفس ضمان أسوأ حالة ولكن بأداء تجريبي أفضل. عندما${\displaystyle L<1}$يمكن لـ BEDFix أيضًا حساب${\displaystyle \delta }$- نقطة ثابتة مطلقة باستخدام${\displaystyle O(\log(1/\varepsilon )+\log(1/(1-L)))}$استفسارات.

قدم شيلمان وسيكورسكي ^{[ 2 ]} خوارزمية تسمى PFix لحساب نقطة ثابتة متبقية من النوع ε لدالة ذات بُعد d حيث L ≤ 1، باستخدام${\displaystyle O(\log ^{d}(1/\varepsilon ))}$استفسارات. متى${\displaystyle L}$< 1، يمكن تنفيذ PFix باستخدام${\displaystyle \varepsilon =(1-L)\cdot \delta }$وفي هذه الحالة، يتم حساب نقطة ثابتة مطلقة من نوع دلتا، باستخدام${\displaystyle O(\log ^{d}(1/[(1-L)\delta ]))}$الاستعلامات. إنها أكثر كفاءة من خوارزمية التكرار عندما${\displaystyle L}$يقترب من 1. الخوارزمية تكرارية: فهي تتعامل مع دالة ذات أبعاد d عن طريق استدعاءات متكررة على دوال ذات أبعاد ( d -1).

بالنسبة للدوال ذات ثابت ليبشيتز${\displaystyle L}$> 1، حساب النقطة الثابتة أصعب بكثير.

بالنسبة لدالة أحادية البعد ( d = 1)، أ${\displaystyle \delta }$يمكن إيجاد النقطة الثابتة المطلقة باستخدام${\displaystyle O(\log(1/\delta )))}$الاستعلامات باستخدام طريقة التنصيف : ابدأ بالفترة الزمنية${\displaystyle E:=[0,1]}$في كل تكرار، دع${\displaystyle x}$ليكن مركز الفترة الحالية، واحسب${\displaystyle f(x)}$؛ لو${\displaystyle f(x)>x}$ثم قم بالتكرار على الفترة الفرعية إلى يمين${\displaystyle x}$وإلا، فقم بالتكرار على الفترة الزمنية إلى يسار${\displaystyle x}$لاحظ أن الفترة الحالية تحتوي دائمًا على نقطة ثابتة، لذلك بعد${\displaystyle O(\log(1/\delta )))}$في حالة الاستفسارات، فإن أي نقطة في الفترة المتبقية هي${\displaystyle \delta }$-النقطة الثابتة المطلقة لـ${\displaystyle f}$جلسة${\displaystyle \delta$ :=\varepsilon /(L+1)} ، حيث${\displaystyle L}$يمثل ثابت ليبشيتز، ويعطي نقطة ثابتة متبقية من النوع ε ، باستخدام${\displaystyle O(\log(L/\varepsilon )=\log(L)+\log(1/\varepsilon ))}$استفسارات. ^{[ 3 ]}

بالنسبة للدوال في بعدين أو أكثر، تصبح المشكلة أكثر تعقيدًا. أثبت شيلمان وسيكورسكي ^{[ 2 ]} أنه لأي عددين صحيحين d ≥ 2 و${\displaystyle L}$> 1، إيجاد نقطة ثابتة مطلقة من نوع دلتا ذات بُعد d${\displaystyle L}$قد تتطلب الدوال التي تحقق شرط ليبشيتز عددًا لا نهائيًا من عمليات التقييم. وتتلخص فكرة البرهان فيما يلي: لأي عدد صحيح T > 1 وأي سلسلة من T من استعلامات التقييم (قد تكون تكيفية)، يمكن إنشاء دالتين متصلتين وفقًا لشرط ليبشيتز بثابت${\displaystyle L}$وتعطي هذه الاستعلامات نفس الإجابة، لكن إحداها لها نقطة ثابتة فريدة عند ( x , 0) والأخرى لها نقطة ثابتة فريدة عند ( x , 1). لا يمكن لأي خوارزمية تستخدم T من التقييمات التمييز بين هاتين الدالتين، وبالتالي لا يمكنها إيجاد نقطة ثابتة مطلقة من نوع دلتا . وينطبق هذا على أي عدد صحيح محدود T.

تم تطوير العديد من الخوارزميات القائمة على تقييمات الدوال لإيجاد نقطة ثابتة متبقية من نوع ε .

الدالة المنفصلة هي دالة معرفة على مجموعة جزئية من${\displaystyle \mathbb {Z} ^{d}}$( شبكة الأعداد الصحيحة ذات الأبعاد d ). توجد عدة نظريات للنقطة الثابتة المنفصلة ، ​​تنص على الشروط التي بموجبها يكون للدالة المنفصلة نقطة ثابتة. على سبيل المثال، تنص نظرية إيمورا-موروتا-تامورا على أنه (على وجه الخصوص) إذا${\displaystyle f}$هي دالة من مجموعة جزئية مستطيلة من${\displaystyle \mathbb {Z} ^{d}}$لنفسه، و${\displaystyle f}$إذا كان مكعبًا فائقًا يحافظ على الاتجاه ، فـ${\displaystyle f}$له نقطة ثابتة.

يترك${\displaystyle f}$لتكن دالة تحافظ على الاتجاه من مكعب الأعداد الصحيحة${\displaystyle \{1,\dots ,n\}^{d}}$إلى نفسها. أثبت تشين ودينغ ^{[ 20 ]} أنه لأي قيمة d ≥ 2 و n > 48 d ، فإن حساب مثل هذه النقطة الثابتة يتطلب ${\displaystyle \Theta (n^{d-1})}$تقييمات الدوال.

عرّف تشين ودينغ ^{[ 21 ]} مسألة نقطة ثابتة منفصلة مختلفة، أطلقوا عليها اسم 2D-BROUWER . وهي تأخذ في الاعتبار دالة منفصلة${\displaystyle f}$على${\displaystyle \{0,\dots ,n\}^{2}}$بحيث يكون لكل قيمة x على الشبكة،${\displaystyle f}$( x ) - x إما (0, 1) أو (1, 0) أو (-1, -1). الهدف هو إيجاد مربع في الشبكة يحتوي على جميع هذه القيم الثلاث.${\displaystyle f}$يجب رسم خريطة للمربع${\displaystyle \{0,\dots ,n\}^{2}}$لذا، يجب أن تُسقط الدالة الخطين x = 0 و y = 0 إما على النقطة (0, 1) أو (1, 0)؛ والخط x = n على النقطة (-1, -1) أو (0, 1)؛ والخط y = n على النقطة (-1, -1) أو (1, 0). يمكن اختزال المسألة إلى مسألة سبيرنر ثنائية الأبعاد (حساب مثلث مُصنَّف بالكامل في عملية تثليث تُحقق شروط مبرهنة سبيرنر )، وبالتالي فهي مسألة كاملة من نوع PPAD . هذا يعني أن حساب نقطة ثابتة تقريبية هو مسألة كاملة من نوع PPAD حتى بالنسبة للدوال البسيطة جدًا.

بالنظر إلى دالة${\displaystyle g}$من${\displaystyle E^{d}}$إلى R ، جذر من${\displaystyle g}$هي نقطة x في${\displaystyle E^{d}}$بحيث${\displaystyle g}$( x ) = 0. الجذر ε للدالة g هو نقطة x في${\displaystyle E^{d}}$بحيث${\displaystyle g(x)\leq \varepsilon }$.

تُعد حسابات النقطة الثابتة حالة خاصة من إيجاد الجذور: بالنظر إلى دالة${\displaystyle f}$على${\displaystyle E^{d}}$، يُعرِّف${\displaystyle g(x):=|f(x)-x|}$. X هي نقطة ثابتة لـ${\displaystyle f}$إذا وفقط إذا كان x جذرًا لـ${\displaystyle g}$و x هي نقطة ثابتة متبقية من النوع ε لـ${\displaystyle f}$إذا وفقط إذا كان x جذرًا من النوع ε لـ${\displaystyle g}$لذلك، يمكن استخدام أي خوارزمية لإيجاد الجذر (خوارزمية تحسب جذرًا تقريبيًا لدالة) لإيجاد نقطة ثابتة تقريبية.

ليس العكس صحيحًا: قد يكون إيجاد جذر تقريبي لدالة عامة أصعب من إيجاد نقطة ثابتة تقريبية. على وجه الخصوص، أثبت سيكورسكي ^{[ 22 ]} أن إيجاد جذر من النوع ε يتطلب${\displaystyle \Omega (1/\varepsilon ^{d})}$تقييمات الدالة. وهذا يعطي حدًا أدنى أُسّيًا حتى للدالة أحادية البُعد (على النقيض من ذلك، يمكن إيجاد نقطة ثابتة متبقية من النوع ε لدالة أحادية البُعد باستخدام${\displaystyle O(\log(1/\varepsilon ))}$الاستعلامات باستخدام طريقة التنصيف ). إليك مخططًا للبرهان. ^{[ 3 ] : 35} أنشئ دالة${\displaystyle g}$وهي أكبر قليلاً من ε في كل مكان في${\displaystyle E^{d}}$باستثناء مكعب صغير حول نقطة ما x ₀ ، حيث x ₀ هو الجذر الوحيد لـ${\displaystyle g}$. لو${\displaystyle g}$هل هي دالة ليبشيتز متصلة ذات ثابت${\displaystyle L}$إذن، يمكن أن يكون طول ضلع المكعب حول x _{0 هو}${\displaystyle \varepsilon /L}$أي خوارزمية تجد جذرًا من نوع ε لـ${\displaystyle g}$يجب فحص مجموعة من المكعبات التي تغطي كامل${\displaystyle E^{d}}$عدد هذه المكعبات لا يقل عن${\displaystyle (L/\varepsilon )^{d}}$.

مع ذلك، توجد فئات من الدوال يكون فيها إيجاد جذر تقريبي مكافئًا لإيجاد نقطة ثابتة تقريبية. ومن الأمثلة على ذلك ^{[ 20 ]} فئة الدوال${\displaystyle g}$بحيث${\displaystyle g(x)+x}$خرائط${\displaystyle E^{d}}$ لنفسه (أي:${\displaystyle g(x)+x}$هو في${\displaystyle E^{d}}$لكل x في${\displaystyle E^{d}}$وذلك لأنه بالنسبة لكل دالة من هذا القبيل، فإن الدالة${\displaystyle f(x):=g(x)+x}$يستوفي X شروط نظرية النقطة الثابتة لبروير. X هي نقطة ثابتة لـ${\displaystyle f}$إذا وفقط إذا كان x جذرًا لـ${\displaystyle g}$و x هي نقطة ثابتة متبقية من النوع ε لـ${\displaystyle f}$إذا وفقط إذا كان x جذرًا من النوع ε لـ${\displaystyle g}$أظهر تشين ودينغ ^{[ 20 ]} أن المتغيرات المنفصلة لهذه المسائل متكافئة حسابيًا: تتطلب كلتا المسألتين ${\displaystyle \Theta (n^{d-1})}$تقييمات الدوال.

درس رافغاردن وواينشتاين ^{[ 23 ]} تعقيد الاتصال لحساب نقطة ثابتة تقريبية. في نموذجهما، يوجد عاملان: أحدهما يعرف دالة${\displaystyle f}$والآخر يعرف وظيفة${\displaystyle g}$كلتا الدالتين متصلتان وفقًا لشرط ليبشيتز وتستوفيان شروط براور. الهدف هو حساب نقطة ثابتة تقريبية للدالة المركبة.${\displaystyle g\circ f}$تُظهر هذه النتائج أن تعقيد الاتصال الحتمي موجود في${\displaystyle \Omega (2^{d})}$.

• ياناكاكيس، ميهاليس (مايو 2009). "التوازنات، والنقاط الثابتة، وفئات التعقيد" . مجلة مراجعة علوم الحاسوب . 3 (2): 71-85 . arXiv : 0802.2831 . doi : 10.1016/j.cosrev.2009.03.004 .