# Thread: Contraction Mapping Theorem / Simple iteration

1. ## Contraction Mapping Theorem / Simple iteration

So, I am reading in a introductory numerical analysis book, but I believe my question fits into the calculus forums.

First, the definition of a simple iteration as given in my book:

Suppose that $\displaystyle g$ is a real-valued function, defined and continuous on a bounded closed interval $\displaystyle [a,b]$ of the real line, and assume that $\displaystyle g(x)\in [a,b]$ for all $\displaystyle x\in [a,b]$. Given that $\displaystyle x_0\in [a,b]$, the recursion defined by
$\displaystyle x_{k+1}=g(x_k),\;k=0,1,2,\cdots,$
is called a simple iteration.

Contraction Mapping Theorem:

Let g be as in the definition above. Suppose further, that g is a contraction on $\displaystyle [a,b]$. Then, $\displaystyle g$ has a unique fixed point $\displaystyle \xi$ in the interval $\displaystyle [a,b]$. Moreover the sequence $\displaystyle (x_k)$ defined above converges to $\displaystyle \xi$ as $\displaystyle k\rightarrow \infty$ for any starting value $\displaystyle x_0$ in $\displaystyle [a,b]$.

First of all, I don't really understand the simple iteration. I see that because $\displaystyle g(x)\in [a,b]$ for all $\displaystyle x\in [a,b]$, then there exists a number $\displaystyle \xi\in [a,b]$ such that $\displaystyle g(\xi)=\xi$. It would be great if someone had the time to explain this in more detail.

As for the contraction mapping theorem, I understand how $\displaystyle g$ has a unique fixed point $\displaystyle \xi$ in the interval $\displaystyle [a,b]$. However, I do not understand how it implies that the recursive sequence converges to $\displaystyle \xi$ as $\displaystyle k\rightarrow \infty$.
The proof of this is given in the book and is as follows;

$\displaystyle |x_k-\xi|=|g(x_{k-1})-g(\xi)|\leq L|x_{k-1}-\xi|,\;k\geq 1$

we then deduce by induction that

$\displaystyle |x_k-\xi|\leq L^k|x_0-\xi|,\;k\geq 1$

I do not understand how they come to that last part by induction.

Any help is appreciated. Thanks!

2. L|x_{k-1} - h|<L*L|x_{k-2}-h}|<L*L*L|x_{k-3}-h}|< ...

3. First of all, I don't really understand the simple iteration. I see that because for all , then there exists a number such that . It would be great if someone had the time to explain this in more detail.
Since g is continuous $\displaystyle g(x)-x$ is continuous as well. Moreover $\displaystyle g(a)-a\geq 0$ and $\displaystyle g(b)-b\leq 0$. By the itermediate value theorem $\displaystyle g(\zeta)-\zeta = 0$ for some $\displaystyle \zeta\in [a,b]$. Hence $\displaystyle \zeta$ is a fixpoint of g.

I do not understand how they come to that last part by induction.
Since g is a contraction there exists a real number $\displaystyle L < 1$ such that for all $\displaystyle x,y\in [a,b]$ we have $\displaystyle |g(x)-g(y)|\leq L|x-y|$.

The fact that $\displaystyle L < 1$ is important and the reason why this works.

If we let $\displaystyle \zeta$ our fixpoint then:

$\displaystyle |x_k-\zeta| = |g(x_{k-1})-g(\zeta)| \leq L|x_{k-1}-\zeta|$

$\displaystyle = L|g(x_{k-2})-g(\zeta)|\leq L^2|x_{k-2}-\zeta|=\cdots \leq L^k|x_0-\zeta|$

And since $\displaystyle L < 1$ and $\displaystyle k\to \infty$ it's clear that $\displaystyle |x_k-\zeta| \to 0$, hence why $\displaystyle x_k\to \zeta$

4. By the way... g(x) is L Lipschitz function...

5. Originally Posted by Dinkydoe
Since g is continuous $\displaystyle g(x)-x$ is continuous as well. Moreover $\displaystyle g(a)-a\geq 0$ and $\displaystyle g(b)-b\leq 0$. By the itermediate value theorem $\displaystyle g(\zeta)-\zeta = 0$ for some $\displaystyle \zeta\in [a,b]$. Hence $\displaystyle \zeta$ is a fixpoint of g
Hi,
to me that looks like a proof for Brouwer's Fixed Point Theorem. Perhaps that explains all there is to explain about simple iteration, but I unfortunately don't get it.
$\displaystyle x_{k+1}=g(x_k}$ tells me that if $\displaystyle x_k\in [a,b]$ then $\displaystyle x_{k-1}\in [a,b]$. I don't see why $\displaystyle x_{k+1}=g(x_k}$..

The rest of what you wrote is crystal clear, thank you very much.

6. to me that looks like a proof for Brouwer's Fixed Point Theorem.
That's exactly what it was. I thought you wanted more clarification on the existence of a fixpoint.

About the simple iteration I don't quite understand your problem. It's just a definition.

Given that $\displaystyle g(x) \in [a,b]$ for all $\displaystyle x\in [a,b]$. Starting with some point $\displaystyle x_0\in [a,b]$ we can define a sequence by $\displaystyle x_{k+1}= g(x_k)$.

We get a sequence:

$\displaystyle x_0$
$\displaystyle x_1=g(x_0)$
$\displaystyle x_2=g(g(x_0))= g(x_1)$
$\displaystyle x_3=g(g(g(x_0)))= g(x_2)$

$\displaystyle \cdots$

$\displaystyle x_k= g^{(k)}(x_0) = g(x_{k-1})$

$\displaystyle \cdots$

And the contraction mapping theorem then gives that this sequence $\displaystyle (x_k)$ converges to $\displaystyle \zeta$, the fixpoint of g

7. Just what I needed mate, thanks!