Fixed point (mathematics)

In

Formally, c is a fixed point of a function f if c belongs to both the domain and the codomain of f, and f(c) = c.

For example, if f is defined on the real numbers by

$${\displaystyle f(x)=x^{2}-3x+4,}$$

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.

Fixed point iteration

In numerical analysis, fixed-point iteration is a method of computing fixed points of a function. Specifically, given a function ${\displaystyle f}$ with the same domain and codomain, a point ${\displaystyle x_{0}}$ in the domain of ${\displaystyle f}$, the fixed-point iteration is

$${\displaystyle x_{n+1}=f(x_{n}),\,n=0,1,2,\dots }$$

which gives rise to the sequence ${\displaystyle x_{0},x_{1},x_{2},\dots }$ of iterated function applications ${\displaystyle x_{0},f(x_{0}),f(f(x_{0})),\dots }$ which is hoped to converge to a point ${\displaystyle x}$. If ${\displaystyle f}$ is continuous, then one can prove that the obtained ${\displaystyle x}$ is a fixed point of ${\displaystyle f}$.

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.^[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

The Lefschetz fixed-point theorem (and the Nielsen fixed-point theorem) 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 ${\displaystyle \cdot }$, x in X is said to be a fixed point of g if ${\displaystyle g\cdot x=x}$.

The fixed-point subgroup ${\displaystyle G^{f}}$ of an automorphism f of a group G is the subgroup of G:

$${\displaystyle G^{f}=\{g\in G\mid f(g)=g\}.}$$

Similarly, the fixed-point subring ${\displaystyle R^{f}}$ of an automorphism f of a ring R is the subring of the fixed points of f, that is,

$${\displaystyle R^{f}=\{r\in R\mid f(r)=r\}.}$$

In

Topological fixed point property

A topological space ${\displaystyle X}$ is said to have the

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]

Fixed points of partial orders

In

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

In combinatory logic for computer science, a fixed-point combinator is a higher-order function ${\displaystyle {\mathsf {fix}}}$ that returns a fixed point of its argument function, if one exists. Formally, if the function f has one or more fixed points, then

${\displaystyle \operatorname {\mathsf {fix}} f=f(\operatorname {\mathsf {fix}} f).}$

Fixed-point logics

In

.

Applications

This section needs additional citations for verification. Please help improve this article by adding citations to reliable sources in this section. Unsourced material may be challenged and removed. (July 2018) (Learn how and when to remove this template message)

In many fields, equilibria or stability are fundamental concepts that can be described in terms of fixed points. Some examples follow.

• In
  projectivity has been called a double point.^[8][9]
• 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
  critical phenomenon."^[10][11]
• optimization. They are also the core concept used by the generic program analysis method abstract interpretation.^[12]
• In
  untyped lambda calculus
  .
• The vector of
  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.
• Fixed points are used to finding formulas for iterated functions.

See also

Notes