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. Specifically, for functions, a fixed point is an element that is mapped to itself by the function.
Formally, is a fixed point of a function if belongs to both the domain and the codomain of, and .
For example, if is defined on the real numbers bythen 2 is a fixed point of, because .
Not all functions have fixed points: for example,, has no fixed points, since is never equal to for any real number. In graphical terms, a fixed-point means the point is on the line, or in other words the graph of has a point in common with that line.
See main article: Fixed-point iteration.
In numerical analysis, fixed-point iteration is a method of computing fixed points of a function. Specifically, given a function
f
x0
f
x0,x1,x2,...
x0,f(x0),f(f(x0)),...
x
f
x
f
The notions of attracting fixed points, repelling fixed points, and periodic points are defined with respect to fixed-point iteration.
See main article: Fixed-point theorems.
A fixed-point theorem is a result saying that at least one fixed point exists, under some general condition.[1]
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 fixed-point theorem) from algebraic topology give a way to count fixed points.
⋅
g ⋅ x=x
Gf
Rf
In Galois theory, the set of the fixed points of a set of field automorphisms is a field called the fixed field of the set of automorphisms.
See main article: article and Fixed-point property.
X
f\colonX\toX
x\inX
f(x)=x
The FPP is a topological invariant, i.e. is preserved by any homeomorphism. The FPP is also preserved by any retraction.
According to the Brouwer fixed-point theorem, every compact and 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 Borsuk asked whether compactness together with 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.[2]
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) of f is any p such that f(p) ≤ p. Analogously, a postfixed point of f is any p such that p ≤ f(p).[3] The opposite usage occasionally appears.[4] Malkis justifies the definition presented here as follows: "since f is the inequality sign in the term f(x) ≤ x, such x is called a fix point."[5] A fixed point is a point that is both a prefixpoint and a postfixpoint. Prefixpoints and postfixpoints have applications in theoretical computer science.[6]
See main article: Least fixed point.
In order theory, the least fixed point of a 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 fixpoint that coincides with its least prefixpoint (and similarly its greatest fixpoint coincides with its greatest postfixpoint).[7]
See main article: Fixed point combinator.
fix
\operatorname{fix
See main article: 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 languages, in particular to Datalog.
In many fields, equilibria or stability are fundamental concepts that can be described in terms of fixed points. Some examples follow.