Fixed-point computation: Difference between revisions

Revision as of 08:58, 16 April 2023

Revision as of 08:59, 16 April 2023

Line 4:

The unit interval is denoted by ''E'' := [0,1], and the unit [[N-cube|''d''-dimensional cube]] is denoted by ''E^d''. A [[continuous function]] ''f'' is defined on ''E^d'' (from ''E^d'' to itself)''.'' Often, it is assumed that ''f'' is not only continuous but also [[Lipschitz continuous]], that is, for some constant ''L'', <math>|f(x)-f(y)| \leq L\cdot |x-y|</math> for all ''x,y'' in ''E^d''.

A '''fixed point''' of ''f'' is a point ''x'' in ''E^d'' such that ''f''(''x'')=''x''. ForBy the [[Brouwer fixed-point theorem]], any contiuous function from ''E^d'' to itself has a fixed point. But for general functions, it is impossible to compute a fixed point precisely, since it can be an arbitrary real number. Fixed-point computation algorithms look for ''approximate'' fixed points. There are several criteria for an approximate fixed point. Two of the more common criteria are:<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>

* The '''residual criterion''': given an approximation parameter <math>\varepsilon>0</math> , An '''{{mvar|ε}}-residual fixed-point of''' '''''f''''' is a point ''x'' in ''E^d'' 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}}