Fixed-point computation: Difference between revisions

Content deleted Content added
T6283 (talk | contribs)
m Grammar fixes
T6283 (talk | contribs)
m Fix math notation
Line 9:
A '''fixed point''' of ''f'' is a point ''x'' in ''E<sup>d</sup>'' such that ''f''(''x'') = ''x''. By the [[Brouwer fixed-point theorem]], any continuous function from ''E<sup>d</sup>'' 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. Several common criteria are:<ref name=":3">{{cite journal |last1=Shellman |first1=Spencer |last2=Sikorski |first2=K. |title=A recursive algorithm for the infinity-norm fixed point problem |journal=Journal of Complexity |date=December 2003 |volume=19 |issue=6 |pages=799–834 |doi=10.1016/j.jco.2003.06.001 |doi-access=free }}</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<sup>d</sup>'' such that <math>|f(x)-x|\leq \varepsilon</math>, where here ''<math>|.\cdot|''</math> 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}}
* The '''absolute criterion''': given an approximation parameter <math>\delta>0</math>, A '''δ-absolute 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.''
* The '''relative criterion''': given an approximation parameter <math>\delta>0</math>, A '''δ-relative fixed-point of''' '''''f''''' is a point ''x'' in ''E<sup>d</sup>'' such that <math>|x-x_0|/|x_0|\leq \delta</math>, where <math>x_0</math> is any fixed-point of ''f.''