Fixed point (mathematics)

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search
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.

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

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

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

  • 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[edit]

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

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

Notes[edit]

  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" (PDF). 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

External links[edit]