Fixed point (mathematics)

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. Any set of fixed points of a transformation is also an invariant set.

---

Fixed point of a function Formally, is a fixed point of a function if belongs to both the domain and the codomain of , and . In particular, cannot have any fixed point if its domain is disjoint from its codomain. If is defined on the , it corresponds, in graphical terms, to a curve in the Euclidean plane, and each fixed-point corresponds to an intersection of the curve with the line , cf. picture.

For example, if is defined on the by $f(x)\; =\; x^2\; -\; 3\; x\; +\; 4,$ then 2 is a fixed point of , because .

Not all functions have fixed points: for example, has no fixed points because is never equal to for any real number.

---

Fixed point iteration In numerical analysis, fixed-point iteration is a method of computing fixed points of a function. Specifically, given a function $f$ with the same domain and codomain, a point $x\_0$ in the domain of $f$, the fixed-point iteration is

$$x\_\{n+1\}=f(x\_n),\; \backslash ,\; n=0,\; 1,\; 2,\; \backslash dots$$

which gives rise to the sequence $x\_0,\; x\_1,\; x\_2,\; \backslash dots$ of iterated function applications $x\_0,\; f(x\_0),\; f(f(x\_0)),\; \backslash dots$ which is hoped to converge to a point $x$. If $f$ is continuous, then one can prove that the obtained $x$ is a fixed point of $f$.

The notions of attracting fixed points, repelling fixed points, and 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.

(1988). 9780821850800, American Mathematical Society. ISBN 9780821850800

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 theory) 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 $\backslash cdot$, x in X is said to be a fixed point of g if $g\; \backslash cdot\; x\; =\; x$.

The fixed-point subgroup $G^f$ of an automorphism f of a group G is the subgroup of G: $$G^f\; =\; \backslash \{\; g\; \backslash in\; G\; \backslash mid\; f(g)\; =\; g\; \backslash \}.$$

Similarly, 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\; =\; \backslash \{\; r\; \backslash in\; R\; \backslash mid\; f(r)\; =\; r\; \backslash \}.$$

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.

---

Topological fixed point property A topological space $X$ is said to have the fixed point property (FPP) if for any continuous function

$f\backslash colon\; X\; \backslash to\; X$

there exists $x\; \backslash in\; X$ such that $f(x)=x$.

The FPP is a topological invariant, i.e., it is preserved by any homeomorphism. The FPP is also preserved by any retraction.

According to the Brouwer fixed-point theorem, every compact space and convex set 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 Karol 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."

(2026). 9783319245362 ISBN 9783319245362

A fixed point is a point that is both a prefixpoint and a postfixpoint. Prefixpoints and postfixpoints have applications in theoretical computer science.Yde Venema (2008) Lectures on the Modal μ-calculus

---

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 fixed point that coincides with its least prefixpoint (and similarly its greatest fixed point coincides with its greatest postfixpoint).Yde Venema (2008) Lectures on the Modal μ-calculus

---

Fixed-point combinator In combinatory logic for computer science, a fixed-point combinator is a higher-order function $\backslash 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

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

---

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 theory 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.G. B. Halsted (1906) Synthetic Projective Geometry, page 27
• In economics, a Nash equilibrium of a game theory is a fixed point of the game's best response. 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 phase transition, linearization 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.
• 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

---

External links

Post Comment