Fixed point (mathematics)

See also fixed-point arithmetic.

In mathematics, a fixed point of a function is a point that is mapped to itself by the function. For example, if f is defined on the real numbers by f(x) = x² − 3x + 4, then 2 is a fixed point of f, because f(2) = 2.

Not all functions have fixed points: for example, the function x -> x+1 has no fixed point on the reals, since x is never equal to x+1 for any real number.

Attractive fixed points

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

x,\ f(x),\ f(f(x)),\ f(f(f(x))),\dots

converges to x₀. How close is "close enough" is sometimes a subtle question.

The natural cosine function ("natural" means in radians, not degrees or other units) has exactly one fixed point, which is attractive. 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. It quickly converges to about 0.73908513, the fixed point. That's where the graph of the cosine function intersects the line y = x, and this is no coincidence.

Not all fixed points are attractive: for example, x=0 is a fixed point of the function x -> x²+x, but iteration of this function for any value other than zero rapidly diverges.

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

Theorems guaranteeing fixed points

The Banach fixed point theorem gives a general criterion guaranteeing that, if it is satisfied, the procedure of iterating a function (as shown above) yields a fixed point.

By contrast, the Brouwer fixed point theorem is a non-constructive result: it 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 (See also Sperner's lemma). The cosine example above fits this theorem as the cosine function is continuous in [-1,1] and maps to [-1, 1], and thus should have a fixed point. There are a number of generalisations to Banach spaces and further; these are applied in PDE theory.

The Knaster-Tarski theorem is somewhat removed from analysis and does not deal with continuous functions. It states that any order-preserving function on a complete lattice has a fixed point, and indeed a smallest fixed point.

A common theme in lambda calculus is to find fixed points of given lambda expressions. Every lambda expression has a fixed point, and a fixed point combinator is a "function" which takes as input a lambda expression and produces as output a fixed point of that expression. An important fixed point combinator is the Y combinator used to give recursive definitions.

The above technique of iterating a function to find a fixed point can also be used in set theory; the fixed-point lemma for normal functions states that any continuous strictly increasing function from ordinals to ordinals has one (and indeed many) fixed points.

Every closure operator on a poset has many fixed points; these are the "closed elements" with respect to the closure operator, and they are the main reason the closure operator was defined in the first place.