Contraction Mapping Theorem / Simple iteration

Printable View

July 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!
July 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}|< ...
July 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$
July 19th 2010, 06:47 AM
Also sprach Zarathustra

By the way... g(x) is L Lipschitz function...
July 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.
July 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
July 20th 2010, 05:16 AM
Mollier

Just what I needed mate, thanks!