# Contraction Mapping Theorem / Simple iteration

• Jul 19th 2010, 04:32 AM
Mollier
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 $g$ is a real-valued function, defined and continuous on a bounded closed interval $[a,b]$ of the real line, and assume that $g(x)\in [a,b]$ for all $x\in [a,b]$. Given that $x_0\in [a,b]$, the recursion defined by
$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 $[a,b]$. Then, $g$ has a unique fixed point $\xi$ in the interval $[a,b]$. Moreover the sequence $(x_k)$ defined above converges to $\xi$ as $k\rightarrow \infty$ for any starting value $x_0$ in $[a,b]$.

First of all, I don't really understand the simple iteration. I see that because $g(x)\in [a,b]$ for all $x\in [a,b]$, then there exists a number $\xi\in [a,b]$ such that $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 $g$ has a unique fixed point $\xi$ in the interval $[a,b]$. However, I do not understand how it implies that the recursive sequence converges to $\xi$ as $k\rightarrow \infty$.
The proof of this is given in the book and is as follows;

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

we then deduce by induction that

$|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!
• Jul 19th 2010, 04:37 AM
Also sprach Zarathustra
L|x_{k-1} - h|<L*L|x_{k-2}-h}|<L*L*L|x_{k-3}-h}|< ...
• Jul 19th 2010, 06:32 AM
Dinkydoe
Quote:

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 $g(x)-x$ is continuous as well. Moreover $g(a)-a\geq 0$ and $g(b)-b\leq 0$. By the itermediate value theorem $g(\zeta)-\zeta = 0$ for some $\zeta\in [a,b]$. Hence $\zeta$ is a fixpoint of g.

Quote:

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

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

If we let $\zeta$ our fixpoint then:

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

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

And since $L < 1$ and $k\to \infty$ it's clear that $|x_k-\zeta| \to 0$, hence why $x_k\to \zeta$
• Jul 19th 2010, 06:47 AM
Also sprach Zarathustra
By the way... g(x) is L Lipschitz function...
• Jul 19th 2010, 08:30 PM
Mollier
Quote:

Originally Posted by Dinkydoe
Since g is continuous $g(x)-x$ is continuous as well. Moreover $g(a)-a\geq 0$ and $g(b)-b\leq 0$. By the itermediate value theorem $g(\zeta)-\zeta = 0$ for some $\zeta\in [a,b]$. Hence $\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.
$x_{k+1}=g(x_k}$ tells me that if $x_k\in [a,b]$ then $x_{k-1}\in [a,b]$. I don't see why $x_{k+1}=g(x_k}$..

The rest of what you wrote is crystal clear, thank you very much.
• Jul 20th 2010, 05:02 AM
Dinkydoe
Quote:

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 $g(x) \in [a,b]$ for all $x\in [a,b]$. Starting with some point $x_0\in [a,b]$ we can define a sequence by $x_{k+1}= g(x_k)$.

We get a sequence:

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

$\cdots$

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

$\cdots$

And the contraction mapping theorem then gives that this sequence $(x_k)$ converges to $\zeta$, the fixpoint of g
• Jul 20th 2010, 05:16 AM
Mollier
Just what I needed mate, thanks!