All entries for Tuesday 23 October 2007
October 23, 2007
In mathematics, a fixed point (sometimes shortened to fixpoint) of a function is a point that is mapped to itself by the function. [More]
The Banach fixed point theorem gives a general criterion guaranteeing that, if it is satisfied, the procedure of iterating a function yields a fixed point. The banach fixed point theorem statement is the following.
Let (X, d) be a non-empty complete metric space. Let T : X → X be a contraction mapping on X, i.e: there is a nonnegative real number q < 1 such that
d(Tx,Ty) \le q\cdot d(x,y), for all x, y in X.
Then the map T admits one and only one fixed point x* in X (this means Tx* = x*).
Furthermore, this fixed point can be found as follows: start with an arbitrary element x0 in X and define an iterative sequence by xn = Txn-1 for n = 1, 2, 3, ... This sequence converges, and its limit is x*.
The proof follows from the fact that for every x, the sequence (x, f(x), f(f(x)), ... ) is a cauchy sequence and hence convergent by completeness. The limit of the sequence is the fixed-point. It is easy to show that the fixed-point is unique.
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.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. Formally the statement is the following:
Let L be a complete lattice and let f : L → L be an order-preserving function. Then the set of fixed points of f in L is also a complete lattice.
Since complete lattices cannot be empty, the theorem in particular guarantees the existence of at least one fixed point of f, and even the existence of a least (or greatest) fixed point.