Results 1 to 7 of 7

Thread: Contraction Mapping Theorem / Simple iteration

  1. #1
    Member Mollier's Avatar
    Joined
    Nov 2009
    From
    Norway
    Posts
    234
    Awards
    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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1
    L|x_{k-1} - h|<L*L|x_{k-2}-h}|<L*L*L|x_{k-3}-h}|< ...
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member Dinkydoe's Avatar
    Joined
    Dec 2009
    Posts
    411
    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 $
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1
    By the way... g(x) is L Lipschitz function...
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member Mollier's Avatar
    Joined
    Nov 2009
    From
    Norway
    Posts
    234
    Awards
    1
    Quote Originally Posted by Dinkydoe View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member Dinkydoe's Avatar
    Joined
    Dec 2009
    Posts
    411
    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
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member Mollier's Avatar
    Joined
    Nov 2009
    From
    Norway
    Posts
    234
    Awards
    1
    Just what I needed mate, thanks!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Contraction mapping theorem
    Posted in the Advanced Math Topics Forum
    Replies: 20
    Last Post: Nov 9th 2011, 01:10 AM
  2. Contraction Mapping.
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: Jul 30th 2011, 07:38 AM
  3. Contraction mapping theorem
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: Feb 20th 2011, 08:10 PM
  4. Contraction mapping theorem
    Posted in the Differential Geometry Forum
    Replies: 6
    Last Post: Nov 28th 2010, 08:20 PM
  5. Help with Theorem - Local Contraction Mapping
    Posted in the Calculus Forum
    Replies: 0
    Last Post: Aug 5th 2010, 09:27 PM

Search Tags


/mathhelpforum @mathhelpforum