Banach fixed-point theorem

<h2 id="statement">Statement</h2>
Definition. Let 
 
 
 
 (
 X
 ,
 d
 )
 
 
 {\displaystyle (X,d)}
 
 be a <a href="/facts/Metric_space/gnBBRXtc">metric space</a>. Then a map 
 
 
 
 T
 :
 X
 →
 X
 
 
 {\displaystyle T:X\to X}
 
 is called a <a href="/facts/Contraction_mapping/VSu4qNqa">contraction mapping</a> 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.}

<blockquote>
Banach fixed-point theorem. Let 
 
 
 
 (
 X
 ,
 d
 )
 
 
 {\displaystyle (X,d)}
 
 be a non-<a href="/facts/Empty_set/ffEk3eA6">empty</a> <a href="/facts/Complete_metric_space/lsckmU8G">complete metric space</a> with a contraction mapping 
 
 
 
 T
 :
 X
 →
 X
 .
 
 
 {\displaystyle T:X\to X.}
 
 Then T admits a unique <a href="/facts/Fixed_point_(mathematics)/vVVddTKc">fixed-point</a> 
 
 
 
 
 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 <a href="/facts/Sequence/gV2S4uqp">sequence</a> 
 
 
 
 (
 
 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^{*}}
 
.</blockquote>
Remark 1. The following inequalities are equivalent and describe the <a href="/facts/Rate_of_convergence/JVGuzPoS">speed of convergence</a>:

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 <a href="/facts/Lipschitz_constant/Hw20EPEU">Lipschitz constant</a> 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))<d(x,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 <a href="/facts/Compact_space/d0cgXJH7">compact</a>, 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.}

<h2 id="proof">Proof</h2>
Let 
 
 
 
 
 x
 
 0
 
 
 ∈
 X
 
 
 {\displaystyle x_{0}\in X}
 
 be arbitrary and define a <a href="/facts/Sequence/gV2S4uqp">sequence</a> 
 
 
 
 (
 
 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 <a href="/facts/Principle_of_mathematical_induction/KxAPqNrH">induction</a> 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 <a href="/facts/Cauchy_sequence/7Q5c8TuF">Cauchy sequence</a>. 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 <a href="/facts/Fixed_point_(mathematics)/vVVddTKc">fixed point</a> 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}).}

<h2 id="applications">Applications</h2>
<ul><li>A standard application is the proof of the <a href="/facts/Picard%25E2%2580%2593Lindel%25C3%25B6f_theorem/yKHSWoMJ">Picard–Lindelöf theorem</a> about the existence and uniqueness of solutions to certain <a href="/facts/Ordinary_differential_equation/ygKGQ8kD">ordinary differential equations</a>. 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 <a href="/facts/Uniform_norm/5yIkjNE3">uniform norm</a>. The Banach fixed-point theorem is then used to show that this integral operator has a unique fixed point.</li>
<li>One consequence of the Banach fixed-point theorem is that small Lipschitz perturbations of the identity are <a href="/facts/Lipschitz_continuity/Hw20EPEU">bi-lipschitz</a> 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</li></ul>
<ol><li>Ω′ := (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)) ⊂ Ω′;</li>
<li>I + g : Ω → Ω′ is a bi-Lipschitz homeomorphism;</li></ol>
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 <a href="/facts/Inverse_function_theorem/pIwcyc6X">inverse function theorem</a>.
<ul><li>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.</li>
<li>It can be used to prove existence and uniqueness of solutions to integral equations.</li>
<li>It can be used to give a proof to the <a href="/facts/Nash_embedding_theorem/a7eLrRLM">Nash embedding theorem</a>.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a></li>
<li>It can be used to prove existence and uniqueness of solutions to value iteration, policy iteration, and policy evaluation of <a href="/facts/Reinforcement_learning/NrgPPS0Q">reinforcement learning</a>.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a></li>
<li>It can be used to prove existence and uniqueness of an equilibrium in <a href="/facts/Cournot_competition/lLxXk8e7">Cournot competition</a>,<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a> and other dynamic economic models.<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a></li></ul>
<h2 id="converses">Converses</h2>
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 <a href="/facts/Set_(mathematics)/BfucfHMq">set</a> such that each <a href="/facts/Iterated_function/Vzsx64An">iterate</a> 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 <a href="/facts/T1_space/K4exfuf7">T1 topological space</a> with a unique <a href="/facts/Fixed_point_(mathematics)/vVVddTKc">fixed point</a> 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.<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a> In this case the metric is in fact an <a href="/facts/Ultrametric/QhJQBG9N">ultrametric</a>.

<h2 id="generalizations">Generalizations</h2>
There are a number of generalizations (some of which are immediate <a href="/facts/Corollary/ntQ8zR9N">corollaries</a>).<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a>
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:

<ul><li>Assume that some iterate Tn of T is a contraction. Then T has a unique fixed point.</li>
<li>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</li></ul>

∑
 
 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 <a href="/facts/Fixed_point_theorems_in_infinite-dimensional_spaces/4rJmoRml">fixed point theorems in infinite-dimensional spaces</a> for generalizations.
In a non-empty <a href="/facts/Compact_metric_space/gnBBRXtc">compact metric space</a>, any function 
 
 
 
 T
 
 
 {\displaystyle T}
 
 satisfying 
 
 
 
 d
 (
 T
 (
 x
 )
 ,
 T
 (
 y
 )
 )
 <
 d
 (
 x
 ,
 y
 )
 
 
 {\displaystyle d(T(x),T(y))<d(x,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 <a href="/facts/Metric_space/gnBBRXtc">metric space</a>, e.g. by weakening the defining axioms for the notion of metric.<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a> Some of these have applications, e.g., in the theory of programming semantics in theoretical computer science.<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a>

<h2 id="example">Example</h2>
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 <a href="/facts/Mean_value_theorem/JnjkzQb4">mean value theorem</a>, 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 \,.}

<ul><li><a href="/facts/Brouwer_fixed-point_theorem/xP2p03lQ">Brouwer fixed-point theorem</a></li>
<li><a href="/facts/Caristi_fixed-point_theorem/dGT4IIzP">Caristi fixed-point theorem</a></li>
<li><a href="/facts/Contraction_mapping/VSu4qNqa">Contraction mapping</a></li>
<li><a href="/facts/Fichera%2527s_existence_principle/nCMIAPPz">Fichera's existence principle</a></li>
<li><a href="/facts/Fixed-point_iteration/05dQGazd">Fixed-point iteration</a></li>
<li><a href="/facts/Fixed-point_theorem/Jvkz4SUu">Fixed-point theorems</a></li>
<li><a href="/facts/Infinite_compositions_of_analytic_functions/N1JmTkaT">Infinite compositions of analytic functions</a></li>
<li><a href="/facts/Kantorovich_theorem/Grtj9yBF">Kantorovich theorem</a></li></ul>

<h2 id="notes">Notes</h2>

<ul><li>Agarwal, Praveen; Jleli, Mohamed; Samet, Bessem (2018). "Banach Contraction Principle and Applications". Fixed Point Theory in Metric Spaces. Singapore: Springer. pp. 1–23. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2F978-981-13-2913-5_1">10.1007/978-981-13-2913-5_1</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-981-13-2912-8.</li>
<li>Chicone, Carmen (2006). <a href="https://books.google.com/books?id=yfY2uGROVrUC&pg=PA121">"Contraction"</a>. Ordinary Differential Equations with Applications (2nd ed.). New York: Springer. pp. 121–135. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-387-30769-9.</li>
<li>Granas, Andrzej; <a href="/facts/James_Dugundji/xCy4DgGy">Dugundji, James</a> (2003). Fixed Point Theory. New York: Springer-Verlag. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-387-00173-5.</li>
<li>Istrăţescu, Vasile I. (1981). Fixed Point Theory: An Introduction. The Netherlands: D. Reidel. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 90-277-1224-7. See chapter 7.</li>
<li>Kirk, William A.; Khamsi, Mohamed A. (2001). An Introduction to Metric Spaces and Fixed Point Theory. New York: John Wiley. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-471-41825-0.</li></ul>
This article incorporates material from <a href="https://planetmath.org/banachfixedpointtheorem">Banach fixed point theorem</a> on <a href="/facts/PlanetMath/wphPCtLf">PlanetMath</a>, which is licensed under the Creative Commons Attribution/Share-Alike License.

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Kinderlehrer, David; Stampacchia, Guido (1980). "Variational Inequalities in RN". An Introduction to Variational Inequalities and Their Applications. New York: Academic Press. pp. 7–22. ISBN 0-12-407350-6. <a href="0-12-407350-6" target="_blank">0-12-407350-6</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Banach, Stefan (1922). "Sur les opérations dans les ensembles abstraits et leur application aux équations intégrales" (PDF). Fundamenta Mathematicae. 3: 133–181. doi:10.4064/fm-3-1-133-181. Archived (PDF) from the original on 2011-06-07. <a href="/wiki/Stefan_Banach" target="_blank">/wiki/Stefan_Banach</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Ciesielski, Krzysztof (2007). "On Stefan Banach and some of his results" (PDF). Banach J. Math. Anal. 1 (1): 1–10. doi:10.15352/bjma/1240321550. Archived (PDF) from the original on 2009-05-30. <a href="http://www.emis.de/journals/BJMA/tex_v1_n1_a1.pdf" target="_blank">http://www.emis.de/journals/BJMA/tex_v1_n1_a1.pdf</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Günther, Matthias (1989). "Zum Einbettungssatz von J. Nash" [On the embedding theorem of J. Nash]. Mathematische Nachrichten (in German). 144: 165–187. doi:10.1002/mana.19891440113. MR 1037168. <a href="/wiki/Mathematische_Nachrichten" target="_blank">/wiki/Mathematische_Nachrichten</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Lewis, Frank L.; Vrabie, Draguna; Syrmos, Vassilis L. (2012). "Reinforcement Learning and Optimal Adaptive Control". Optimal Control. New York: John Wiley & Sons. pp. 461–517 [p. 474]. ISBN 978-1-118-12272-3. <a href="978-1-118-12272-3" target="_blank">978-1-118-12272-3</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Long, Ngo Van; Soubeyran, Antoine (2000). "Existence and Uniqueness of Cournot Equilibrium: A Contraction Mapping Approach" (PDF). Economics Letters. 67 (3): 345–348. doi:10.1016/S0165-1765(00)00211-1. Archived (PDF) from the original on 2004-12-30. <a href="https://www.cirano.qc.ca/pdf/publication/99s-22.pdf" target="_blank">https://www.cirano.qc.ca/pdf/publication/99s-22.pdf</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Stokey, Nancy L.; Lucas, Robert E. Jr. (1989). Recursive Methods in Economic Dynamics. Cambridge: Harvard University Press. pp. 508–516. ISBN 0-674-75096-9. <a href="0-674-75096-9" target="_blank">0-674-75096-9</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Hitzler, Pascal; Seda, Anthony K. (2001). "A 'Converse' of the Banach Contraction Mapping Theorem". Journal of Electrical Engineering. 52 (10/s): 3–6. <a href="/wiki/Pascal_Hitzler" target="_blank">/wiki/Pascal_Hitzler</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Latif, Abdul (2014). "Banach Contraction Principle and its Generalizations". Topics in Fixed Point Theory. Springer. pp. 33–64. doi:10.1007/978-3-319-01586-6_2. ISBN 978-3-319-01585-9. <a href="978-3-319-01585-9" target="_blank">978-3-319-01585-9</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Hitzler, Pascal; Seda, Anthony (2010). Mathematical Aspects of Logic Programming Semantics. Chapman and Hall/CRC. ISBN 978-1-4398-2961-5. <a href="978-1-4398-2961-5" target="_blank">978-1-4398-2961-5</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Seda, Anthony K.; Hitzler, Pascal (2010). "Generalized Distance Functions in the Theory of Computation". The Computer Journal. 53 (4): 443–464. doi:10.1093/comjnl/bxm108. <a href="/wiki/Pascal_Hitzler" target="_blank">/wiki/Pascal_Hitzler</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
</ol>

Banach fixed-point theorem open-in-new

Banach fixed-point theorem