Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Fixed point (mathematics)
open-in-new
<h2 id="fixed-point-of-a-function">Fixed point of a function</h2> <p>Formally, c is a fixed point of a function f if c belongs to both the <a href="/facts/Domain_of_a_function/FQvoeUpX">domain</a> and the <a href="/facts/Codomain/MGc43nwQ">codomain</a> of f, and <i>f</i>(<i>c</i>) = <i>c</i>. In particular, f cannot have any fixed point if its domain is disjoint from its codomain. If <i>f</i> is defined on the <a href="/facts/Real_number/R02gw5Pb">real numbers</a>, it corresponds, in graphical terms, to a <a href="/facts/Curve/xBQ0pTBW">curve</a> in the <a href="/facts/Euclidean_plane/tAUtRFcn">Euclidean plane</a>, and each fixed-point <i>c</i> corresponds to an intersection of the curve with the line <i>y</i> = <i>x</i>, cf. picture. </p><p>For example, if <i>f</i> is defined on the <a href="/facts/Real_number/R02gw5Pb">real numbers</a> by f ( x ) = x 2 − 3 x + 4 , {\displaystyle f(x)=x^{2}-3x+4,} then 2 is a fixed point of <i>f</i>, because <i>f</i>(2) = 2. </p><p>Not all functions have fixed points: for example, <i>f</i>(<i>x</i>) = <i>x</i> + 1 has no fixed points because <i>x</i> + 1 is never equal to <i>x</i> for any real number. If a linear equation is not of the form <i>x</i> + <i>n</i>, it has one fixed point. </p> <h2 id="fixed-point-iteration">Fixed point iteration</h2> <p class="note">Main article: <a href="/facts/Fixed-point_iteration/05dQGazd">Fixed-point iteration</a></p> <p>In <a href="/facts/Numerical_analysis/QT9cYa9z">numerical analysis</a>, <i>fixed-point iteration</i> is a method of computing fixed points of a function. Specifically, given a function f {\displaystyle f} with the same domain and codomain, a point x 0 {\displaystyle x_{0}} in the domain of f {\displaystyle f} , the fixed-point iteration is </p><p> x n + 1 = f ( x n ) , n = 0 , 1 , 2 , … {\displaystyle x_{n+1}=f(x_{n}),\,n=0,1,2,\dots } </p><p>which gives rise to the <a href="/facts/Sequence/gV2S4uqp">sequence</a> x 0 , x 1 , x 2 , … {\displaystyle x_{0},x_{1},x_{2},\dots } of <a href="/facts/Iterated_function/Vzsx64An">iterated function</a> applications x 0 , f ( x 0 ) , f ( f ( x 0 ) ) , … {\displaystyle x_{0},f(x_{0}),f(f(x_{0})),\dots } which is hoped to <a href="/facts/Limit_(mathematics)/j8JBhj4e">converge</a> to a point x {\displaystyle x} . If f {\displaystyle f} is continuous, then one can prove that the obtained x {\displaystyle x} is a fixed point of f {\displaystyle f} . </p><p>The notions of attracting fixed points, repelling fixed points, and <a href="/facts/Periodic_point/9tRHxcrn">periodic points</a> are defined with respect to fixed-point iteration. </p> <h2 id="fixed-point-theorems">Fixed-point theorems</h2> <p class="note">Main article: <a href="/facts/Fixed-point_theorems/Jvkz4SUu">Fixed-point theorems</a></p> <p>A fixed-point theorem is a result saying that at least one fixed point exists, under some general condition.<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a> </p><p>For example, the <a href="/facts/Banach_fixed-point_theorem/TRygeoCP">Banach fixed-point theorem</a> (1922) gives a general criterion guaranteeing that, if it is satisfied, <a href="/facts/Fixed-point_iteration/05dQGazd">fixed-point iteration</a> will always converge to a fixed point. </p><p>The <a href="/facts/Brouwer_fixed-point_theorem/xP2p03lQ">Brouwer fixed-point theorem</a> (1911) says that any <a href="/facts/Continuous_function/sKbl02pB">continuous function</a> from the closed <a href="/facts/Unit_ball/5UeoTcug">unit ball</a> in <i>n</i>-dimensional <a href="/facts/Euclidean_space/R2UbzmzM">Euclidean space</a> to itself must have a fixed point, but it doesn't describe how to find the fixed point. </p><p>The <a href="/facts/Lefschetz_fixed-point_theorem/TEjN2DQ8">Lefschetz fixed-point theorem</a> (and the <a href="/facts/Nielsen_theory/1VvcXSSb">Nielsen fixed-point theorem</a>) from <a href="/facts/Algebraic_topology/2wA8yrjT">algebraic topology</a> give a way to count fixed points. </p> <h2 id="fixed-point-of-a-group-action">Fixed point of a group action</h2> <p>In <a href="/facts/Algebra/nMdqczjo">algebra</a>, for a group <i>G</i> acting on a set <i>X</i> with a <a href="/facts/Group_action/Vh9VtUUw">group action</a> ⋅ {\displaystyle \cdot } , <i>x</i> in <i>X</i> is said to be a fixed point of <i>g</i> if g ⋅ x = x {\displaystyle g\cdot x=x} . </p><p>The <a href="/facts/Fixed-point_subgroup/tekvHaSE">fixed-point subgroup</a> G f {\displaystyle G^{f}} of an <a href="/facts/Automorphism/WnyxNFkQ">automorphism</a> <i>f</i> of a <a href="/facts/Group_(mathematics)/IQTYqINt">group</a> <i>G</i> is the <a href="/facts/Subgroup/r91mBgpa">subgroup</a> of <i>G</i>: G f = { g ∈ G ∣ f ( g ) = g } . {\displaystyle G^{f}=\{g\in G\mid f(g)=g\}.} </p><p>Similarly, the <a href="/facts/Fixed-point_subring/yEXwojME">fixed-point subring</a> R f {\displaystyle R^{f}} of an <a href="/facts/Automorphism/WnyxNFkQ">automorphism</a> <i>f</i> of a <a href="/facts/Ring_(mathematics)/JnCUXz63">ring</a> <i>R</i> is the <a href="/facts/Subring/M0perybt">subring</a> of the fixed points of <i>f</i>, that is, R f = { r ∈ R ∣ f ( r ) = r } . {\displaystyle R^{f}=\{r\in R\mid f(r)=r\}.} </p><p>In <a href="/facts/Galois_theory/54wscJfj">Galois theory</a>, the set of the fixed points of a set of <a href="/facts/Field_automorphism/WnyxNFkQ">field automorphisms</a> is a <a href="/facts/Field_(mathematics)/xAjAS4ko">field</a> called the <a href="/facts/Fixed_field/yEXwojME">fixed field</a> of the set of automorphisms. </p> <h2 id="topological-fixed-point-property">Topological fixed point property</h2> <p class="note">Main article: <a href="/facts/Fixed-point_property/z8bNat1D">Fixed-point property</a></p> <p>A <a href="/facts/Topological_space/v2ut7CbK">topological space</a> X {\displaystyle X} is said to have the <a href="/facts/Fixed_point_property/z8bNat1D">fixed point property</a> (FPP) if for any <a href="/facts/Continuous_function/sKbl02pB">continuous function</a> </p> f : X → X {\displaystyle f\colon X\to X} <p>there exists x ∈ X {\displaystyle x\in X} such that f ( x ) = x {\displaystyle f(x)=x} . </p><p>The FPP is a <a href="/facts/Topological_invariant/vbJR18Sx">topological invariant</a>, i.e., it is preserved by any <a href="/facts/Homeomorphism/jMfWg3Mn">homeomorphism</a>. The FPP is also preserved by any <a href="/facts/Retraction_(topology)/477Gm67f">retraction</a>. </p><p>According to the <a href="/facts/Brouwer_fixed-point_theorem/xP2p03lQ">Brouwer fixed-point theorem</a>, every <a href="/facts/Compact_space/d0cgXJH7">compact</a> and <a href="/facts/Convex_set/vdAuJRJl">convex</a> <a href="/facts/Subset/SJGERmbA">subset</a> of a <a href="/facts/Euclidean_space/R2UbzmzM">Euclidean space</a> 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 <a href="/facts/Karol_Borsuk/SNqCQ4EB">Borsuk</a> asked whether compactness together with <a href="/facts/Contractible_space/REXYj8uS">contractibility</a> 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.<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a> </p> <h2 id="fixed-points-of-partial-orders">Fixed points of partial orders</h2> <p>In <a href="/facts/Domain_theory/G1wRMK2K">domain theory</a>, the notion and terminology of fixed points is generalized to a <a href="/facts/Partial_order/qb4a3FAX">partial order</a>. Let ≤ be a partial order over a set <i>X</i> and let <i>f</i>: <i>X</i> → <i>X</i> be a function over <i>X</i>. Then a prefixed point (also spelled pre-fixed point, sometimes shortened to prefixpoint or pre-fixpoint) of <i>f</i> is any <i>p</i> such that <i>f</i>(<i>p</i>) ≤ <i>p</i>. Analogously, a <i>postfixed point</i> of <i>f</i> is any <i>p</i> such that <i>p</i> ≤ <i>f</i>(<i>p</i>).<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a> The opposite usage occasionally appears.<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> Malkis justifies the definition presented here as follows: "since <i>f</i> is before the inequality sign in the term <i>f</i>(<i>x</i>) ≤ <i>x</i>, such <i>x</i> is called a prefix point."<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a> A fixed point is a point that is both a prefixpoint and a postfixpoint. Prefixpoints and postfixpoints have applications in <a href="/facts/Theoretical_computer_science/jSkGGuvy">theoretical computer science</a>.<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a> </p> <h3>Least fixed point</h3> <p class="note">Main article: <a href="/facts/Least_fixed_point/JbcBLqTN">Least fixed point</a></p> <p>In <a href="/facts/Order_theory/gn6fM3oJ">order theory</a>, the <a href="/facts/Least_fixed_point/JbcBLqTN">least fixed point</a> of a <a href="/facts/Function_(mathematics)/CdReEKCh">function</a> from a <a href="/facts/Partially_ordered_set/qb4a3FAX">partially ordered set</a> (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. </p><p>One way to express the <a href="/facts/Knaster%25E2%2580%2593Tarski_theorem/QeXjysqQ">Knaster–Tarski theorem</a> is to say that a <a href="/facts/Monotone_function/MjQK0YL2">monotone function</a> on a <a href="/facts/Complete_lattice/pQbphWeR">complete lattice</a> has a <a href="/facts/Least_fixed_point/JbcBLqTN">least fixed point</a> that coincides with its least prefixpoint (and similarly its greatest fixed point coincides with its greatest postfixpoint).<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a> </p> <h2 id="fixed-point-combinator">Fixed-point combinator</h2> <p class="note">Main article: <a href="/facts/Fixed_point_combinator/mRqKblYz">Fixed point combinator</a></p> <p>In <a href="/facts/Combinatory_logic/D7NNo4xT">combinatory logic</a> for <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, a fixed-point combinator is a <a href="/facts/Higher-order_function/VjnjGbpt">higher-order function</a> f i x {\displaystyle {\mathsf {fix}}} that returns a fixed point of its argument function, if one exists. Formally, if the function <i>f</i> has one or more fixed points, then </p> f i x f = f ( f i x f ) . {\displaystyle \operatorname {\mathsf {fix}} f=f(\operatorname {\mathsf {fix}} f).} <h2 id="fixed-point-logics">Fixed-point logics</h2> <p class="note">Main article: <a href="/facts/Fixed-point_logic/SaI7Y3wN">Fixed-point logic</a></p> <p>In <a href="/facts/Mathematical_logic/SaI7Y3wN">mathematical logic</a>, fixed-point logics are extensions of classical predicate logic that have been introduced to express recursion. Their development has been motivated by <a href="/facts/Descriptive_complexity_theory/Ec5F9CnT">descriptive complexity theory</a> and their relationship to <a href="/facts/Database_query_language/Sa6K4xXM">database query languages</a>, in particular to <a href="/facts/Datalog/67jbYWDb">Datalog</a>. </p> <h2 id="applications">Applications</h2> <p>In many fields, equilibria or <a href="/facts/Stability_theory/Su5sHnxs">stability</a> are fundamental concepts that can be described in terms of fixed points. Some examples follow. </p> <ul><li>In <a href="/facts/Projective_geometry/rHKSaEbx">projective geometry</a>, a fixed point of a <a href="/facts/Projectivity/wCkNzUjd">projectivity</a> has been called a double point.<a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a><a class="footnote-ref" id="fnref:9" href="#fn:9"><sup>9</sup></a></li> <li>In <a href="/facts/Economics/HYctA2Dn">economics</a>, a <a href="/facts/Nash_equilibrium/l74xzIHd">Nash equilibrium</a> of a <a href="/facts/Game_theory/zkEIj1ya">game</a> is a fixed point of the game's <a href="/facts/Best_response/1yhIpmxB">best response correspondence</a>. <a href="/facts/John_Forbes_Nash_Jr./wAg6sMSY">John Nash</a> exploited the <a href="/facts/Kakutani_fixed-point_theorem/qMQNEjzU">Kakutani fixed-point theorem</a> for his seminal paper that won him the Nobel prize in economics.</li> <li>In <a href="/facts/Physics/a7aH2y08">physics</a>, more precisely in the <a href="/facts/Phase_transition/eLP2BY8R">theory of phase transitions</a>, <i>linearization</i> near an <i>unstable</i> fixed point has led to <a href="/facts/Kenneth_G._Wilson/BSSajpeo">Wilson</a>'s Nobel prize-winning work inventing the <a href="/facts/Renormalization_group/Ugy0I1IR">renormalization group</a>, and to the mathematical explanation of the term "<a href="/facts/Critical_phenomenon/jqDDEnMl">critical phenomenon</a>."<a class="footnote-ref" id="fnref:10" href="#fn:10"><sup>10</sup></a><a class="footnote-ref" id="fnref:11" href="#fn:11"><sup>11</sup></a></li> <li><a href="/facts/Programming_language/cWTYbgWa">Programming language</a> <a href="/facts/Compilers/WNfCDFJe">compilers</a> use fixed point computations for program analysis, for example in <a href="/facts/Data-flow_analysis/jz2oI6sX">data-flow analysis</a>, which is often required for code <a href="/facts/Optimization_(computer_science)/nXz6RpRM">optimization</a>. They are also the core concept used by the generic program analysis method <a href="/facts/Abstract_interpretation/cj6wjzu1">abstract interpretation</a>.<a class="footnote-ref" id="fnref:12" href="#fn:12"><sup>12</sup></a></li> <li>In <a href="/facts/Type_theory/xj0xzVqI">type theory</a>, the <a href="/facts/Fixed-point_combinator/mRqKblYz">fixed-point combinator</a> allows definition of recursive functions in the <a href="/facts/Untyped_lambda_calculus/DaD3RuQ4">untyped lambda calculus</a>.</li> <li>The vector of <a href="/facts/PageRank/KtJRJFUX">PageRank</a> values of all web pages is the fixed point of a <a href="/facts/Linear_transformation/Q1PBKNVV">linear transformation</a> derived from the <a href="/facts/World_Wide_Web/wvnTrWFq">World Wide Web</a>'s link structure.</li> <li>The stationary distribution of a <a href="/facts/Markov_chain/5oP5hntk">Markov chain</a> is the fixed point of the one step transition probability function.</li> <li>Fixed points are used to finding formulas for <a href="/facts/Iterated_function/Vzsx64An">iterated functions</a>.</li></ul> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Cycles_and_fixed_points/1zjqh9he">Cycles and fixed points</a> of permutations</li> <li><a href="/facts/Eigenvector/8TjEoT8u">Eigenvector</a></li> <li><a href="/facts/Equilibrium_point/DgbGMPkg">Equilibrium</a></li> <li><a href="/facts/M%25C3%25B6bius_transformation/YEkTTLfK">Fixed points of a Möbius transformation</a></li> <li><a href="/facts/Idempotence/khbSpexv">Idempotence</a></li> <li><a href="/facts/Infinite_compositions_of_analytic_functions/N1JmTkaT">Infinite compositions of analytic functions</a></li></ul> <ul><li><a href="/facts/Invariant_(mathematics)/9TeNN2ed">Invariant (mathematics)</a></li></ul> <h2 id="notes">Notes</h2> <h2 id="external-links">External links</h2> <ul><li>Yutaka Nishiyama (2012). <a href="http://ijpam.eu/contents/2012-78-3/7/7.pdf">"An Elegant Solution for Drawing a Fixed Point"</a> (PDF). <i>International Journal of Pure and Applied Mathematics</i>. 78 (3): 363–377.</li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Brown, R. F., ed. (1988). Fixed Point Theory and Its Applications. American Mathematical Society. ISBN 0-8218-5080-6. <a href="0-8218-5080-6" target="_blank">0-8218-5080-6</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Kinoshita, Shin'ichi (1953). "On Some Contractible Continua without Fixed Point Property". Fund. Math. 40 (1): 96–98. doi:10.4064/fm-40-1-96-98. ISSN 0016-2736. <a href="https://doi.org/10.4064%2Ffm-40-1-96-98" target="_blank">https://doi.org/10.4064%2Ffm-40-1-96-98</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Smyth, Michael B.; Plotkin, Gordon D. (1982). "The Category-Theoretic Solution of Recursive Domain Equations" (PDF). Proceedings, 18th IEEE Symposium on Foundations of Computer Science. SIAM Journal of Computing (volume 11). pp. 761–783. doi:10.1137/0211062. <a href="https://homepages.inf.ed.ac.uk/gdp/publications/Category_Theoretic_Solution.pdf" target="_blank">https://homepages.inf.ed.ac.uk/gdp/publications/Category_Theoretic_Solution.pdf</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Patrick Cousot; Radhia Cousot (1979). "Constructive Versions of Tarski's Fixed Point Theorems" (PDF). Pacific Journal of Mathematics. 82 (1): 43–57. doi:10.2140/pjm.1979.82.43. <a href="http://www.di.ens.fr/~cousot/COUSOTpapers/publications.www/CousotCousot-PacJMath-82-1-1979.pdf" target="_blank">http://www.di.ens.fr/~cousot/COUSOTpapers/publications.www/CousotCousot-PacJMath-82-1-1979.pdf</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>Malkis, Alexander (2015). "Multithreaded-Cartesian Abstract Interpretation of Multithreaded Recursive Programs Is Polynomial" (PDF). Reachability Problems. Lecture Notes in Computer Science. Vol. 9328. pp. 114–127. doi:10.1007/978-3-319-24537-9_11. ISBN 978-3-319-24536-2. S2CID 17640585. Archived from the original (PDF) on 2022-08-10. <a href="978-3-319-24536-2" target="_blank">978-3-319-24536-2</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>Yde Venema (2008) Lectures on the Modal μ-calculus Archived March 21, 2012, at the Wayback Machine <a href="http://staff.science.uva.nl/~yde/teaching/ml/mu/mu2008.pdf" target="_blank">http://staff.science.uva.nl/~yde/teaching/ml/mu/mu2008.pdf</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>Yde Venema (2008) Lectures on the Modal μ-calculus Archived March 21, 2012, at the Wayback Machine <a href="http://staff.science.uva.nl/~yde/teaching/ml/mu/mu2008.pdf" target="_blank">http://staff.science.uva.nl/~yde/teaching/ml/mu/mu2008.pdf</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>Coxeter, H. S. M. (1942). Non-Euclidean Geometry. University of Toronto Press. p. 36. <a href="/wiki/H._S._M._Coxeter" target="_blank">/wiki/H._S._M._Coxeter</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> <li id="fn:9"><p>G. B. Halsted (1906) Synthetic Projective Geometry, page 27 <a href="/wiki/G._B._Halsted" target="_blank">/wiki/G._B._Halsted</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li> <li id="fn:10"><p>Wilson, Kenneth G. (1971). "Renormalization Group and Critical Phenomena. I. Renormalization Group and the Kadanoff Scaling Picture". Physical Review B. 4 (9): 3174–3183. Bibcode:1971PhRvB...4.3174W. doi:10.1103/PhysRevB.4.3174. <a href="https://doi.org/10.1103%2FPhysRevB.4.3174" target="_blank">https://doi.org/10.1103%2FPhysRevB.4.3174</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li> <li id="fn:11"><p>Wilson, Kenneth G. (1971). "Renormalization Group and Critical Phenomena. II. Phase-Space Cell Analysis of Critical Behavior". Physical Review B. 4 (9): 3184–3205. Bibcode:1971PhRvB...4.3184W. doi:10.1103/PhysRevB.4.3184. <a href="https://doi.org/10.1103%2FPhysRevB.4.3184" target="_blank">https://doi.org/10.1103%2FPhysRevB.4.3184</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></p></li> <li id="fn:12"><p>"P. Cousot & R. Cousot, Abstract interpretation: A unified lattice model for static analysis of programs by construction or approximation of fixpoints". <a href="https://www.di.ens.fr/~cousot/COUSOTpapers/POPL77.shtml" target="_blank">https://www.di.ens.fr/~cousot/COUSOTpapers/POPL77.shtml</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></p></li> </ol>