Results 1 to 7 of 7

Math Help - 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 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!
    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 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.

    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
    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 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.
    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 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
    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: November 9th 2011, 02:10 AM
  2. Contraction Mapping.
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: July 30th 2011, 08:38 AM
  3. Contraction mapping theorem
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: February 20th 2011, 09:10 PM
  4. Contraction mapping theorem
    Posted in the Differential Geometry Forum
    Replies: 6
    Last Post: November 28th 2010, 09:20 PM
  5. Help with Theorem - Local Contraction Mapping
    Posted in the Calculus Forum
    Replies: 0
    Last Post: August 5th 2010, 10:27 PM

Search Tags


/mathhelpforum @mathhelpforum