- Banach fixed-point theorem
- Fixed-point theorem
- Fixed-point iteration
- Fixed-point theorems in infinite-dimensional spaces
- Stefan Banach
- Fixed point (mathematics)
- Schauder fixed-point theorem
- Lipschitz continuity
- Caristi fixed-point theorem
- Picard–Lindelöf theorem
- real analysis - Intuition behind the Banach fixed-point theorem ...
- analysis - Understanding the Banach fixed point theorem
- Banach fixed-point theorem - Mathematics Stack Exchange
- What are some easy Banach fixed point theorem applications?
- real analysis - Banach fixed point theorem and inverse function ...
- Banach fixed point theorem - Mathematics Stack Exchange
- Successive approximation (Banach's fixed point theorem)
- Banach Fixed Point Theorem Proof - Mathematics Stack Exchange
- functional analysis - Banach fixed point theorem: an example ...
- Completeness can be omitted from Banach Fixed Point Theorem?
banach fixed point theorem
![[PDF] Banach fixed point theorem and applications | Semantic Scholar](https://res.cloudinary.com/dyadcr1f1/image/fetch/f_auto,q_auto/https%3A%2F%2Fd3i71xaburhd42.cloudfront.net%2F62e486fc8fd27c7ce88929c97d453acf4e902db6%2F7-Figure3-1.png)
![[PDF] Banach fixed point theorem and applications | Semantic Scholar](https://res.cloudinary.com/dyadcr1f1/image/fetch/f_auto,q_auto/https%3A%2F%2Fd3i71xaburhd42.cloudfront.net%2F62e486fc8fd27c7ce88929c97d453acf4e902db6%2F5-Figure2-1.png)
![[PDF] Banach fixed point theorem and applications | Semantic Scholar](https://res.cloudinary.com/dyadcr1f1/image/fetch/f_auto,q_auto/https%3A%2F%2Fd3i71xaburhd42.cloudfront.net%2F62e486fc8fd27c7ce88929c97d453acf4e902db6%2F7-Figure4-1.png)
Banach fixed-point theorem GudangMovies21 Rebahinxxi LK21
In mathematics, the Banach fixed-point theorem (also known as the contraction mapping theorem or contractive mapping theorem or Banach–Caccioppoli theorem) 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. It can be understood as an abstract formulation of Picard's method of successive approximations. The theorem is named after Stefan Banach (1892–1945) who first stated it in 1922.
Statement
Definition. Let
(
X
,
d
)
{\displaystyle (X,d)}
be a metric space. Then a map
T
:
X
→
X
{\displaystyle T:X\to X}
is called a contraction mapping on X if there exists
q
∈
[
0
,
1
)
{\displaystyle q\in [0,1)}
such that
d
(
T
(
x
)
,
T
(
y
)
)
≤
q
d
(
x
,
y
)
{\displaystyle d(T(x),T(y))\leq qd(x,y)}
for all
x
,
y
∈
X
.
{\displaystyle x,y\in X.}
Banach fixed-point theorem. Let
(
X
,
d
)
{\displaystyle (X,d)}
be a non-empty complete metric space with a contraction mapping
T
:
X
→
X
.
{\displaystyle T:X\to X.}
Then T admits a unique fixed-point
x
∗
{\displaystyle x^{*}}
in X (i.e.
T
(
x
∗
)
=
x
∗
{\displaystyle T(x^{*})=x^{*}}
). Furthermore,
x
∗
{\displaystyle x^{*}}
can be found as follows: start with an arbitrary element
x
0
∈
X
{\displaystyle x_{0}\in X}
and define a sequence
(
x
n
)
n
∈
N
{\displaystyle (x_{n})_{n\in \mathbb {N} }}
by
x
n
=
T
(
x
n
−
1
)
{\displaystyle x_{n}=T(x_{n-1})}
for
n
≥
1.
{\displaystyle n\geq 1.}
Then
lim
n
→
∞
x
n
=
x
∗
{\displaystyle \lim _{n\to \infty }x_{n}=x^{*}}
.
Remark 1. The following inequalities are equivalent and describe the speed of convergence:
d
(
x
∗
,
x
n
)
≤
q
n
1
−
q
d
(
x
1
,
x
0
)
,
d
(
x
∗
,
x
n
+
1
)
≤
q
1
−
q
d
(
x
n
+
1
,
x
n
)
,
d
(
x
∗
,
x
n
+
1
)
≤
q
d
(
x
∗
,
x
n
)
.
{\displaystyle {\begin{aligned}d(x^{*},x_{n})&\leq {\frac {q^{n}}{1-q}}d(x_{1},x_{0}),\\[5pt]d(x^{*},x_{n+1})&\leq {\frac {q}{1-q}}d(x_{n+1},x_{n}),\\[5pt]d(x^{*},x_{n+1})&\leq qd(x^{*},x_{n}).\end{aligned}}}
Any such value of q is called a Lipschitz constant for
T
{\displaystyle T}
, and the smallest one is sometimes called "the best Lipschitz constant" of
T
{\displaystyle T}
.
Remark 2.
d
(
T
(
x
)
,
T
(
y
)
)
<
d
(
x
,
y
)
{\displaystyle d(T(x),T(y))
for all
x
≠
y
{\displaystyle x\neq y}
is in general not enough to ensure the existence of a fixed point, as is shown by the map
T
:
[
1
,
∞
)
→
[
1
,
∞
)
,
T
(
x
)
=
x
+
1
x
,
{\displaystyle T:[1,\infty )\to [1,\infty ),\,\,T(x)=x+{\tfrac {1}{x}}\,,}
which lacks a fixed point. However, if
X
{\displaystyle X}
is compact, then this weaker assumption does imply the existence and uniqueness of a fixed point, that can be easily found as a minimizer of
d
(
x
,
T
(
x
)
)
{\displaystyle d(x,T(x))}
, indeed, a minimizer exists by compactness, and has to be a fixed point of
T
.
{\displaystyle T.}
It then easily follows that the fixed point is the limit of any sequence of iterations of
T
.
{\displaystyle T.}
Remark 3. When using the theorem in practice, the most difficult part is typically to define
X
{\displaystyle X}
properly so that
T
(
X
)
⊆
X
.
{\displaystyle T(X)\subseteq X.}
Proof
Let
x
0
∈
X
{\displaystyle x_{0}\in X}
be arbitrary and define a sequence
(
x
n
)
n
∈
N
{\displaystyle (x_{n})_{n\in \mathbb {N} }}
by setting
x
n
=
T
(
x
n
−
1
)
{\displaystyle x_{n}=T(x_{n-1})}
. We first note that for all
n
∈
N
,
{\displaystyle n\in \mathbb {N} ,}
we have the inequality
d
(
x
n
+
1
,
x
n
)
≤
q
n
d
(
x
1
,
x
0
)
.
{\displaystyle d(x_{n+1},x_{n})\leq q^{n}d(x_{1},x_{0}).}
This follows by induction on
n
{\displaystyle n}
, using the fact that
T
{\displaystyle T}
is a contraction mapping. Then we can show that
(
x
n
)
n
∈
N
{\displaystyle (x_{n})_{n\in \mathbb {N} }}
is a Cauchy sequence. In particular, let
m
,
n
∈
N
{\displaystyle m,n\in \mathbb {N} }
such that
m
>
n
{\displaystyle m>n}
:
d
(
x
m
,
x
n
)
≤
d
(
x
m
,
x
m
−
1
)
+
d
(
x
m
−
1
,
x
m
−
2
)
+
⋯
+
d
(
x
n
+
1
,
x
n
)
≤
q
m
−
1
d
(
x
1
,
x
0
)
+
q
m
−
2
d
(
x
1
,
x
0
)
+
⋯
+
q
n
d
(
x
1
,
x
0
)
=
q
n
d
(
x
1
,
x
0
)
∑
k
=
0
m
−
n
−
1
q
k
≤
q
n
d
(
x
1
,
x
0
)
∑
k
=
0
∞
q
k
=
q
n
d
(
x
1
,
x
0
)
(
1
1
−
q
)
.
{\displaystyle {\begin{aligned}d(x_{m},x_{n})&\leq d(x_{m},x_{m-1})+d(x_{m-1},x_{m-2})+\cdots +d(x_{n+1},x_{n})\\[5pt]&\leq q^{m-1}d(x_{1},x_{0})+q^{m-2}d(x_{1},x_{0})+\cdots +q^{n}d(x_{1},x_{0})\\[5pt]&=q^{n}d(x_{1},x_{0})\sum _{k=0}^{m-n-1}q^{k}\\[5pt]&\leq q^{n}d(x_{1},x_{0})\sum _{k=0}^{\infty }q^{k}\\[5pt]&=q^{n}d(x_{1},x_{0})\left({\frac {1}{1-q}}\right).\end{aligned}}}
Let
ε
>
0
{\displaystyle \varepsilon >0}
be arbitrary. Since
q
∈
[
0
,
1
)
{\displaystyle q\in [0,1)}
, we can find a large
N
∈
N
{\displaystyle N\in \mathbb {N} }
so that
q
N
<
ε
(
1
−
q
)
d
(
x
1
,
x
0
)
.
{\displaystyle q^{N}<{\frac {\varepsilon (1-q)}{d(x_{1},x_{0})}}.}
Therefore, by choosing
m
{\displaystyle m}
and
n
{\displaystyle n}
greater than
N
{\displaystyle N}
we may write:
d
(
x
m
,
x
n
)
≤
q
n
d
(
x
1
,
x
0
)
(
1
1
−
q
)
<
(
ε
(
1
−
q
)
d
(
x
1
,
x
0
)
)
d
(
x
1
,
x
0
)
(
1
1
−
q
)
=
ε
.
{\displaystyle d(x_{m},x_{n})\leq q^{n}d(x_{1},x_{0})\left({\frac {1}{1-q}}\right)<\left({\frac {\varepsilon (1-q)}{d(x_{1},x_{0})}}\right)d(x_{1},x_{0})\left({\frac {1}{1-q}}\right)=\varepsilon .}
This proves that the sequence
(
x
n
)
n
∈
N
{\displaystyle (x_{n})_{n\in \mathbb {N} }}
is Cauchy. By completeness of
(
X
,
d
)
{\displaystyle (X,d)}
, the sequence has a limit
x
∗
∈
X
.
{\displaystyle x^{*}\in X.}
Furthermore,
x
∗
{\displaystyle x^{*}}
must be a fixed point of
T
{\displaystyle T}
:
x
∗
=
lim
n
→
∞
x
n
=
lim
n
→
∞
T
(
x
n
−
1
)
=
T
(
lim
n
→
∞
x
n
−
1
)
=
T
(
x
∗
)
.
{\displaystyle x^{*}=\lim _{n\to \infty }x_{n}=\lim _{n\to \infty }T(x_{n-1})=T\left(\lim _{n\to \infty }x_{n-1}\right)=T(x^{*}).}
As a contraction mapping,
T
{\displaystyle T}
is continuous, so bringing the limit inside
T
{\displaystyle T}
was justified. Lastly,
T
{\displaystyle T}
cannot have more than one fixed point in
(
X
,
d
)
{\displaystyle (X,d)}
, since any pair of distinct fixed points
p
1
{\displaystyle p_{1}}
and
p
2
{\displaystyle p_{2}}
would contradict the contraction of
T
{\displaystyle T}
:
d
(
T
(
p
1
)
,
T
(
p
2
)
)
=
d
(
p
1
,
p
2
)
>
q
d
(
p
1
,
p
2
)
.
{\displaystyle d(T(p_{1}),T(p_{2}))=d(p_{1},p_{2})>qd(p_{1},p_{2}).}
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 on the space of continuous functions under the uniform norm. The Banach fixed-point theorem is then used to show that this integral operator has a unique fixed point.
One consequence of the Banach fixed-point theorem is that small Lipschitz perturbations of the identity are bi-lipschitz homeomorphisms. Let Ω be an open set of a Banach space E; let I : Ω → E denote the identity (inclusion) map and let g : Ω → E be a Lipschitz map of constant k < 1. Then
Ω′ := (I + g)(Ω) is an open subset of E: precisely, for any x in Ω such that B(x, r) ⊂ Ω one has B((I + g)(x), r(1 − k)) ⊂ Ω′;
I + g : Ω → Ω′ is a bi-Lipschitz homeomorphism;
precisely, (I + g)−1 is still of the form I + h : Ω → Ω′ with h a Lipschitz map of constant k/(1 − k). A direct consequence of this result yields the proof of the inverse function theorem.
It can be used to give sufficient conditions under which Newton's method of successive approximations is guaranteed to work, and similarly for Chebyshev's third-order method.
It can be used to prove existence and uniqueness of solutions to integral equations.
It can be used to give a proof to the Nash embedding theorem.
It can be used to prove existence and uniqueness of solutions to value iteration, policy iteration, and policy evaluation of reinforcement learning.
It can be used to prove existence and uniqueness of an equilibrium in Cournot competition, and other dynamic economic models.
Converses
Several converses of the Banach contraction principle exist. The following is due to Czesław Bessaga, from 1959:
Let f : X → X be a map of an abstract set such that each iterate fn has a unique fixed point. Let
q
∈
(
0
,
1
)
,
{\displaystyle q\in (0,1),}
then there exists a complete metric on X such that f is contractive, and q is the contraction constant.
Indeed, very weak assumptions suffice to obtain such a kind of converse. For example if
f
:
X
→
X
{\displaystyle f:X\to X}
is a map on a T1 topological space with a unique fixed point a, such that for each
x
∈
X
{\displaystyle x\in X}
we have fn(x) → a, then there already exists a metric on X with respect to which f satisfies the conditions of the Banach contraction principle with contraction constant 1/2. In this case the metric is in fact an ultrametric.
Generalizations
There are a number of generalizations (some of which are immediate corollaries).
Let T : X → X be a map on a complete non-empty metric space. Then, for example, some generalizations of the Banach fixed-point theorem are:
Assume that some iterate Tn of T is a contraction. Then T has a unique fixed point.
Assume that for each n, there exist cn such that d(Tn(x), Tn(y)) ≤ cnd(x, y) for all x and y, and that
∑
n
c
n
<
∞
.
{\displaystyle \sum \nolimits _{n}c_{n}<\infty .}
Then T has a unique fixed point.
In applications, the existence and uniqueness of a fixed point often can be shown directly with the standard Banach fixed point theorem, by a suitable choice of the metric that makes the map T a contraction. Indeed, the above result by Bessaga strongly suggests to look for such a metric. See also the article on fixed point theorems in infinite-dimensional spaces for generalizations.
In a non-empty compact metric space, any function
T
{\displaystyle T}
satisfying
d
(
T
(
x
)
,
T
(
y
)
)
<
d
(
x
,
y
)
{\displaystyle d(T(x),T(y))
for all distinct
x
,
y
{\displaystyle x,y}
, has a unique fixed point. The proof is simpler than the Banach theorem, because the function
d
(
T
(
x
)
,
x
)
{\displaystyle d(T(x),x)}
is continuous, and therefore assumes a minimum, which is easily shown to be zero.
A different class of generalizations arise from suitable generalizations of the notion of metric space, e.g. by weakening the defining axioms for the notion of metric. Some of these have applications, e.g., in the theory of programming semantics in theoretical computer science.
Example
An application of the Banach fixed-point theorem and fixed-point iteration can be used to quickly obtain an approximation of π with high accuracy. Consider the function
f
(
x
)
=
sin
(
x
)
+
x
{\displaystyle f(x)=\sin(x)+x}
. It can be verified that π is a fixed point of f, and that f maps the interval
[
3
π
/
4
,
5
π
/
4
]
{\displaystyle \left[3\pi /4,5\pi /4\right]}
to itself. Moreover,
f
′
(
x
)
=
1
+
cos
(
x
)
{\displaystyle f'(x)=1+\cos(x)}
, and it can be verified that
0
≤
1
+
cos
(
x
)
≤
1
−
1
2
<
1
{\displaystyle 0\leq 1+\cos(x)\leq 1-{\frac {1}{\sqrt {2}}}<1}
on this interval. Therefore, by an application of the mean value theorem, f has a Lipschitz constant less than 1 (namely
1
−
1
/
2
{\displaystyle 1-1/{\sqrt {2}}}
). Applying the Banach fixed-point theorem shows that the fixed point π is the unique fixed point on the interval, allowing for fixed-point iteration to be used.
For example, the value 3 may be chosen to start the fixed-point iteration, as
3
π
/
4
≤
3
≤
5
π
/
4
{\displaystyle 3\pi /4\leq 3\leq 5\pi /4}
. The Banach fixed-point theorem may be used to conclude that
π
=
f
(
f
(
f
(
⋯
f
(
3
)
⋯
)
)
)
)
.
{\displaystyle \pi =f(f(f(\cdots f(3)\cdots )))).}
Applying f to 3 only three times already yields an expansion of π accurate to 33 digits:
f
(
f
(
f
(
3
)
)
)
=
3.141592653589793238462643383279502
…
.
{\displaystyle f(f(f(3)))=3.141592653589793238462643383279502\ldots \,.}
See also
Notes
References
Agarwal, Praveen; Jleli, Mohamed; Samet, Bessem (2018). "Banach Contraction Principle and Applications". Fixed Point Theory in Metric Spaces. Singapore: Springer. pp. 1–23. doi:10.1007/978-981-13-2913-5_1. ISBN 978-981-13-2912-8.
Chicone, Carmen (2006). "Contraction". Ordinary Differential Equations with Applications (2nd ed.). New York: Springer. pp. 121–135. ISBN 0-387-30769-9.
Granas, Andrzej; Dugundji, James (2003). Fixed Point Theory. New York: Springer-Verlag. ISBN 0-387-00173-5.
Istrăţescu, Vasile I. (1981). Fixed Point Theory: An Introduction. The Netherlands: D. Reidel. ISBN 90-277-1224-7. See chapter 7.
Kirk, William A.; Khamsi, Mohamed A. (2001). An Introduction to Metric Spaces and Fixed Point Theory. New York: John Wiley. ISBN 0-471-41825-0.
This article incorporates material from Banach fixed point theorem on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.
Kata Kunci Pencarian: banach fixed point theorem
banach fixed point theorem
Daftar Isi
real analysis - Intuition behind the Banach fixed-point theorem ...
The Banach fixed point theorem says that any endo-function shrinking distances sufficiently fast must be the result of such a point pulling things to it. If the space is not complete then that …
analysis - Understanding the Banach fixed point theorem
Dec 17, 2014 · The Banach fixed point theorem is stated in my book (Applied Asymptotic Analysis by Miller) as Let $\mathcal B$ be a Banach space with norm $\|\cdot\|$.
Banach fixed-point theorem - Mathematics Stack Exchange
The well known fixed-point theorem by Banach reads as follows: Let $(X,d)$ be a complete metric space, ...
What are some easy Banach fixed point theorem applications?
Oct 18, 2016 · The Banach Fixed Point Theorem plays an important role in guaranteeing the existence of solutions to common problems in economics. Consider some $\beta \in (0,1)$ as …
real analysis - Banach fixed point theorem and inverse function ...
Hahn-Banach and the Fundamental Theorem of Calculus for Banach-space valued functions 0 The sign determinant of the neighbourhood given by the inverse function theorem
Banach fixed point theorem - Mathematics Stack Exchange
Feb 17, 2016 · generalization of Banach fixed-point theorem on short maps? 2. Converse of Banach fixed-point theorem. 1.
Successive approximation (Banach's fixed point theorem)
Rigorous proof of a unique solution using Banach's Fixed Point Theorem. 1.
Banach Fixed Point Theorem Proof - Mathematics Stack Exchange
Feb 16, 2021 · Stack Exchange Network. Stack Exchange network consists of 183 Q&A communities including Stack Overflow, the largest, most trusted online community for …
functional analysis - Banach fixed point theorem: an example ...
Proof using Banach fixed point theorem. 1. fixed point of a multivalued map. 5. Using the Banach fixed ...
Completeness can be omitted from Banach Fixed Point Theorem?
Apr 25, 2017 · In Kreyszig's Functional Analysis, page no. 303, exercise no. 3 says that completeness cannot be omitted from Banach's Fixed Point Theorem.