Fixed point theorem

Fixed point theorem

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

Fixed point theorem in analysis

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.

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).

For example, the cosine function is continuous in [-1,1] and maps it into [-1, 1] , and thus must have a fixed point. This is clear when examining a sketched graph of the cosine function; the fixed point occurs where the cosine curve y=cos(x) intersects the line y=x. Numerically, the fixed point is approximately x=0.73908513321516 (thus x=cos(x)).

The Lefschetz fixed-point theorem (and the Nielsen fixed-point theorem) from algebraic topology is notable because it gives, in some sense, a way to count fixed points.

There are a number of generalisations to Banach spaces and further; these are applied in PDE theory. See fixed point theorems in infinite-dimensional spaces.

The collage theorem in fractal compression proves that, for many images, there exists a relatively small description of a function that, when iteratively applied to any starting image, rapidly converges on the desired image.

Fixed point theorems in discrete mathematics and theoretical computer science

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. See also Bourbaki-Witt theorem.

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.

In denotational semantics of programming languages, a special case of the Knaster-Tarski theorem is used to establish the semantics of recursive definitions. While the fixed point theorem is applied to the "same" function (from a logical point of view), the development of the theory is quite different.

The same definition of recursive function can be given, in computability theory, by applying Kleene's recursion theorem. These results are not equivalent theorems; the Knaster-Tarski theorem is a much stronger result than what is used in denotational semantics. ["The foundations of program verification", 2nd edition, Jacques Loeckx and Kurt Sieber, John Wiley & Sons, ISBN 0 471 91282 4, Chapter 4; theorem 4.24, page 83, is what is used in denotational semantics, while Knaster-Tarski theorem is given to prove as exercise 4.3-5 on page 90.] However, in light of the Church-Turing thesis their intuitive meaning is the same: a recursive function can be described as the least fixed point of a certain functional, mapping functions to functions.

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.

ee also

*Atiyah–Bott fixed-point theorem
*Borel fixed-point theorem
*Brouwer fixed point theorem
*Caristi fixed point theorem
*Diagonal lemma
*Fixed point property
*Injective metric space
*Kakutani fixed-point theorem
*Kleene fixpoint theorem
*Woods Hole fixed-point theorem
*Topological degree theory

Notes

References

*cite book
author = Agarwal, Ravi P.; Meehan, Maria; O'Regan, Donal
title = Fixed Point Theory and Applications
year = 2001
publisher = Cambridge University Press
id = ISBN 0-521-80250-4

*cite book
author = Border, Kim C.
title = Fixed Point Theorems with Applications to Economics and Game Theory
year = 1989
publisher = Cambridge University Press
id = ISBN 0-521-38808-2

*cite book
author = Brown, R. F. (Ed.)
title = Fixed Point Theory and Its Applications
year = 1988
publisher = American Mathematical Society
id = ISBN 0-8218-5080-6

*cite book
author = Dugundji, James; Granas, Andrzej
title = Fixed Point Theory
year = 2003
publisher = Springer-Verlag
id = ISBN 0-387-00173-5

*cite book
author = Kirk, William A.; Goebel, Kazimierz
title = Topics in Metric Fixed Point Theory
year = 1990
publisher = Cambridge University Press
id = ISBN 0-521-38289-0

*cite book
author = Kirk, William A.; Khamsi, Mohamed A.
title = An Introduction to Metric Spaces and Fixed Point Theory
year = 2001
publisher = John Wiley, New York.
id = ISBN 978-0-471-41825-2


*cite book
author = Kirk, William A.; Sims, Brailey
title = Handbook of Metric Fixed Point Theory
year = 2001
publisher = Springer-Verlag
id = ISBN 0-7923-7073-2

*cite book
author = Šaškin, Jurij A; Minachin, Viktor; Mackey, George W.
title = Fixed Points
year = 1991
publisher = American Mathematical Society
id = ISBN 0-8218-9000-X

Links

[http://www.math-linux.com/spip.php?article60 Fixed Point Method]


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • fixed-point theorem — ▪ mathematics       any of various theorems in mathematics dealing with a transformation of the points of a set into points of the same set where it can be proved that at least one point remains fixed. For example, if each real number is squared …   Universalium

  • Kakutani fixed point theorem — 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… …   Wikipedia

  • Brouwer fixed point theorem — In mathematics, the Brouwer fixed point theorem is an important fixed point theorem that applies to finite dimensional spaces and which forms the basis for several general fixed point theorems. It is named after Dutch mathematician L. E. J.… …   Wikipedia

  • Banach fixed-point theorem — In mathematics, the Banach fixed point theorem (also known as the contraction mapping theorem or contraction mapping principle) is an important tool in the theory of metric spaces; it guarantees the existence and uniqueness of fixed points of… …   Wikipedia

  • Banach fixed point theorem — The Banach fixed point theorem (also known as the contraction mapping theorem or contraction mapping principle) is an important tool in the theory of metric spaces; it guarantees the existence and uniqueness of fixed points of certain self maps… …   Wikipedia

  • Lefschetz fixed-point theorem — In mathematics, the Lefschetz fixed point theorem is a formula that counts the number of fixed points of a continuous mapping from a compact topological space X to itself by means of traces of the induced mappings on the homology groups of X . It …   Wikipedia

  • Atiyah–Bott fixed-point theorem — In mathematics, the Atiyah–Bott fixed point theorem, proven by Michael Atiyah and Raoul Bott in the 1960s, is a general form of the Lefschetz fixed point theorem for smooth manifolds M , which uses an elliptic complex on M . This is a system of… …   Wikipedia

  • Caristi fixed point theorem — In mathematics, the Caristi fixed point theorem (also known as the Caristi Kirk fixed point theorem) generalizes the Banach fixed point theorem for maps of a complete metric space into itself. Caristi s fixed point theorem is a variation of the… …   Wikipedia

  • Brouwer's fixed point theorem — ▪ topology       in mathematics, a theorem of algebraic topology (topology) that was stated and proved in 1912 by the Dutch mathematician L.E.J. Brouwer (Brouwer, Luitzen Egbertus Jan). Inspired by earlier work of the French mathematician Henri… …   Universalium

  • Schauder fixed point theorem — The Schauder fixed point theorem is an extension of the Brouwer fixed point theorem to topological vector spaces such as Banach spaces. It asserts that if K is a compact, convex subset of a topological vector space and T is a continuous mapping… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”