
In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern 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
Transformation may refer to:
Science and mathematics
In biology and medicine
* Metamorphosis, the biological process of changing physical form after birth or hatching
* Malignant transformation, the process of cells becoming cancerous
* Trans ...
. Specifically, for
functions, a fixed point is an element that is mapped to itself by the function.
Fixed point of a function
Formally, is a fixed point of a function if belongs to both the
domain
Domain may refer to:
Mathematics
*Domain of a function, the set of input values for which the (total) function is defined
**Domain of definition of a partial function
**Natural domain of a partial function
**Domain of holomorphy of a function
* Do ...
and the
codomain of , and .
For example, if is defined on the
real numbers by
then 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.
Fixed point iteration
In
numerical 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 the
sequence of
iterated function applications
which is hoped to
converge 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, and
periodic points are defined with respect to fixed-point iteration.
Fixed-point theorems
A fixed-point theorem is a result saying that at least one fixed point exists, under some general condition.
For example, the
Banach fixed-point theorem
In mathematics, the Banach fixed-point theorem (also known as the contraction mapping theorem or contractive mapping theorem) is an important tool in the theory of metric spaces; it guarantees the existence and uniqueness of fixed points of certai ...
(1922) gives a general criterion guaranteeing that, if it is satisfied,
fixed-point iteration
In numerical analysis, fixed-point iteration is a method of computing fixed points of a function.
More specifically, given a function f defined on the real numbers with real values and given a point x_0 in the domain of f, the fixed-point iterat ...
will always converge to a fixed point.
The
Brouwer fixed-point theorem (1911) says that any
continuous function
In mathematics, a continuous function is a function such that a continuous variation (that is a change without jump) of the argument induces a continuous variation of the value of the function. This means that there are no abrupt changes in value ...
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 Nielsen theory is a branch of mathematical research with its origins in topological fixed-point theory. Its central ideas were developed by Danish mathematician Jakob Nielsen, and bear his name.
The theory developed in the study of the so-called ' ...
) 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 , ''x'' in ''X'' is said to be a fixed point of ''g'' if
.
The
fixed-point subgroup
In algebra, the fixed-point subgroup G^f of an automorphism ''f'' of a group ''G'' is the subgroup of ''G'':
:G^f = \.
More generally, if ''S'' is a set of automorphisms of ''G'' (i.e., a subset of the automorphism group of ''G''), then the set o ...
of an
automorphism
In mathematics, an automorphism is an isomorphism from a mathematical object to itself. It is, in some sense, a symmetry of the object, and a way of mapping the object to itself while preserving all of its structure. The set of all automorphisms ...
''f'' of a
group ''G'' is the
subgroup of ''G'':
Similarly, the
fixed-point subring In algebra, the fixed-point subring R^f of an automorphism ''f'' of a ring ''R'' is the subring of the fixed points of ''f'', that is,
:R^f = \.
More generally, if ''G'' is a group acting on ''R'', then the subring of ''R''
:R^G = \
is called th ...
of an
automorphism
In mathematics, an automorphism is an isomorphism from a mathematical object to itself. It is, in some sense, a symmetry of the object, and a way of mapping the object to itself while preserving all of its structure. The set of all automorphisms ...
''f'' of a
ring
Ring may refer to:
* Ring (jewellery), a round band, usually made of metal, worn as ornamental jewelry
* To make a sound with a bell, and the sound made by a bell
:(hence) to initiate a telephone connection
Arts, entertainment and media Film and ...
''R'' is the
subring
In mathematics, a subring of ''R'' is a subset of a ring that is itself a ring when binary operations of addition and multiplication on ''R'' are restricted to the subset, and which shares the same multiplicative identity as ''R''. For those wh ...
of the fixed points of ''f'', that is,
In
Galois theory, the set of the fixed points of a set of
field automorphisms is a
field called the
fixed field In algebra, the fixed-point subring R^f of an automorphism ''f'' of a ring ''R'' is the subring of the fixed points of ''f'', that is,
:R^f = \.
More generally, if ''G'' is a group acting on ''R'', then the subring of ''R''
:R^G = \
is called th ...
of the set of automorphisms.
Topological fixed point property
A
topological space is said to have the
fixed point property A mathematical object ''X'' has the fixed-point property if every suitably well-behaved mapping from ''X'' to itself has a fixed point. The term is most commonly used to describe topological spaces on which every continuous mapping has a fixed poi ...
(FPP) if for any
continuous function
In mathematics, a continuous function is a function such that a continuous variation (that is a change without jump) of the argument induces a continuous variation of the value of the function. This means that there are no abrupt changes in value ...
:
there exists
such that
.
The FPP is a
topological invariant, i.e. is preserved by any
homeomorphism. The FPP is also preserved by any
retraction
Retraction or retract(ed) may refer to:
Academia
* Retraction in academic publishing, withdrawals of previously published academic journal articles
Mathematics
* Retraction (category theory)
* Retract (group theory)
* Retraction (topology)
Huma ...
.
According to the
Brouwer fixed-point theorem, every
compact
Compact as used in politics may refer broadly to a pact or treaty; in more specific cases it may refer to:
* Interstate compact
* Blood compact, an ancient ritual of the Philippines
* Compact government, a type of colonial rule utilized in British ...
and
convex subset
In mathematics, Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are ...
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.
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) of ''f'' is any ''p'' such that ''f''(''p'') ≤ ''p''. Analogously, a ''postfixed point'' of ''f'' is any ''p'' such that ''p'' ≤ ''f''(''p'').
The opposite usage occasionally appears.
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." A fixed point is a point that is both a prefixpoint and a postfixpoint. Prefixpoints and postfixpoints have applications in
theoretical computer science.
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
In mathematics, a complete lattice is a partially ordered set in which ''all'' subsets have both a supremum (join) and an infimum (meet). A lattice which satisfies at least one of these properties is known as a ''conditionally complete lattice.'' ...
has a
least fixpoint
In order theory, a branch of mathematics, the least fixed point (lfp or LFP, sometimes also smallest fixed point) of a function from a partially ordered set to itself is the fixed point which is less than each other fixed point, according to the ...
that coincides with its least prefixpoint (and similarly its greatest fixpoint coincides with its greatest postfixpoint).
Fixed-point combinator
In
combinatory logic
Combinatory logic is a notation to eliminate the need for quantified variables in mathematical logic. It was introduced by Moses Schönfinkel and Haskell Curry, and has more recently been used in computer science as a theoretical model of comput ...
for
computer science, a fixed-point combinator is a
higher-order function
In mathematics and computer science, a higher-order function (HOF) is a function that does at least one of the following:
* takes one or more functions as arguments (i.e. a procedural parameter, which is a parameter of a procedure that is itself ...
that returns a fixed point of its argument function, if one exists. Formally, if the function ''f'' has one or more fixed points, then
:
Fixed-point logics
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.
Applications
In many fields, equilibria or
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.
* In
economics, a
Nash equilibrium
In game theory, the Nash equilibrium, named after the mathematician John Nash, is the most common way to define the solution of a non-cooperative game involving two or more players. In a Nash equilibrium, each player is assumed to know the equili ...
of a
game
A game is a structured form of play (activity), play, usually undertaken for enjoyment, entertainment or fun, and sometimes used as an educational tool. Many games are also considered to be work (such as professional players of spectator s ...
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, ''linearization'' near an ''unstable'' fixed point has led to
Wilson
Wilson may refer to:
People
* Wilson (name)
** List of people with given name Wilson
** List of people with surname Wilson
* Wilson (footballer, 1927–1998), Brazilian manager and defender
* Wilson (footballer, born 1984), full name Wilson Ro ...
's Nobel prize-winning work inventing the
renormalization group, and to the mathematical explanation of the term "
critical phenomenon
In physics, critical phenomena is the collective name associated with the
physics of critical points. Most of them stem from the divergence of the
correlation length, but also the dynamics slows down. Critical phenomena include scaling relations ...
."
*
Programming language compilers use fixed point computations for program analysis, for example in
data-flow analysis
In computing, dataflow is a broad concept, which has various meanings depending on the application and context. In the context of software architecture, data flow relates to stream processing or reactive programming.
Software architecture
Dataf ...
, which is often required for code
optimization. They are also the core concept used by the generic program analysis method
abstract interpretation
In computer science, abstract interpretation is a theory of sound approximation of the semantics of computer programs, based on monotonic functions over ordered sets, especially lattices. It can be viewed as a partial execution of a computer prog ...
.
* In
type theory, the
fixed-point combinator
In mathematics and computer science in general, a '' fixed point'' of a function is a value that is mapped to itself by the function.
In combinatory logic for computer science, a fixed-point combinator (or fixpoint combinator) is a higher-order fu ...
allows definition of recursive functions in the
untyped lambda calculus
Lambda calculus (also written as ''λ''-calculus) is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution. It is a universal model of computation t ...
.
* 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
A Markov chain or Markov process is a stochastic model describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event. Informally, this may be thought of as, "What happe ...
is the fixed point of the one step transition probability function.
* Fixed points are used to finding formulas for
iterated functions.
See also
*
Cycles and fixed points of permutations
*
Eigenvector
*
Equilibrium
*
Fixed points of a Möbius transformation
*
Idempotence
*
Infinite compositions of analytic functions
*
Invariant (mathematics)
Notes
{{reflist
External links
An Elegant Solution for Drawing a Fixed Point
Game theory