Inmathematics, afixed point (sometimes shortened tofixpoint), also known as aninvariant point, is a value that does not change under a giventransformation. Specifically, forfunctions, a fixed point is an element that is mapped to itself by the function. Any set of fixed points of a transformation is also aninvariant set.
Formally,c is a fixed point of a functionf ifc belongs to both thedomain and thecodomain off, andf(c) =c.In particular,f cannot have any fixed point if its domain is disjoint from its codomain.Iff is defined on thereal numbers, it corresponds, in graphical terms, to acurve in theEuclidean plane, and each fixed-pointc corresponds to an intersection of the curve with the liney = x, cf. picture.
For example, iff is defined on thereal numbers bythen 2 is a fixed point off, becausef(2) = 2.
Not all functions have fixed points: for example,f(x) =x + 1 has no fixed points becausex + 1 is never equal tox for any real number.
Innumerical analysis,fixed-point iteration is a method of computing fixed points of a function. Specifically, given a function with the same domain and codomain, a point in the domain of, the fixed-point iteration is
which gives rise to thesequence ofiterated function applications which is hoped toconverge to a point. If is continuous, then one can prove that the obtained is a fixed point of.
The notions of attracting fixed points, repelling fixed points, andperiodic points are defined with respect to fixed-point iteration.
A fixed-point theorem is a result saying that at least one fixed point exists, under some general condition.[1]
For example, theBanach fixed-point theorem (1922) gives a general criterion guaranteeing that, if it is satisfied,fixed-point iteration will always converge to a fixed point.
TheBrouwer fixed-point theorem (1911) says that anycontinuous function from the closedunit ball inn-dimensionalEuclidean space to itself must have a fixed point, but it doesn't describe how to find the fixed point.
TheLefschetz fixed-point theorem (and theNielsen fixed-point theorem) fromalgebraic topology give a way to count fixed points.
Inalgebra, for a groupG acting on a setX with agroup action,x inX is said to be a fixed point ofg if.
Thefixed-point subgroup of anautomorphismf of agroupG is thesubgroup ofG:
Similarly, thefixed-point subring of anautomorphismf of aringR is thesubring of the fixed points off, that is,
InGalois theory, the set of the fixed points of a set offield automorphisms is afield called thefixed field of the set of automorphisms.
Atopological space is said to have thefixed point property (FPP) if for anycontinuous function
there exists such that.
The FPP is atopological invariant, i.e., it is preserved by anyhomeomorphism. The FPP is also preserved by anyretraction.
According to theBrouwer fixed-point theorem, everycompact andconvexsubset of aEuclidean 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 1932Borsuk asked whether compactness together withcontractibility 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.[2]
Indomain theory, the notion and terminology of fixed points is generalized to apartial order. Let ≤ be a partial order over a setX and letf:X →X be a function overX. Then aprefixed point (also spelledpre-fixed point, sometimes shortened toprefixpoint orpre-fixpoint)[citation needed] off is anyp such thatf(p) ≤p. Analogously, apostfixed point off is anyp such thatp ≤f(p).[3] The opposite usage occasionally appears.[4] Malkis justifies the definition presented here as follows: "sincef isbefore the inequality sign in the termf(x) ≤x, suchx is called aprefix point."[5] A fixed point is a point that is both a prefixpoint and a postfixpoint. Prefixpoints and postfixpoints have applications intheoretical computer science.[6]
Inorder theory, theleast fixed point of afunction from apartially 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 theKnaster–Tarski theorem is to say that amonotone function on acomplete lattice has aleast fixed point that coincides with its least prefixpoint (and similarly its greatest fixed point coincides with its greatest postfixpoint).[7]
Incombinatory logic forcomputer science, a fixed-point combinator is ahigher-order function that returns a fixed point of its argument function, if one exists. Formally, if the functionf has one or more fixed points, then
Inmathematical logic, fixed-point logics are extensions of classical predicate logic that have been introduced to express recursion. Their development has been motivated bydescriptive complexity theory and their relationship todatabase query languages, in particular toDatalog.
 | This sectionneeds additional citations forverification. Please helpimprove this article byadding citations to reliable sources in this section. Unsourced material may be challenged and removed.(July 2018) (Learn how and when to remove this message) |
In many fields, equilibria orstability are fundamental concepts that can be described in terms of fixed points. Some examples follow.