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 of metric spaces, and provides a constructive method to find those fixed points. The theorem is named after Stefan Banach (1892-1945), and was first stated by Banach in 1922. In mathematics, a fixed-point theorem is a result saying that a function will have at least one fixed point, under some conditions on that can be stated in general term. ... In mathematics, a metric space is a set where a notion of distance between elements of the set is defined. ... In mathematics, a fixed point (sometimes shortened to fixpoint) of a function is a point that is mapped to itself by the function. ... Stefan Banach Stefan Banach (March 30, 1892 in Kraków, Austria-Hungary now Poland– August 31, 1945 in Lwów, Soviet Union - occupied Poland), was an eminent Polish mathematician, one of the moving spirits of the Lwów School of Mathematics in pre-war Poland. ... 1922 (MCMXXII) was a common year starting on Sunday (see link for calendar). ...

The theorem

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 In mathematical analysis, a metric space M is said to be complete (or Cauchy) if every Cauchy sequence of points in M has a limit that is also in M. Intuitively, a space is complete if it doesnt have any holes, if there arent any points missing. For... In mathematics, a contraction mapping, or contraction, on a metric space (M,d) is a function f from M to itself, with the property that there is some real number such that, for all x and y in M, The smallest such value of k is called the Lipschitz constant... In mathematics, the set of real numbers, denoted R, or in blackboard bold , is the set of all rational and irrational numbers. ...

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 x₀ in X and define an iterative sequence by x_n = Tx_n-1 for n = 1, 2, 3, ... This sequence converges, and its limit is x^*. The following inequality describes the speed of convergence: An iterative method attempts to solve a problem (for example an equation or system of equations) by finding successive approximations to the solution starting from an initial guess. ... In mathematics, the concept of a limit is used to describe the behavior of a function as its argument either gets close to some point, or as it becomes arbitrarily large; or the behavior of a sequences elements, as their index increases indefinitely. ...

.

Equivalently,

and

.

The smallest such value of q is sometimes called the Lipschitz constant. In mathematics, a contraction mapping, or contraction, on a metric space (M,d) is a function f from M to itself, with the property that there is some real number k < 1 such that, for all x and y in M, The smallest such value of k is called the...

Note that the requirement d(Tx, Ty) < d(x, y) for all unequal x and y is in general not enough to ensure the existence of a fixed point, as is shown by the map T : [1,∞) → [1,∞) with T(x) = x + 1/x, which lacks a fixed point. However, if the space X is compact, then this weaker assumption does imply all the statements of the theorem. In mathematics, a subset of Euclidean space Rn is called compact if it is closed and bounded. ...

When using the theorem in practice, the most difficult part is typically to define X properly so that T actually maps elements from X to X, i.e. that Tx is always an element of X.

Proof

Choose any . For each , define . We claim that for all , the following is true:

.

To show this, we will proceed using induction. The above statement is true for the case , for

.

Suppose the above statement holds for some . Then we have

	.

The inductive assumption is used going from line three to line four. By the principle of mathematical induction, for all , the above claim is true. Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers. ...

Let . Since , we can find a large so that

.

Using the claim above, we have that for any , with ,

	.

The inequality in line one follows from repeated applications of the triangle inequality; the series in line four is a geometric series with and hence it converges. The above shows that is a Cauchy sequence in and hence convergent by completeness. So let . We make two claims: (1) is a fixed point of . That is, ; (2) is the only fixed point of in . In mathematics, triangle inequality is the theorem stating that for any triangle, the measure of a given side must be less than the sum of the other two sides but greater than the difference between the two sides. ... In mathematics, a geometric progression is a sequence of numbers such that the quotient of any two successive members of the sequence is a constant called the common ratio of the sequence. ... In mathematical analysis, a Cauchy sequence, named after Augustin Cauchy, is a sequence whose elements become close as the sequence progresses. ... In mathematics, a fixed point of a function f is an argument x such that f(x) = x; see fixed point (mathematics). ...

To see (1), we note that for any ,

.

Since as , the squeeze theorem shows that . This shows that as . But as , and limits are unique; hence it must be the case that . In calculus, the squeeze theorem, (also known as the pinching theorem or sandwich theorem) is a theorem regarding the limit of a function. ...

To show (2), we suppose that also satisfies . Then

.

Remembering that , the above implies that , which shows that , whence by positive definiteness, and the proof is complete. In mathematics, a definite bilinear form B is one for which B(v, v) has a fixed sign (positive or negative) when v is not 0. ...

Applications

A standard application is the proof of the Picard-Lindelöf theorem about the existence and uniqueness of solutions to certain ordinary differential equations. The sought solution of the differential equation is expressed as a fixed point of a suitable integral operator which transforms continuous functions into continuous functions. The Banach fixed point theorem is then used to show that this integral operator has a unique fixed point. In mathematics, the Picard-Lindelöf theorem on existence and uniqueness of solutions of differential equations (Picard 1890, Lindelöf 1894) states that an initial value problem has exactly one solution if f is Lipschitz continuous in , continuous in as long as stays bounded. ... In mathematics, an ordinary differential equation (or ODE) is a relation that contains functions of only one independent variable, and one or more of its derivatives with respect to that variable. ...

Converses

Several converses of the Banach contraction principle exist. The following is due to Czeslaw Bessaga, from 1959: 1959 (MCMLIX) was a common year starting on Thursday of the Gregorian calendar. ...

Let be a map of an abstract set such that each iterate f ⁿ has a unique fixed point. Let q be a real number, 0 < q < 1. Then there exists a complete metric on X such that f is contractive, and q is the contraction constant. This article is about sets in mathematics. ... In mathematics, iterated functions are the objects of study in fractals and dynamical systems. ...

Generalizations

See the article on fixed point theorems in infinite-dimensional spaces for generalizations. In mathematics, a number of fixed point theorems in infinite-dimensional spaces generalise the Brouwer fixed point theorem. ...

References

• Vasile I. Istratescu, Fixed Point Theory, An Introduction, D.Reidel, the Netherlands (1981). ISBN 90-277-1224-7 See chapter 7.
• Andrzej Granas and James Dugundji, Fixed Point Theory (2003) Springer-Verlag, New York, ISBN 0-387-00173-5.
• William A. Kirk and Brailey Sims, Handbook of Metric Fixed Point Theory (2001), Kluwer Academic, London ISBN 0-7923-7073-2.

An earlier version of this article was posted on Planet Math. This article is open content. Open content, coined by analogy with open source, (though technically it is actually share-alike) describes any kind of creative work including articles, pictures, audio, and video that is published in a format that explicitly allows the copying of the information. ...