Fixed point theorem from Banach

The Banach fixed-point theorem , also known as Banach fixed point theorem called, is a mathematical theorem from functional analysis , a branch of mathematics . It belongs to the fixed point theorems and, in addition to the existence and uniqueness of a fixed point, also provides the convergence of the fixed point iteration . Thus the statement is constructive . A method for determining the fixed point as well as an error estimate for this is given.

With Banach's fixed point theorem, for example, the convergence of iterative methods such as Newton's method can be shown and the Picard-Lindelöf theorem, which is the basis of the existence theory of ordinary differential equations, can be proven .

The set is named after Stefan Banach , who showed it in 1922.

An illustration of the sentence is provided by a map on which the environment in which one is located is depicted. If you see this map as a contraction of the environment, you will find exactly one point on the map that corresponds to the point directly below in the real world.

statement

A complete metric space and a non-empty, closed set are given . Be ${\displaystyle (X,d)}$ ${\displaystyle M\subset X}$

${\displaystyle \varphi \colon M\to M}$

a contraction with contraction number . That means it applies ${\displaystyle k\in [0,1)}$

${\displaystyle d\left(\varphi (x),\varphi (y)\right)\leq k\cdot d(x,y)}$for everyone . ${\displaystyle x,y\in M}$

In addition, let the sequence be iteratively defined by ${\displaystyle (x_{n})_{n\in \mathbb {N} }}$

${\displaystyle x_{n+1}=\varphi (x_{n})}$

for an arbitrary initial value from . ${\displaystyle x_{0}}$ ${\displaystyle M}$

The following applies under the above conditions:

There is exactly one such that ${\displaystyle {\tilde {x}}\in M}$

${\displaystyle \varphi ({\tilde {x}})={\tilde {x}}}$

is. Also applies to all ${\displaystyle x_{0}\in M}$

${\displaystyle \lim _{n\to \infty }x_{n}={\tilde {x}}}$

The mapping therefore has a clearly defined fixed point and this corresponds to the limit value of the iteration for all starting values ​​of the iteration rule specified above. ${\displaystyle \varphi }$

Error estimation of the fixed point iteration

For the iteration rule

${\displaystyle x_{n+1}=\varphi (x_{n})}$

the following error estimates apply:

• A priori error assessment : It is

${\displaystyle d(x_{n},{\tilde {x}})\leq {\frac {k^{n}}{1-k}}d(x_{1},x_{0})}$

• A posteriori error estimation : It is

${\displaystyle d(x_{n+1},{\tilde {x}})\leq {\frac {k}{1-k}}d(x_{n+1},x_{n})}$

In addition, the estimate applies

${\displaystyle d(x_{n+1},{\tilde {x}})\leq k\cdot d(x_{n},{\tilde {x}})}$,

the speed of convergence is therefore linear.

comment

In the literature, there are sometimes formulations that deviate from the statement given above. Possible differences are:

• The property of the image of being a contraction is instead formulated in terms of Lipschitz continuity . Then it has to be Lipschitz-continuous with a Lipschitz constant . ${\displaystyle \varphi }$ ${\displaystyle \varphi }$ ${\displaystyle M}$ ${\displaystyle L=k<1}$
• The underlying room is different. So the sentence is partly formulated on Banach spaces (that is, on completely standardized spaces ) or on . The statement as well as the proof remain identical; it is then only to be set in the case of a normalized space or in the real case. ${\displaystyle \mathbb {R} }$ ${\displaystyle d(x,y)=\|y-x\|}$ ${\displaystyle (X,\|\cdot \|)}$ ${\displaystyle d(x,y)=|y-x|}$

Evidence sketch

The proof of the statement is based on showing that the sequence is a Cauchy sequence , which then converges due to the completeness of the underlying space. ${\displaystyle (x_{n})_{n\in \mathbb {N} }}$

First, due to contractivity

${\displaystyle d(x_{n},x_{n+1})=d\left(\varphi (x_{n-1}),\varphi (x_{n})\right)\leq kd(x_{n-1},x_{n})}$

By repeatedly applying this estimate, one obtains

${\displaystyle d(x_{n},x_{n+1})\leq k^{n}d(x_{0},x_{1})}$ (1)

Furthermore it follows through repeated estimations with the triangle inequality

${\displaystyle d(x_{n},x_{n+m})\leq d(x_{n},x_{n+1})+d(x_{n+1},x_{n+2})+\dots +d(x_{n+m-1},x_{n+m})}$ (2)

If one estimates the individual summation terms on the right-hand side of (2) by (1), one obtains

${\displaystyle d(x_{n},x_{n+m})\leq k^{n}(1+k+k^{2}+\dots +k^{m-1})d(x_{0},x_{1})\leq {\frac {k^{n}}{1-k}}d(x_{0},x_{1})}$

The last estimate follows here with the help of the geometric series , da . It follows directly from the estimate that it is a Cauchy sequence. The limit value then exists due to the completeness ${\displaystyle k<1}$ ${\displaystyle (x_{n})_{n\in \mathbb {N} }}$

${\displaystyle {\tilde {x}}:=\lim _{n\to \infty }x_{n}}$

the consequence. Since there is a picture of in itself, and is complete, is contained in the multitude . ${\displaystyle \varphi }$ ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle {\tilde {x}}}$ ${\displaystyle M}$

Since is continuous (since it is contractive), it follows ${\displaystyle \varphi }$

${\displaystyle {\tilde {x}}=\lim _{n\to \infty }x_{n}=\lim _{n\to \infty }\varphi (x_{n-1})=\varphi ({\tilde {x}})}$,

the limit value is therefore a fixed point. ${\displaystyle {\tilde {x}}}$

Suppose there are two fixed points . Then ${\displaystyle {\tilde {x}},{\tilde {y}}}$

${\displaystyle \varphi ({\tilde {x}})={\tilde {x}}}$and . ${\displaystyle \varphi ({\tilde {y}})={\tilde {y}}}$

It then follows from the contractivity

${\displaystyle d({\tilde {x}},{\tilde {y}})=d(\varphi ({\tilde {x}}),\varphi ({\tilde {y}}))\leq k\cdot d({\tilde {x}},{\tilde {y}})}$.

But there must be. Hence is . ${\displaystyle k<1}$ ${\displaystyle d({\tilde {x}},{\tilde {y}})=0}$ ${\displaystyle {\tilde {x}}={\tilde {y}}}$

Applications

This theorem is used in many constructive theorems of calculus, the most important of which are:

• the inverse and implicit function theorem
• the existence and uniqueness Picard-Lindelöf theorem for ordinary differential equations

In the numerical analysis the Fixed Point plays an important role. Examples of this are the convergence theories of numerical methods, such as the Newton method or the splitting method .

reversal

The following also as a set of Bessaga known statement represents a reversal of the fixed-point theorem is:

• Is a function on a non-empty set, so and all iterates have exactly one fixed point, as there is for every complete metric on so that respect. Contraction with contraction constant is. ${\displaystyle \varphi :M\rightarrow M}$ ${\displaystyle \varphi }$ ${\displaystyle \varphi ^{n}}$ ${\displaystyle k\in (0,1)}$ ${\displaystyle d_{k}}$ ${\displaystyle M}$ ${\displaystyle \varphi }$ ${\displaystyle d_{k}}$ ${\displaystyle k}$

literature

• Hans-Rudolf Schwarz, Norbert Köckler: Numerical Mathematics. 5th, revised edition. Teubner, Stuttgart et al. 2004, ISBN 3-519-42960-8 .
• Otto Forster : Analysis 2 . Differential calculus im , ordinary differential equations. 10th, improved edition. Springer Spectrum, Wiesbaden 2013, ISBN 978-3-658-02356-0 , doi : 10.1007 / 978-3-658-02357-7 . ${\displaystyle \mathbb {R} ^{n}}$
• Dirk Werner : Functional Analysis . 7th, corrected and enlarged edition. Springer-Verlag, Heidelberg Dordrecht London New York 2011, ISBN 978-3-642-21016-7 , doi : 10.1007 / 978-3-642-21017-4 .

Individual evidence

1. ^ Werner: Functional Analysis. 2011, p. 197.
2. ↑ William A. Kirk, Brailey Sims (ed.): Handbook of Metric Fixed Point Theory. Kluwer, Dordrecht et al. 2001, ISBN 0-7923-7073-2 , Theorem 8.1.