All entries for Tuesday 23 October 2007

October 23, 2007

Fixed Point

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.

PhD Comics

October 2007

Mo Tu We Th Fr Sa Su
Sep |  Today  | Nov
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31            

Search this blog


Most recent comments

  • Can't beat a German Market. by on this entry
  • Imagine Shiva in Words by this stotra (Thanks to Ravana) by Yogendra on this entry
  • This is the favorite and most inspiring stothram for me. It invokes the manliness in ourself to rise… by Bhargav on this entry
  • Went last night and it was really good. First time i have been and will definatly return next year. by Mad Dozza on this entry
  • strota really purifies soul by shailendra on this entry

Blog archive

Not signed in
Sign in

Powered by BlogBuilder