, a fixed point (sometimes shortened to fixpoint, also known as an invariant point) of a function
is an element of the function's domain
that is mapped to itself by the function. That is to say, ''c'' is a fixed point of the function ''f'' if ''f''(''c'') = ''c''. This means ''f''(''f''(...''f''(''c'')...)) = ''f'' ''n''
(''c'') = ''c'', an important terminating consideration when recursively computing ''f''. A set
of fixed points is sometimes called a ''fixed set''.
For example, if ''f'' is defined on the real number
then 2 is a fixed point of ''f'', because ''f''(2) = 2.
Not all functions have fixed points: for example, ''f''(''x'') = ''x'' +1, has no fixed points, since ''x'' is never equal to ''x'' +1 for any real number. In graphical terms, a fixed point ''x'' means the point (''x'', ''f''(''x'')) is on the line ''y'' = ''x'', or in other words the graph
of ''f'' has a point in common with that line.
Points that come back to the same value after a finite number of iterations
of the function are called ''periodic point
s''. A ''fixed point'' is a periodic point with period equal to one. In projective geometry
, a fixed point of a projectivity
has been called a double point.
In Galois theory
, the set of the fixed points of a set of field automorphism
s is a field
called the fixed field
of the set of automorphisms.
Attracting fixed points
An ''attracting fixed point'' of a function ''f'' is a fixed point ''x''0
of ''f'' such that for any value of ''x'' in the domain that is close enough to ''x''0
, the iterated function
. An expression of prerequisites and proof of the existence of such a solution is given by the Banach fixed-point theorem
The natural cosine
function ("natural" means in radian
s, not degrees or other units) has exactly one fixed point, which is attracting. In this case, "close enough" is not a stringent criterion at all—to demonstrate this, start with ''any'' real number and repeatedly press the ''cos'' key on a calculator (checking first that the calculator is in "radians" mode). It eventually converges to about 0.739085133, which is a fixed point. That is where the graph of the cosine function intersects the line
Not all fixed points are attracting. For example, ''x'' = 0 is a fixed point of the function ''f''(''x'') = 2''x'', but iteration of this function for any value other than zero rapidly diverges. However, if the function ''f'' is continuously differentiable in an open neighbourhood of a fixed point ''x''0
, attraction is guaranteed.
Attracting fixed points are a special case of a wider mathematical concept of attractor
An attracting fixed point is said to be a ''stable fixed point'' if it is also Lyapunov stable
A fixed point is said to be a ''neutrally stable fixed point'' if it is Lyapunov stable
but not attracting. The center of a linear homogeneous differential equation
of the second order is an example of a neutrally stable fixed point.
Multiple attracting points can be collected in an ''attracting fixed set''.
In many fields, equilibria or stability
are fundamental concepts that can be described in terms of fixed points. Some examples follow.
* In economics
, a Nash equilibrium
of a game
is a fixed point of the game's best response correspondence
. 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 theory of phase transitions
, ''linearisation'' near an ''unstable'' fixed point has led to Wilson
's Nobel prize-winning work inventing the renormalization group
, and to the mathematical explanation of the term "critical phenomenon
* Programming language compilers
use fixed point computations for program analysis, for example in data-flow analysis
, which is often required for code optimization
. They are also the core concept used by the generic program analysis method abstract interpretation
* 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.
* Logician Saul Kripke
makes use of fixed points in his influential theory of truth. He shows how one can generate a partially defined truth predicate (one that remains undefined for problematic sentences like "''This sentence is not true''"), by recursively defining "truth" starting from the segment of a language that contains no occurrences of the word, and continuing until the process ceases to yield any newly well-defined sentences. (This takes a countable infinity
of steps.) That is, for a language L, let L′ (read "L-prime") be the language generated by adding to L, for each sentence S in L, the sentence "''S is true.''" A fixed point is reached when L′ is L; at this point sentences like "''This sentence is not true''" remain undefined, so, according to Kripke, the theory is suitable for a natural language that contains its ''own'' truth predicate.
Topological fixed point property
A topological space
is said to have the ''fixed point property'' (FPP) if for any continuous function
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.
Generalization to partial orders: prefixpoint and postfixpoint
The notion and terminology 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 prefixpoint (also spelled pre-fixpoint) of ''f'' is any ''p'' such that ''f''(''p'') ≤ ''p''. Analogously a postfixpoint (or post-fixpoint) of ''f'' is any ''p'' such that ''p'' ≤ ''f''(''p'').
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). Prefixpoints and postfixpoints have applications in theoretical computer science
[Yde Venema (2008]
Lectures on the Modal μ-calculus
*Fixed points of a Möbius transformation
*Infinite compositions of analytic functions
*Cycles and fixed points
An Elegant Solution for Drawing a Fixed Point