Open main menu
Home
Random
Recent changes
Special pages
Community portal
Preferences
About Wikipedia
Disclaimers
Incubator escapee wiki
Search
User menu
Talk
Dark mode
Contributions
Create account
Log in
Editing
Fixed point (mathematics)
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
{{Short description|Element mapped to itself by a mathematical function}} {{hatnote|1=Fixed points in mathematics are not to be confused with [[Fixed point (disambiguation)|other uses of "fixed point"]], or [[stationary point]]s where <math> f'(x) = 0</math>.}} [[File:Fixpoint012 svg.svg|thumb|300px|The function <math>f(x)=x^3 - 3x^2 + 3x</math> (shown in red) has the fixed points 0, 1, and 2.]] In [[mathematics]], a '''fixed point''' (sometimes shortened to '''fixpoint'''), also known as an '''invariant point''', is a value that does not change under a given [[transformation (mathematics)|transformation]]. Specifically, for [[function (mathematics)|functions]], a fixed point is an element that is mapped to itself by the function. Any set of fixed points of a transformation is also an [[invariant set]]. == Fixed point of a function == Formally, {{mvar|c}} is a fixed point of a function {{mvar|f}} if {{mvar|c}} belongs to both the [[domain of a function|domain]] and the [[codomain]] of {{mvar|f}}, and {{math|1=''f''(''c'') = ''c''}}. In particular, {{mvar|f}} cannot have any fixed point if its domain is disjoint from its codomain. If {{math|''f''}} is defined on the [[real number]]s, it corresponds, in graphical terms, to a [[curve]] in the [[Euclidean plane]], and each fixed-point {{math|''c''}} corresponds to an intersection of the curve with the line {{math|1=''y'' = ''x''}}, cf. picture. For example, if {{math|''f''}} is defined on the [[real number]]s by <math> f(x) = x^2 - 3 x + 4,</math> then 2 is a fixed point of {{math|''f''}}, because {{math|1=''f''(2) = 2}}. Not all functions have fixed points: for example, {{math|1=''f''(''x'') = ''x'' + 1}} has no fixed points because {{math|''x'' + 1}} is never equal to {{math|''x''}} for any real number. == Fixed point iteration == {{Main|Fixed-point iteration}} In [[numerical analysis]], ''fixed-point iteration'' is a method of computing fixed points of a function. Specifically, given a function <math>f</math> with the same domain and codomain, a point <math>x_0</math> in the domain of <math>f</math>, the fixed-point iteration is <math display="block">x_{n+1}=f(x_n), \, n=0, 1, 2, \dots</math> which gives rise to the [[sequence]] <math>x_0, x_1, x_2, \dots</math> of [[iterated function]] applications <math>x_0, f(x_0), f(f(x_0)), \dots</math> which is hoped to [[limit (mathematics)|converge]] to a point <math>x</math>. If <math>f</math> is continuous, then one can prove that the obtained <math>x</math> is a fixed point of <math>f</math>. The notions of attracting fixed points, repelling fixed points, and [[periodic point]]s are defined with respect to fixed-point iteration. ==Fixed-point theorems== {{Main|Fixed-point theorems}} A fixed-point theorem is a result saying that at least one fixed point exists, under some general condition.<ref>{{cite book | editor = Brown, R. F. | title = Fixed Point Theory and Its Applications | year = 1988 | publisher = American Mathematical Society | isbn = 0-8218-5080-6 }} </ref> For example, the [[Banach fixed-point theorem]] (1922) gives a general criterion guaranteeing that, if it is satisfied, [[fixed-point iteration]] will always converge to a fixed point. The [[Brouwer fixed-point theorem]] (1911) says that any [[continuous function]] from the closed [[unit ball]] in ''n''-dimensional [[Euclidean space]] to itself must have a fixed point, but it doesn't describe how to find the fixed point. The [[Lefschetz fixed-point theorem]] (and the [[Nielsen theory|Nielsen fixed-point theorem]]) from [[algebraic topology]] give a way to count fixed points. == Fixed point of a group action == In [[algebra]], for a group ''G'' acting on a set ''X'' with a [[group action]] <math>\cdot</math>, ''x'' in ''X'' is said to be a fixed point of ''g'' if <math>g \cdot x = x</math>. The [[fixed-point subgroup]] <math>G^f</math> of an [[automorphism]] ''f'' of a [[group (mathematics)|group]] ''G'' is the [[subgroup]] of ''G'': <math display="block">G^f = \{ g \in G \mid f(g) = g \}.</math> Similarly, the [[fixed-point subring]] <math>R^f</math> of an [[automorphism]] ''f'' of a [[ring (mathematics)|ring]] ''R'' is the [[subring]] of the fixed points of ''f'', that is, <math display="block">R^f = \{ r \in R \mid f(r) = r \}.</math> In [[Galois theory]], the set of the fixed points of a set of [[field automorphism]]s is a [[field (mathematics)|field]] called the [[fixed field]] of the set of automorphisms. ==Topological fixed point property== {{main article|Fixed-point property}} A [[topological space]] <math>X</math> is said to have the [[fixed point property]] (FPP) if for any [[continuous function]] :<math>f\colon X \to X</math> there exists <math>x \in X</math> such that <math>f(x)=x</math>. The FPP is a [[topological invariant]], i.e., it is preserved by any [[homeomorphism]]. The FPP is also preserved by any [[Retraction (topology)|retraction]]. According to the [[Brouwer fixed-point theorem]], every [[compact space|compact]] and [[convex set|convex]] [[subset]] of a [[Euclidean space]] has the FPP. Compactness alone does not imply the FPP, and convexity is not even a topological property, so it makes sense to ask how to topologically characterize the FPP. In 1932 [[Karol Borsuk|Borsuk]] asked whether compactness together with [[contractible space|contractibility]] could be a necessary and sufficient condition for the FPP to hold. The problem was open for 20 years until the conjecture was disproved by Kinoshita, who found an example of a compact contractible space without the FPP.<ref>{{cite journal |last=Kinoshita |first=Shin'ichi |year=1953 |title=On Some Contractible Continua without Fixed Point Property |journal=[[Fundamenta Mathematicae|Fund. Math.]] |volume=40 |issue=1 |pages=96–98 |doi=10.4064/fm-40-1-96-98 |issn=0016-2736 |doi-access=free}}</ref> ==Fixed points of partial orders == In [[domain theory]], the notion and terminology of fixed points is generalized to a [[partial order]]. Let ≤ be a partial order over a set ''X'' and let ''f'': ''X'' → ''X'' be a function over ''X''. Then a '''prefixed point''' (also spelled '''pre-fixed point''', sometimes shortened to '''prefixpoint''' or '''pre-fixpoint'''){{citation needed|reason=Give a source for each of the spellings.|date=October 2022}} of ''f'' is any ''p'' such that ''f''(''p'') ≤ ''p''. Analogously, a ''postfixed point'' of ''f'' is any ''p'' such that ''p'' ≤ ''f''(''p'').<ref name="SmythPlotkin1982">{{cite conference |last1=Smyth |first1=Michael B. |last2=Plotkin |first2=Gordon D. |date=1982 |title=The Category-Theoretic Solution of Recursive Domain Equations |url=https://homepages.inf.ed.ac.uk/gdp/publications/Category_Theoretic_Solution.pdf |publisher=SIAM Journal of Computing (volume 11) |pages=761–783 |doi=10.1137/0211062 |book-title=Proceedings, 18th IEEE Symposium on Foundations of Computer Science}}</ref> The opposite usage occasionally appears.<ref name="CousotCousot1979">{{cite journal |author1=Patrick Cousot |author2=Radhia Cousot |year=1979 |title=Constructive Versions of Tarski's Fixed Point Theorems |url=http://www.di.ens.fr/~cousot/COUSOTpapers/publications.www/CousotCousot-PacJMath-82-1-1979.pdf |journal=[[Pacific Journal of Mathematics]] |volume=82 |issue=1 |pages=43–57 |doi=10.2140/pjm.1979.82.43}}</ref> Malkis justifies the definition presented here as follows: "since ''f'' is {{em|before}} the inequality sign in the term ''f''(''x'') ≤ ''x'', such ''x'' is called a {{em|pre}}fix point."<ref>{{cite book |last1=Malkis |first1=Alexander |date=2015 |chapter=Multithreaded-Cartesian Abstract Interpretation of Multithreaded Recursive Programs Is Polynomial |chapter-url=https://www.sec.in.tum.de/~malkis/Malkis-MultCartAbstIntOfMultRecProgIsPoly_techrep.pdf |title=Reachability Problems |series=Lecture Notes in Computer Science |volume=9328 |pages=114–127 |doi=10.1007/978-3-319-24537-9_11 |isbn=978-3-319-24536-2 |s2cid=17640585 |archive-url=https://web.archive.org/web/20220810075519/https://www.sec.in.tum.de/~malkis/Malkis-MultCartAbstIntOfMultRecProgIsPoly_techrep.pdf |archive-date=2022-08-10}}</ref> A fixed point is a point that is both a prefixpoint and a postfixpoint. Prefixpoints and postfixpoints have applications in [[theoretical computer science]].<ref>Yde Venema (2008) [http://staff.science.uva.nl/~yde/teaching/ml/mu/mu2008.pdf Lectures on the Modal μ-calculus] {{webarchive|url=https://web.archive.org/web/20120321162526/http://staff.science.uva.nl/~yde/teaching/ml/mu/mu2008.pdf|date=March 21, 2012}}</ref> === Least fixed point === {{Main|Least fixed point}} In [[order theory]], the [[least fixed point]] of a [[function (mathematics)|function]] from a [[partially ordered set]] (poset) to itself is the fixed point which is less than each other fixed point, according to the order of the poset. A function need not have a least fixed point, but if it does then the least fixed point is unique. One way to express the [[Knaster–Tarski theorem]] is to say that a [[monotone function]] on a [[complete lattice]] has a [[least fixed point]] that coincides with its least prefixpoint (and similarly its greatest fixed point coincides with its greatest postfixpoint).<ref>Yde Venema (2008) [http://staff.science.uva.nl/~yde/teaching/ml/mu/mu2008.pdf Lectures on the Modal μ-calculus] {{webarchive|url=https://web.archive.org/web/20120321162526/http://staff.science.uva.nl/~yde/teaching/ml/mu/mu2008.pdf|date=March 21, 2012}}</ref> ==Fixed-point combinator== {{Main|Fixed point combinator}} In [[combinatory logic]] for [[computer science]], a fixed-point combinator is a [[higher-order function]] <math>\mathsf{fix}</math> that returns a fixed point of its argument function, if one exists. Formally, if the function ''f'' has one or more fixed points, then : <math>\operatorname{\mathsf{fix}}f = f(\operatorname{\mathsf{fix}}f).</math> ==Fixed-point logics== {{Main|Fixed-point logic}} In [[mathematical logic]], fixed-point logics are extensions of classical predicate logic that have been introduced to express recursion. Their development has been motivated by [[descriptive complexity theory]] and their relationship to [[database query language]]s, in particular to [[Datalog]]. ==Applications== {{more citations needed section|date=July 2018}} In many fields, equilibria or [[stability theory|stability]] are fundamental concepts that can be described in terms of fixed points. Some examples follow. * In [[projective geometry]], a fixed point of a [[projectivity]] has been called a '''double point'''.<ref>{{cite book |author-link=H. S. M. Coxeter |first=H. S. M. |last=Coxeter |year=1942 |title=Non-Euclidean Geometry |page=36 |publisher=[[University of Toronto Press]] }}</ref><ref>[[G. B. Halsted]] (1906) ''Synthetic Projective Geometry'', page 27</ref> * In [[economics]], a [[Nash equilibrium]] of a [[game theory|game]] is a fixed point of the game's [[best response|best response correspondence]]. [[John Forbes Nash Jr.|John Nash]] exploited the [[Kakutani fixed-point theorem]] for his seminal paper that won him the Nobel prize in economics. * In [[physics]], more precisely in the [[phase transition|theory of phase transitions]], ''linearization'' near an ''unstable'' fixed point has led to [[Kenneth G. Wilson|Wilson]]'s Nobel prize-winning work inventing the [[renormalization group]], and to the mathematical explanation of the term "[[critical phenomenon]]."<ref>{{Cite journal|doi = 10.1103/PhysRevB.4.3174|title = Renormalization Group and Critical Phenomena. I. Renormalization Group and the Kadanoff Scaling Picture|year = 1971|last1 = Wilson|first1 = Kenneth G.|journal = Physical Review B|volume = 4|issue = 9|pages = 3174–3183|bibcode = 1971PhRvB...4.3174W|doi-access = free}}</ref><ref>{{Cite journal|doi = 10.1103/PhysRevB.4.3184|title = Renormalization Group and Critical Phenomena. II. Phase-Space Cell Analysis of Critical Behavior|year = 1971|last1 = Wilson|first1 = Kenneth G.|journal = Physical Review B|volume = 4|issue = 9|pages = 3184–3205|bibcode = 1971PhRvB...4.3184W|doi-access = free}}</ref> * [[Programming language]] [[compilers]] use fixed point computations for program analysis, for example in [[data-flow analysis]], which is often required for code [[Optimization (computer science)|optimization]]. They are also the core concept used by the generic program analysis method [[abstract interpretation]].<ref>{{Cite web|url=https://www.di.ens.fr/~cousot/COUSOTpapers/POPL77.shtml|title = P. Cousot & R. Cousot, Abstract interpretation: A unified lattice model for static analysis of programs by construction or approximation of fixpoints}}</ref> * In [[type theory]], the [[fixed-point combinator]] allows definition of recursive functions in the [[untyped lambda calculus]]. * The vector of [[PageRank]] values of all web pages is the fixed point of a [[linear transformation]] derived from the [[World Wide Web]]'s link structure. * The stationary distribution of a [[Markov chain]] is the fixed point of the one step transition probability function. * Fixed points are used to finding formulas for [[Iterated function|iterated functions]]. ==See also== {{Div col|colwidth=25em}} *[[Cycles and fixed points]] of permutations *[[Eigenvector]] *[[equilibrium point|Equilibrium]] *[[Möbius transformation#Fixed points|Fixed points of a Möbius transformation]] *[[Idempotence]] *[[Infinite compositions of analytic functions]] *[[Invariant (mathematics)]] {{div col end}} ==Notes== {{reflist}} ==External links== * {{cite journal | url=http://ijpam.eu/contents/2012-78-3/7/7.pdf | author=Yutaka Nishiyama | title=An Elegant Solution for Drawing a Fixed Point | journal=International Journal of Pure and Applied Mathematics | volume=78 | number=3 | pages=363–377 | date=2012 }} [[Category:Fixed points (mathematics)| ]]
Edit summary
(Briefly describe your changes)
By publishing changes, you agree to the
Terms of Use
, and you irrevocably agree to release your contribution under the
CC BY-SA 4.0 License
and the
GFDL
. You agree that a hyperlink or URL is sufficient attribution under the Creative Commons license.
Cancel
Editing help
(opens in new window)
Pages transcluded onto the current version of this page
(
help
)
:
Template:Citation needed
(
edit
)
Template:Cite book
(
edit
)
Template:Cite conference
(
edit
)
Template:Cite journal
(
edit
)
Template:Cite web
(
edit
)
Template:Div col
(
edit
)
Template:Div col end
(
edit
)
Template:Em
(
edit
)
Template:Hatnote
(
edit
)
Template:Main
(
edit
)
Template:Main article
(
edit
)
Template:Math
(
edit
)
Template:More citations needed section
(
edit
)
Template:Mvar
(
edit
)
Template:Reflist
(
edit
)
Template:Short description
(
edit
)
Template:Webarchive
(
edit
)