Fixed-point computation: Difference between revisions

Revision as of 20:27, 12 August 2023

Revision as of 21:59, 14 December 2023

Line 50:

* Developing the simplicial approach further, Orin Harrison Merrill<ref>{{cite thesis |last1=Merrill |first1=Orin Harrison |date=1972 |title=Applications and Extensions of an Algorithm that Computes Fixed Points of Certain Upper Semi-continuous Point to Set Mappings |id={{NAID|10006142329}} |oclc=570461463 |url=https://www.proquest.com/openview/9bd010ff744833cb3a23ef521046adcb/1 }}</ref> presented the ''restart algorithm''.

* B. Curtis Eaves<ref>{{cite journal |last1=Eaves |first1=B. Curtis |title=Homotopies for computation of fixed points |journal=Mathematical Programming |date=December 1972 |volume=3-3 |issue=1 |pages=1–22 |doi=10.1007/BF01584975 |s2cid=39504380 }}</ref> presented the ''[[homotopy]] algorithm''. The algorithm works by starting with an affine function that approximates ''f'', and deforming it towards ''f'', while following the fixed point''.'' A book by Michael Todd<ref name=":1" /> surveys various algorithms developed until 1976.

* [[David Gale]]<ref>{{cite journal |first1=David |last1=Gale |year=1979 |title=The Game of Hex and Brouwer Fixed-Point Theorem |journal=The American Mathematical Monthly |volume=86 |issue=10 |pages=818–827 |doi=10.2307/2320146 |jstor=2320146 }}</ref> showed that computing a fixed point of an ''n''-dimensional function (on the unit ''d''-dimensional cube) is equivalent to deciding who is the winner in ana ''d''-dimensional game of [[Hex (board game)|Hex]] (a game with ''d'' players, each of whom needs to connect two opposite faces of an ''d''-cube). Given the desired accuracy ''{{mvar|ε}}''

** Construct a Hex board of size ''kd'', where <math>k > 1/\varepsilon</math>. Each vertex ''z'' corresponds to a point ''z''/''k'' in the unit ''n''-cube.

** Compute the difference ''f''(''z''/''k'') - ''z''/''k''; note that the difference is an ''n''-vector.