การคำนวณจุดตรึงหมายถึงกระบวนการคำนวณจุดตรึง ที่แน่นอนหรือโดยประมาณ ของฟังก์ชันที่กำหนด^{[ 1 ]}ในรูปแบบที่พบได้บ่อยที่สุด ฟังก์ชันที่กำหนดจะตรงตามเงื่อนไขของทฤษฎีบทจุดตรึงของ Brouwerนั่นคือมีความต่อเนื่องและแมปลูกบาศก์d หน่วย ไปยังตัวมันเองทฤษฎีบทจุดตรึงของ Brouwerรับประกันว่ามีจุดตรึง แต่การพิสูจน์ไม่ใช่แบบสร้างสรรค์มีการคิดค้นอัลกอริทึมต่างๆ สำหรับการคำนวณจุดตรึงโดยประมาณ อัลกอริทึมดังกล่าวใช้ในงานต่างๆ เช่น ${\displaystyle f}$${\displaystyle f}$${\displaystyle f}$

• การ คำนวณสมดุลแนช
• การ คำนวณจุดสมดุลของตลาด
• การวิเคราะห์ระบบพลวัต

ช่วงหน่วยจะถูกแทนด้วยและลูกบาศก์หน่วยมิติdจะถูกแทนด้วยฟังก์ชันต่อเนื่องถูกกำหนดบน(จากไปยังตัวมันเอง) บ่อยครั้งที่ถือว่าไม่เพียงแต่ต่อเนื่องเท่านั้น แต่ยังต่อ เนื่องแบบลิปชิตซ์ด้วยนั่นคือ สำหรับค่าคงที่บางค่าสำหรับ ทุกใน${\displaystyle E:=[0,1]}$${\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}}$

จุดตรึงของคือจุดในที่. ตามทฤษฎีบทจุดตรึงของ Brouwerฟังก์ชันต่อเนื่องใดๆ จาก ไปยังตัวมันเองจะมีจุดตรึง แต่สำหรับฟังก์ชันทั่วไป เป็นไปไม่ได้ที่จะคำนวณจุดตรึงได้อย่างแม่นยำ เนื่องจากอาจเป็นจำนวนจริง ใดๆ ก็ได้ อัลกอริทึมการคำนวณจุดตรึงจะมองหา จุดตรึง โดยประมาณมีเกณฑ์หลายประการสำหรับจุดตรึงโดยประมาณเกณฑ์ทั่วไป หลายประการ ได้แก่: ^{[ 2 ]}${\displaystyle f}$${\displaystyle x}$${\displaystyle E^{d}}$${\displaystyle f(x)=x}$${\displaystyle E^{d}}$

• เกณฑ์ตกค้าง : เมื่อกำหนดพารามิเตอร์การประมาณค่าεจุดคงที่ตกค้างของ ε คือจุดใน' เช่นนั้นโดยที่ในที่นี้หมายถึงบรรทัดฐานสูงสุดนั่นคือพิกัดทั้งหมดของความแตกต่าง ควรมี ค่าไม่เกินε ^{[ 3 ] : 4} ${\displaystyle \varepsilon >0}$${\displaystyle f}$${\displaystyle x}$${\displaystyle E^{d}}$${\displaystyle |f(x)-x|\leq \varepsilon }$${\displaystyle |\cdot |}$${\displaystyle d}$${\displaystyle f(x)-x}$
• เกณฑ์สัมบูรณ์ : เมื่อกำหนดพารามิเตอร์การประมาณค่า δ แล้ว จุดตรึงสัมบูรณ์ δ ของคือจุดในที่ โดยที่เป็นจุดตรึงใดๆของ${\displaystyle \delta >0}$${\displaystyle f}$${\displaystyle x}$${\displaystyle E^{d}}$${\displaystyle |x-x_{0}|\leq \delta }$${\displaystyle x_{0}}$${\displaystyle f}$
• เกณฑ์เชิงสัมพัทธ์ : เมื่อกำหนดพารามิเตอร์การประมาณค่าδ แล้ว จุดตรึงเชิงสัมพัทธ์ δ ของคือจุดxในซึ่งโดยที่เป็นจุดตรึงใดๆของ${\displaystyle \delta >0}$${\displaystyle f}$${\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)}$

ฟังก์ชันต่อเนื่องแบบลิปชิตซ์ที่มีค่าคงที่เรียกว่าฟังก์ชันหดตัว (contractive function ) ถ้า; และเรียกว่า ฟังก์ชันหดตัวแบบ อ่อน (weakly-contractive function ) ถ้าทุกฟังก์ชันหดตัวที่ตรงตามเงื่อนไขของบราวเวอร์ (Brouwer's conditions) จะมี จุดตรึง (fixed point) เพียงจุด เดียวยิ่งไปกว่านั้น การคำนวณจุดตรึงสำหรับฟังก์ชันหดตัวนั้นง่ายกว่าสำหรับฟังก์ชันทั่วไป ${\displaystyle L}$${\displaystyle L<1}$${\displaystyle L\leq 1}$

อัลกอริทึมแรกสำหรับการคำนวณจุดคงที่คือ อัลกอริ ทึมการวนซ้ำจุดคงที่ของ Banach ทฤษฎีบทจุดคงที่ของ Banachบ่งชี้ว่า เมื่อใช้การวนซ้ำจุดคงที่กับแผนที่การหดตัว ข้อผิดพลาดหลังจากการวนซ้ำจะอยู่ในดังนั้น จำนวนการประเมินที่จำเป็นสำหรับจุดคงที่สัมพัทธ์ - จะประมาณSikorski และ Wozniakowski ^{[ 4 ]}แสดงให้เห็นว่าอัลกอริทึมของ Banach เหมาะสมที่สุดเมื่อมิติมีขนาดใหญ่ โดยเฉพาะอย่างยิ่ง เมื่อจำนวนการประเมินที่จำเป็นของ อัลกอริทึม ใดๆสำหรับจุดคงที่สัมพัทธ์ - จะมากกว่า 50% ของจำนวนการประเมินที่จำเป็นโดยอัลกอริทึมการวนซ้ำ โปรดทราบว่าเมื่อเข้าใกล้ 1 จำนวนการประเมินจะเข้าใกล้ค่าอนันต์ ไม่มีอัลกอริทึมจำกัดใดที่สามารถคำนวณจุดคงที่สัมบูรณ์ - สำหรับฟังก์ชันทั้งหมดที่มีได้^{[ 5 ]}${\displaystyle t}$${\displaystyle O(L^{t})}$${\displaystyle \delta }$${\displaystyle \log _{L}(\delta )=\log(\delta )/\log(L)=\log(1/\delta )/\log(1/L)}$${\displaystyle d\geq \log(1/\delta )/\log(1/L)}$${\displaystyle \delta }$${\displaystyle L}$${\displaystyle \delta }$${\displaystyle L=1}$

เมื่อ< 1 และd = 1 อัลกอริทึมที่เหมาะสมที่สุดคือ อัลกอริทึม Fixed Point Envelope (FPE) ของ Sikorski และ Wozniakowski ^{[ 4 ]}โดยจะค้นหาจุดคงที่สัมพัทธ์δ โดยใช้ การสอบถาม และจุดคงที่สัมบูรณ์δ โดยใช้ การสอบถาม ซึ่งเร็วกว่าอัลกอริทึมการวนซ้ำจุดคงที่^{[ 6 ]}${\displaystyle L}$${\displaystyle O(\log(1/\delta )+\log \log(1/(1-L)))}$${\displaystyle O(\log(1/\delta ))}$

เมื่อแต่ไม่ใหญ่เกินไป และอัลกอริทึมที่เหมาะสมที่สุดคืออัลกอริทึมวงรีภายใน (อิงตามวิธีการวงรี ) ^{[ 7 ]}โดยจะค้นหาจุดคงที่ε -residual โดยใช้ การประเมิน เมื่อจะค้นหาจุดคงที่ -absolute โดยใช้การประเมิน ${\displaystyle d>1}$${\displaystyle L\leq 1}$${\displaystyle O(d\cdot \log(1/\varepsilon ))}$${\displaystyle L<1}$${\displaystyle \delta }$${\displaystyle O(d\cdot [\log(1/\delta )+\log(1/(1-L))])}$

Shellman และ Sikorski ^{[ 8 ]}นำเสนออัลกอริทึมที่เรียกว่าBEFix (Bisection Envelope Fixed-point) สำหรับการคำนวณ จุดคงที่ ε -residual ของฟังก์ชันสองมิติที่มี ' โดยใช้เพียงการสอบถามเท่านั้น ต่อมาพวกเขา^{[ 9 ]}ได้นำเสนอการปรับปรุงที่เรียกว่าBEDFix (Bisection Envelope Deep-cut Fixed-point) ซึ่งมีการรับประกันกรณีที่เลวร้ายที่สุดเหมือนกัน แต่มีประสิทธิภาพเชิงประจักษ์ที่ดีกว่า เมื่อBEDFix ยังสามารถคำนวณจุดคงที่สัมบูรณ์โดยใช้การสอบถาม ได้อีกด้วย${\displaystyle L\leq 1}$${\displaystyle 2\lceil \log _{2}(1/\varepsilon )\rceil +1}$${\displaystyle L<1}$${\displaystyle \delta }$${\displaystyle O(\log(1/\varepsilon )+\log(1/(1-L)))}$

Shellman และ Sikorski ^{[ 2 ]}นำเสนออัลกอริทึมที่เรียกว่าPFixสำหรับการคำนวณจุดคงที่ε -residual ของ ฟังก์ชันมิติ d ที่มี L ≤ 1 โดยใช้การสอบถาม เมื่อ< 1, PFixสามารถดำเนินการได้ด้วยและในกรณีนั้น จะคำนวณจุดคงที่ δ-absolute โดยใช้การสอบถาม ซึ่งมีประสิทธิภาพมากกว่าอัลกอริทึมการวนซ้ำเมื่อใกล้เคียงกับ 1 อัลกอริทึมนี้เป็นแบบเรียกซ้ำ: มันจัดการ ฟังก์ชันมิติ dโดยการเรียกซ้ำบนฟังก์ชันมิติ ( d -1) ${\displaystyle O(\log ^{d}(1/\varepsilon ))}$${\displaystyle L}$${\displaystyle \varepsilon =(1-L)\cdot \delta }$${\displaystyle O(\log ^{d}(1/[(1-L)\เดลต้า ]))}$${\displaystyle L}$

เมื่อฟังก์ชันสามารถหาอนุพันธ์ได้ และอัลกอริทึมสามารถประเมินอนุพันธ์ของฟังก์ชันได้ (ไม่เฉพาะตัวมันเอง) สามารถใช้ วิธีของนิวตันได้ ซึ่งเร็วกว่ามาก^{[ 10 ] [ 11 ]}${\displaystyle f}$${\displaystyle f}$

สำหรับฟังก์ชันที่มีค่าคงที่ลิปชิตซ์> 1 การคำนวณจุดตรึงนั้นยากกว่ามาก ${\displaystyle L}$

สำหรับฟังก์ชัน 1 มิติ ( d = 1) สามารถค้นหาจุดคงที่สัมบูรณ์ได้โดยใช้การสอบถามโดยใช้วิธีการแบ่งครึ่ง : เริ่มต้นด้วยช่วง; ในแต่ละรอบ ให้เป็นจุดศูนย์กลางของช่วงปัจจุบัน และคำนวณ; ถ้าจากนั้นเรียกซ้ำในช่วงย่อยทางด้านขวาของ; มิฉะนั้น ให้เรียกซ้ำในช่วงทางด้านซ้ายของโปรดทราบว่าช่วงปัจจุบันจะมีจุดคงที่อยู่เสมอ ดังนั้นหลังจากการสอบถาม จุดใดๆ ในช่วงที่เหลือจะเป็นจุดคงที่สัมบูรณ์ของการตั้งค่าโดยที่เป็นค่าคงที่ลิปชิตซ์ จะให้จุดคงที่ตกค้างε โดยใช้ การสอบถาม^{[ 3 ]}${\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 ))}$

สำหรับฟังก์ชันในสองมิติขึ้นไป ปัญหาจะซับซ้อนมากขึ้น Shellman และ Sikorski ^{[ 2 ]}พิสูจน์ว่าสำหรับจำนวนเต็มd ≥ 2 และ> 1 การหาจุดคงที่สัมบูรณ์ δ ของ ฟังก์ชันลิปชิตซ์ dมิติอาจต้องใช้การประเมินค่าเป็นอนันต์ แนวคิดการพิสูจน์มีดังนี้ สำหรับจำนวนเต็มT > 1 ใดๆ และลำดับTของการสอบถามการประเมินค่าใดๆ (อาจปรับเปลี่ยนได้) เราสามารถสร้างฟังก์ชันสองฟังก์ชันที่ต่อเนื่องแบบลิปชิตซ์ด้วยค่าคงที่และให้คำตอบเดียวกันสำหรับการสอบถามทั้งหมดเหล่านี้ แต่ฟังก์ชันหนึ่งมีจุดคงที่ที่ไม่ซ้ำกันที่ ( x , 0) และอีกฟังก์ชันหนึ่งมีจุดคงที่ที่ไม่ซ้ำกันที่ ( x , 1) อัลกอริทึมใดๆ ที่ใช้ การประเมินค่า Tไม่สามารถแยกแยะความแตกต่างระหว่างฟังก์ชันเหล่านี้ได้ ดังนั้นจึงไม่สามารถหาจุดคงที่สัมบูรณ์ δ ได้ นี่เป็นจริงสำหรับจำนวนเต็มจำกัดT ใด ๆ ${\displaystyle L}$${\displaystyle L}$${\displaystyle L}$

มีการพัฒนาอัลกอริธึมหลายตัวโดยอาศัยการประเมินฟังก์ชันเพื่อค้นหาจุดตรึง ε -residual

อัลกอริทึมแรกในการประมาณจุดคงที่ของฟังก์ชันทั่วไปได้รับการพัฒนาโดยHerbert Scarfในปี 1967 ^{[ 12 ] [ 13 ]}อัลกอริทึมของ Scarf ค้นหา จุดคงที่ ε -residual โดยการค้นหา "เซตดั้งเดิม" ที่มีป้ายกำกับครบถ้วน ในการสร้างที่คล้ายกับทฤษฎีบทของ Sperner

อัลกอริทึมที่พัฒนาในภายหลังโดยHarold Kuhn ^{[ 14 ]}ใช้ซิมเพล็กซ์และพาร์ติชันซิมเพล็กซ์แทนเซตดั้งเดิม

^{Orin Harrison Merrill [ 15 ]}ได้พัฒนาแนวทางเชิงซิมพลิเชียลเพิ่มเติมโดยนำเสนออัลกอริทึมการเริ่มต้นใหม่

B. Curtis Eaves ^{[ 16 ]}นำเสนอวิธีโฮโมโทปีโดยอิงจากแนวคิดของโฮโมโทปี

เมื่อกำหนดฟังก์ชันfซึ่งเราต้องการหาจุดตรึง อัลกอริทึมจะทำงานโดยเริ่มจากฟังก์ชันเชิงเส้นที่ประมาณค่าfแล้วทำการเปลี่ยนรูปฟังก์ชันนั้นเข้าหาfโดยติดตามจุดตรึงไปด้วย

วิธีโฮโมโทปีถูกนำมาใช้ใน การ คำนวณสมดุลของตลาด^{[ 17 ]}

วิธีการนี้ได้รับการอธิบายเพิ่มเติมในหนังสือของ Michael Todd ^{[ 18 ]}ซึ่งสำรวจอัลกอริธึมต่างๆ ที่พัฒนาขึ้นจนถึงปี 1976

• David Gale ^{[ 19 ]}แสดงให้เห็นว่าการคำนวณจุดคงที่ของ ฟังก์ชัน nมิติ (บน ลูกบาศก์ dมิติหน่วย) เทียบเท่ากับการตัดสินว่าใครเป็นผู้ชนะใน เกม Hex dมิติ(เกมที่มี ผู้เล่น dคน โดยแต่ละคนต้องเชื่อมต่อหน้าตรงข้ามสองด้านของลูกบาศก์dมิติ) โดยกำหนดความแม่นยำที่ต้องการε
  • สร้างกระดานหกเหลี่ยมขนาดkdโดยที่แต่ละจุดยอดzสอดคล้องกับจุดz / kในลูกบาศก์หน่วยnมิติ${\displaystyle k>1/\varepsilon }$
  • คำนวณผลต่าง( z / k ) - z / k ; โปรดทราบว่าผลต่างเป็นเวกเตอร์n มิติ${\displaystyle f}$
  • กำหนดป้ายกำกับให้กับจุดยอดzด้วยป้ายกำกับในลำดับ 1, ..., d โดยที่ d แทนพิกัดที่ใหญ่ที่สุดในเวกเตอร์ผลต่าง
  • การติดป้ายกำกับที่ได้นั้นสอดคล้องกับความเป็นไปได้ในการเล่น เกม Hex มิติ dระหว่าง ผู้เล่น dคน เกมนี้ต้องมีผู้ชนะ และ Gale ได้นำเสนออัลกอริทึมสำหรับการสร้างเส้นทางสู่ชัยชนะ
  • ในเส้นทางที่ชนะ จะต้องมีจุดหนึ่งที่f _i ( z / k ) - z / kเป็นบวก และจุดที่อยู่ติดกันซึ่งf _i ( z / k ) - z / kเป็นลบ ซึ่งหมายความว่ามีจุดคงที่อยู่ระหว่างสองจุดนี้${\displaystyle f}$

ในกรณีที่เลวร้ายที่สุด จำนวนการประเมินฟังก์ชันที่จำเป็นสำหรับอัลกอริธึมทั้งหมดเหล่านี้จะเป็นแบบเลขชี้กำลังตามการแสดงค่าความแม่นยำในรูปแบบไบนารี นั่นคือ ใน. ${\displaystyle \โอเมก้า (1/\varepsilon )}$

Hirsch, Papadimitriouและ Vavasis พิสูจน์ว่า^{[ 3 ]} อัลกอริทึม ใดๆที่ใช้การประเมินฟังก์ชัน ซึ่งค้นหา จุดคงที่ ε -residual ของfต้องใช้การประเมินฟังก์ชัน โดยที่คือค่าคงที่ Lipschitz ของฟังก์ชัน(โปรดทราบว่า) กล่าวโดยละเอียด: ${\displaystyle \โอเมก้า (L'/\varepsilon )}$${\displaystyle L'}$${\displaystyle f(x)-x}$${\displaystyle L-1\leq L'\leq L+1}$

• สำหรับฟังก์ชัน 2 มิติ ( d = 2) พวกเขาได้พิสูจน์ขอบเขตที่แน่นหนา${\displaystyle \ทีต้า (L'/\varepsilon )}$
• สำหรับ d ≥ 3 ใดๆ การหาจุดตรึงตกค้างε ของ ฟังก์ชันมิติd ต้องใช้ การสอบถามและ การสอบถามซ้ำๆ${\displaystyle \โอเมก้า ((L'/\varepsilon )^{d-2})}$${\displaystyle O((L'/\varepsilon )^{d})}$

ผลลัพธ์หลังนี้ทำให้เกิดช่องว่างในเลขชี้กำลัง Chen และ Deng ^{[ 20 ]}ได้ปิดช่องว่างดังกล่าว พวกเขาพิสูจน์ว่าสำหรับd ≥ 2 และและจำนวนคำถามที่จำเป็นสำหรับการคำนวณจุดคงที่ε -residual อยู่ ใน ${\displaystyle 1/\varepsilon >4d}$${\displaystyle L'/\varepsilon >192d^{3}}$${\displaystyle \Theta ((L'/\varepsilon )^{d-1})}$

ฟังก์ชันแบบไม่ต่อเนื่อง (Discrete function ) คือฟังก์ชันที่กำหนดบนเซตย่อยของ( ตารางจำนวนเต็ม dมิติ) มีทฤษฎีบทจุดตรึงแบบไม่ต่อเนื่อง หลายทฤษฎี ที่ระบุเงื่อนไขที่ฟังก์ชันแบบไม่ต่อเนื่องมีจุดตรึง ตัวอย่างเช่นทฤษฎีบท Iimura-Murota-Tamuraกล่าวว่า (โดยเฉพาะอย่างยิ่ง) ถ้าเป็นฟังก์ชันจากเซตย่อยสี่เหลี่ยมผืนผ้าของไปยังตัวมันเอง และเป็น ฟังก์ชันรักษาทิศทางแบบไฮเปอร์คิวบิก (Hypercubic direction-preserving ) แล้วจะมีจุดตรึง ${\displaystyle \mathbb {Z} ^{d}}$${\displaystyle f}$${\displaystyle \mathbb {Z} ^{d}}$${\displaystyle f}$${\displaystyle f}$

ให้เป็นฟังก์ชันที่รักษาทิศทางจากลูกบาศก์จำนวนเต็มไปยังตัวมันเอง Chen และ Deng ^{[ 20 ]}พิสูจน์ว่า สำหรับd ≥ 2 และn > 48 d ใดๆ การคำนวณจุดคงที่ดังกล่าวต้องใช้ การประเมินฟังก์ชัน ${\displaystyle f}$${\displaystyle \{1,\dots ,n\}^{d}}$${\displaystyle \Theta (n^{d-1})}$

Chen และ Deng ^{[ 21 ]}กำหนดปัญหาจุดตรึงแบบไม่ต่อเนื่องที่แตกต่างกัน ซึ่งพวกเขาเรียกว่า2D-BROUWERโดยพิจารณาฟังก์ชันแบบไม่ต่อเนื่องบนโดยที่สำหรับทุกxบนตาราง( x ) - xจะเป็น (0, 1) หรือ (1, 0) หรือ (-1, -1) เป้าหมายคือการหาช่องสี่เหลี่ยมในตารางซึ่งมีป้ายกำกับทั้งสามปรากฏอยู่ ฟังก์ชันต้องแมปช่องสี่เหลี่ยมไปยังตัวมันเอง ดังนั้นมันต้องแมปเส้นx = 0 และy = 0 ไปยัง (0, 1) หรือ (1, 0) เส้นx = nไปยัง (-1, -1) หรือ (0, 1) และเส้นy = nไปยัง (-1, -1) หรือ (1, 0) ปัญหานี้สามารถลดลงเหลือ2D-SPERNER (การคำนวณสามเหลี่ยมที่มีป้ายกำกับครบถ้วนในการแบ่งสามเหลี่ยมที่ตรงตามเงื่อนไขของทฤษฎีบทของ Sperner ) และด้วยเหตุนี้จึงเป็นPPAD- complete นี่หมายความว่าการคำนวณจุดตรึงโดยประมาณนั้นเป็นปัญหา PPAD-complete แม้แต่สำหรับฟังก์ชันที่ง่ายมากก็ตาม ${\displaystyle f}$${\displaystyle \{0,\dots ,n\}^{2}}$${\displaystyle f}$${\displaystyle f}$${\displaystyle \{0,\dots ,n\}^{2}}$

กำหนดฟังก์ชันจากไปยังRรากของ g คือ จุดx ในที่( x ) =0 รากεของ g คือจุดxในที่${\displaystyle g}$${\displaystyle E^{d}}$${\displaystyle g}$${\displaystyle E^{d}}$${\displaystyle g}$${\displaystyle E^{d}}$${\displaystyle g(x)\leq \varepsilon }$

การคำนวณจุดตรึงเป็นกรณีพิเศษของการหาค่าราก: กำหนดฟังก์ชันบนให้กำหนดxเป็นจุดตรึงของก็ต่อเมื่อxเป็นรากของและxเป็นจุดตรึงตกค้างε ของ ก็ต่อเมื่อxเป็น ราก εของ ดังนั้น อัลกอริทึมการหาค่ารากใดๆ(อัลกอริทึมที่คำนวณรากโดยประมาณของฟังก์ชัน) สามารถใช้เพื่อหาจุดตรึงโดยประมาณได้ ${\displaystyle f}$${\displaystyle E^{d}}$${\displaystyle g(x):=|f(x)-x|}$${\displaystyle f}$${\displaystyle g}$${\displaystyle f}$${\displaystyle g}$

ตรงกันข้ามไม่เป็นความจริง: การหาค่ารากโดยประมาณของฟังก์ชันทั่วไปอาจยากกว่าการหาค่าจุดคงที่โดยประมาณ โดยเฉพาะอย่างยิ่ง Sikorski ^{[ 22 ]}พิสูจน์ว่าการหา ค่าราก εต้องใช้การประเมินฟังก์ชัน ซึ่งให้ขอบเขตล่างแบบเลขชี้กำลังแม้แต่สำหรับฟังก์ชันหนึ่งมิติ (ในทางตรงกันข้าม จุดคงที่ตกค้าง εของฟังก์ชันหนึ่งมิติสามารถหาได้โดยใช้การสอบถามโดยใช้วิธีการแบ่งครึ่ง ) นี่คือโครงร่างการพิสูจน์^{[ 3 ] : 35} สร้างฟังก์ชันที่ใหญ่กว่าε เล็กน้อย ทุกที่ยกเว้นในลูกบาศก์ขนาดเล็กบางลูกรอบจุดx ₀ บางจุด โดยที่x ₀เป็นรากเดียวของถ้ามีความต่อเนื่องแบบลิปชิตซ์ด้วยค่าคงที่ ลูกบาศก์รอบx ₀สามารถมีความยาวด้านได้อัลกอริทึมใด ๆ ที่หา ค่าราก εของต้องตรวจสอบชุดของลูกบาศก์ที่ครอบคลุมทั้งหมดจำนวนลูกบาศก์ดังกล่าวมีอย่างน้อย ${\displaystyle \Omega (1/\varepsilon ^{d})}$${\displaystyle O(\log(1/\varepsilon ))}$${\displaystyle g}$${\displaystyle E^{d}}$${\displaystyle g}$${\displaystyle g}$${\displaystyle L}$${\displaystyle \varepsilon /L}$${\displaystyle g}$${\displaystyle E^{d}}$${\displaystyle (L/\varepsilon )^{d}}$

อย่างไรก็ตาม มีฟังก์ชันบางประเภทที่การหาค่ารากโดยประมาณเทียบเท่ากับการหาค่าจุดตรึงโดยประมาณ ตัวอย่างหนึ่ง^{[ 20 ]}คือคลาสของฟังก์ชันที่แมป ไปยังตัวมันเอง (นั่นคือ: อยู่ในสำหรับทุก x ใน) ทั้งนี้เพราะสำหรับทุกฟังก์ชันดังกล่าว ฟังก์ชันจะตรงตามเงื่อนไขของทฤษฎีบทจุดตรึงของ Brouwer Xเป็นจุดตรึงของ ก็ต่อเมื่อxเป็นรากของและxเป็นจุดตรึงε -residual ของ ก็ต่อเมื่อxเป็น ราก εของChen และ Deng ^{[ 20 ]}แสดงให้เห็นว่ารูปแบบดิสครีตของปัญหาเหล่านี้เทียบเท่ากันในเชิงการคำนวณ: ทั้งสองปัญหาต้องใช้ การประเมินฟังก์ชัน ${\displaystyle g}$${\displaystyle g(x)+x}$${\displaystyle E^{d}}$${\displaystyle g(x)+x}$${\displaystyle E^{d}}$${\displaystyle E^{d}}$${\displaystyle f(x):=g(x)+x}$${\displaystyle f}$${\displaystyle g}$${\displaystyle f}$${\displaystyle g}$${\displaystyle \Theta (n^{d-1})}$

Roughgarden และ Weinstein ^{[ 23 ]}ศึกษาความซับซ้อนของการสื่อสารในการคำนวณจุดคงที่โดยประมาณ ในแบบจำลองของพวกเขามีตัวแทนสองตัว ตัวหนึ่งรู้จักฟังก์ชันและอีกตัวหนึ่งรู้จักฟังก์ชันทั้งสองฟังก์ชันมีความต่อเนื่องแบบ Lipschitz และตรงตามเงื่อนไขของ Brouwer เป้าหมายคือการคำนวณจุดคงที่โดยประมาณของฟังก์ชันประกอบพวกเขาแสดงให้เห็นว่าความซับซ้อนของการสื่อสารแบบกำหนดได้อยู่ใน ${\displaystyle f}$${\displaystyle g}$${\displaystyle g\circ f}$${\displaystyle \Omega (2^{d})}$

• Yannakakis, Mihalis (พฤษภาคม 2009). "สมดุล จุดคงที่ และคลาสความซับซ้อน" . Computer Science Review . 3 (2): 71– 85. arXiv : 0802.2831 . doi : 10.1016/j.cosrev.2009.03.004 .