Fixed point (mathematics)

Last updated
A function with three fixed points Fixed point example.svg
A function with three fixed points

In mathematics, 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)...)) = fn(c) = c, an important terminating consideration when recursively computing f. A set of fixed points is sometimes called a fixed set.

Contents

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

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 points . 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. [1] [2]

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.

Attracting fixed points

The fixed point iteration xn+1 = cos xn with initial value x1 = -1. Cosine fixed point.svg
The fixed point iteration xn+1 = cos xn with initial value x1 = −1.

An attracting fixed point of a function f is a fixed point x0 of f such that for any value of x in the domain that is close enough to x0, the iterated function sequence

converges to x0. 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 radians, 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 . [3]

Not all fixed points are attracting. For example, x = 0 is a fixed point of the function f(x) = 2x, 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 x0, and , attraction is guaranteed.

Attracting fixed points are a special case of a wider mathematical concept of attractors.

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.

Applications

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

Topological fixed point property

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

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.

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

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: XX be a function over X. Then a prefixpoint (also spelled pre-fixpoint) of f is any p such that pf(p). Analogously, a postfixpoint (or post-fixpoint) of f is any p such that f(p) ≤ p. [8] 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 postfixpoint (and similarly its greatest fixpoint coincides with its greatest prefixpoint). Prefixpoints and postfixpoints have applications in theoretical computer science. [9]

See also

Notes

  1. Coxeter, H. S. M. (1942). Non-Euclidean Geometry. University of Toronto Press. p. 36.
  2. G. B. Halsted (1906) Synthetic Projective Geometry, page 27
  3. Weisstein, Eric W. "Dottie Number". Wolfram MathWorld. Wolfram Research, Inc. Retrieved 23 July 2016.
  4. https://journals.aps.org/prb/pdf/10.1103/PhysRevB.4.3174
  5. https://journals.aps.org/prb/pdf/10.1103/PhysRevB.4.3184
  6. https://www.di.ens.fr/~cousot/COUSOTpapers/POPL77.shtml
  7. Kinoshita, S. (1953). "On Some Contractible Continua without Fixed Point Property". Fund. Math. 40 (1): 96–98. ISSN   0016-2736.
  8. Patrick Cousot; Radhia Cousot (1979). "Constructive Versions of Tarski's Fixed Point Theorems". Pacific Journal of Mathematics . 82 (1): 43–57.
  9. Yde Venema (2008) Lectures on the Modal μ-calculus Archived March 21, 2012, at the Wayback Machine

Related Research Articles

Brouwer's fixed-point theorem is a fixed-point theorem in topology, named after L. E. J. (Bertus) Brouwer. It states that for any continuous function mapping a compact convex set to itself there is a point such that . The simplest forms of Brouwer's theorem are for continuous functions from a closed interval in the real numbers to itself or from a closed disk to itself. A more general form than the latter is for continuous functions from a convex compact subset of Euclidean space to itself.

Compact space Topological notions of all points being "close"

In mathematics, more specifically in general topology, compactness is a property that generalizes the notion of a subset of Euclidean space being closed and bounded. Examples include a closed interval, a rectangle, or a finite set of points. This notion is defined for more general topological spaces than Euclidean space in various ways.

In mathematics, a topological space is, roughly speaking, a geometrical space in which closeness is defined but cannot necessarily be measured by a numeric distance. More specifically, a topological space is a set of points, along with a set of neighbourhoods for each point, satisfying a set of axioms relating points and neighbourhoods.

In computability theory, Kleene's recursion theorems are a pair of fundamental results about the application of computable functions to their own descriptions. The theorems were first proved by Stephen Kleene in 1938 and appear in his 1952 book Introduction to Metamathematics. A related theorem, which constructs fixed points of a computable function, is known as Rogers's theorem and is due to Hartley Rogers, Jr..

General topology Branch of topology

In mathematics, general topology is the branch of topology that deals with the basic set-theoretic definitions and constructions used in topology. It is the foundation of most other branches of topology, including differential topology, geometric topology, and algebraic topology. Another name for general topology is point-set topology.

In the mathematical areas of order and lattice theory, the Knaster–Tarski theorem, named after Bronisław Knaster and Alfred Tarski, states the following:

In mathematics, specifically in the study of dynamical systems, an orbit is a collection of points related by the evolution function of the dynamical system. It can be understood as the subset of phase space covered by the trajectory of the dynamical system under a particular set of initial conditions, as the system evolves. As phase space trajectory is uniquely determined for any given set of phase space coordinates, it is not possible for different orbits to intersect in phase space, therefore the set of all orbits of a dynamical system is a partition of the phase space. Understanding the properties of orbits by using topological methods is one of the objectives of the modern theory of dynamical systems.

In differential geometry, the Atiyah–Singer index theorem, proved by Michael Atiyah and Isadore Singer (1963), states that for an elliptic differential operator on a compact manifold, the analytical index is equal to the topological index. It includes many other theorems, such as the Chern–Gauss–Bonnet theorem and Riemann–Roch theorem, as special cases, and has applications to theoretical physics.

In mathematics, a duality translates concepts, theorems or mathematical structures into other concepts, theorems or structures, in a one-to-one fashion, often by means of an involution operation: if the dual of A is B, then the dual of B is A. Such involutions sometimes have fixed points, so that the dual of A is A itself. For example, Desargues' theorem is self-dual in this sense under the standard duality in projective geometry.

In mathematics, a number of fixed-point theorems in infinite-dimensional spaces generalise the Brouwer fixed-point theorem. They have applications, for example, to the proof of existence theorems for partial differential equations.

In mathematics, a fixed-point theorem is a result saying that a function F will have at least one fixed point, under some conditions on F that can be stated in general terms. Results of this kind are amongst the most generally useful in mathematics.

In mathematics, geometric invariant theory is a method for constructing quotients by group actions in algebraic geometry, used to construct moduli spaces. It was developed by David Mumford in 1965, using ideas from the paper in classical invariant theory.

Manifold Topological space that locally resembles Euclidean space

In mathematics, a manifold is a topological space that locally resembles Euclidean space near each point. More precisely, an n-dimensional manifold, or n-manifold for short, is a topological space with the property that each point has a neighborhood that is homeomorphic to an open subset of n-dimensional Euclidean space.

In mathematical analysis, the Kakutani fixed-point theorem is a fixed-point theorem for set-valued functions. It provides sufficient conditions for a set-valued function defined on a convex, compact subset of a Euclidean space to have a fixed point, i.e. a point which is mapped to a set containing it. The Kakutani fixed point theorem is a generalization of Brouwer fixed point theorem. The Brouwer fixed point theorem is a fundamental result in topology which proves the existence of fixed points for continuous functions defined on compact, convex subsets of Euclidean spaces. Kakutani's theorem extends this to set-valued functions.

In mathematics, the Lefschetz zeta-function is a tool used in topological periodic and fixed point theory, and dynamical systems. Given a continuous map , the zeta-function is defined as the formal series

In mathematics, and in particular the study of dynamical systems, the idea of stable and unstable sets or stable and unstable manifolds give a formal mathematical definition to the general notions embodied in the idea of an attractor or repellor. In the case of hyperbolic dynamics, the corresponding notion is that of the hyperbolic set.

In mathematics, especially in the study of dynamical systems and differential equations, the stable manifold theorem is an important result about the structure of the set of orbits approaching a given hyperbolic fixed point. It roughly states that the existence of a local diffeomorphism near a fixed point implies the existence of a local stable center manifold containing that fixed point. This manifold has dimension equal to the number of eigenvalues of the Jacobian matrix of the fixed point that are less than 1.

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 point. But another use is in order theory, where a partially ordered set P is said to have the fixed point property if every increasing function on P has a fixed point.

In mathematics, the Denjoy–Wolff theorem is a theorem in complex analysis and dynamical systems concerning fixed points and iterations of holomorphic mappings of the unit disc in the complex numbers into itself. The result was proved independently in 1926 by the French mathematician Arnaud Denjoy and the Dutch mathematician Julius Wolff.