Content deleted Content added
Erel Segal (talk | contribs) |
Erel Segal (talk | contribs) |
||
Line 6:
A '''fixed point''' of ''f'' is a point ''x'' in ''E<sup>d</sup>'' such that ''f''(''x'')=''x''. Given an approximation parameter <math>\varepsilon>0</math> , An '''{{mvar|ε}}-fixed-point of''' '''''f''''' is a point ''x'' in ''E<sup>d</sup>'' such that <math>|f(x)-x|\leq \varepsilon</math>, where here ''|.|'' denotes the [[maximum norm]]. That is, all ''d'' coordinates of the difference <math>f(x)-x</math> should be at most {{mvar|ε}}.<ref name=":0" />{{Rp|page=4}}
An alternative possible definition of an approximate fixed point uses an approximation parameter <math>\delta>0</math>. A '''δ-near fixed-point of''' '''''f''''' is a point ''x'' in ''E<sup>d</sup>'' such that <math>|x-x_0|\leq \delta</math>, where <math>x_0</math> is any fixed-point of ''f'' (this criterion is also called the '''absolute criterion''').<ref name=":3">{{Cite journal |last=Shellman |first=Spencer |last2=Sikorski |first2=K. |date=2003-12-01 |title=A recursive algorithm for the infinity-norm fixed point problem |url=https://www.sciencedirect.com/science/article/pii/S0885064X03000682 |journal=Journal of Complexity |language=en |volume=19 |issue=6 |pages=799–834 |doi=10.1016/j.jco.2003.06.001 |issn=0885-064X}}</ref> Note that, if ''f'' is Lipschitz-continuous with constant ''L'', then <math>|x-x_0|\leq \delta</math> implies <math>|f(x)-f(x_0)|\leq L\cdot \delta</math>. Since <math>x_0</math> is a fixed-point of ''f'', this implies <math>|f(x)-x_0|\leq L\cdot \delta</math>, so <math>|f(x)-x|\leq (L+1)\cdot \delta</math>. Therefore, a δ-near fixed-point is also an {{mvar|ε}}-fixed-point with <math>\varepsilon = (L+1)\cdot \delta</math>. {{Under construction|placedby=Erel Segal}}
== Algorithms based on function evaluations ==
Line 45:
The special case in which the Lipschitz constant is exactly 1 is not covered by the above results, but there are specialized algorithms for this case:
* Shellman and Sikorski<ref>{{Cite journal |last=Shellman |first=Spencer |last2=Sikorski |first2=K. |date=2002-06-01 |title=A Two-Dimensional Bisection Envelope Algorithm for Fixed Points |url=https://www.sciencedirect.com/science/article/pii/S0885064X01906259 |journal=Journal of Complexity |language=en |volume=18 |issue=2 |pages=641–659 |doi=10.1006/jcom.2001.0625 |issn=0885-064X}}</ref> presented an algorithm called BEFix (Bisection Envelope Fixed-point) for computing an {{mvar|ε}}-fixed-point of a two-dimensional function with Lipschitz constant ''L''=1, using only <math>2 \lceil\log_2(1/\varepsilon)\rceil+1</math> queries. They later<ref>{{Cite journal |last=Shellman |first=Spencer |last2=Sikorski |first2=K. |date=2003-09-01 |title=Algorithm 825: A deep-cut bisection envelope algorithm for fixed points |url=https://doi.org/10.1145/838250.838255 |journal=ACM Transactions on Mathematical Software |volume=29 |issue=3 |pages=309–325 |doi=10.1145/838250.838255 |issn=0098-3500}}</ref> presented an improvement called BEDFix (Bisection Envelope Deep-cut Fixed-point), with the same worst-case guarantee but better empirical performance. When ''L''<1, BEDFix can also compute a δ-near fixed-point, using <math>2 \lceil\log_2(1/((1-L)\delta)\rceil+1</math> queries (that is: a similar complexity but with <math>\varepsilon = (1-L)\cdot \delta</math>).
* Shellman and Sikorski<ref name=":3" />
== Discrete fixed-point computation ==
| |||