Results 1 to 8 of 8

Math Help - Convergence rate

  1. #1
    Senior Member Twig's Avatar
    Joined
    Mar 2008
    From
    Gothenburg
    Posts
    396

    Convergence rate

    Hi

    Not really sure where to post this question, but here we go.

    I need to compute the first several iterations of Newtonīs method for solving
    x^{2}-1=0 , using initial guess x_{0}=10^{6} .

    First things first. How would this be set up?

     \mbox{Newtons method:  }x_{k+1}=x_{k} - \frac{f(x_{k})}{f'(x_{k})}

    Would this give me:

     x_{1}=10^{6}-\frac{(10^{6})^{2}-1}{2\cdot 10^{6}}

    If so, how do I decide in general the apparent convergence rate?
    What should the asymptotic convergence rate be?
    How many iterations are required before the asymptotic convergence is reached?
    Finally, give an analytical explanation of the behavior one observes.

    I donīt even know what asymptotic convergence is.

    Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Twig View Post
    Hi

    Not really sure where to post this question, but here we go.

    I need to compute the first several iterations of Newtonīs method for solving
    x^{2}-1=0 , using initial guess x_{0}=10^{6} .

    First things first. How would this be set up?

     \mbox{Newtons method: }x_{k+1}=x_{k} - \frac{f(x_{k})}{f'(x_{k})}

    Would this give me:

     x_{1}=10^{6}-\frac{(10^{6})^{2}-1}{2\cdot 10^{6}}

    If so, how do I decide in general the apparent convergence rate?
    What should the asymptotic convergence rate be?
    How many iterations are required before the asymptotic convergence is reached?
    Finally, give an analytical explanation of the behavior one observes.

    I donīt even know what asymptotic convergence is.

    Thanks!
    Start by writing x_{n+1} explicitly in terms of x_n

    Only after that worry about anything else.

    CB
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member Twig's Avatar
    Joined
    Mar 2008
    From
    Gothenburg
    Posts
    396

    hi

    hi CB

    I donīt really understand what you mean.
    x_{n+1} \mbox{ explicitly in terms of } x_{n} ?

    Ainīt that just

    x_{n+1}=x_{n}-\frac{x_{n}^{2}-1}{2x_{n}}
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Twig View Post
    hi CB

    I donīt really understand what you mean.
    x_{n+1} \mbox{ explicitly in terms of } x_{n} ?

    Ainīt that just

    x_{n+1}=x_{n}-\frac{x_{n}^{2}-1}{2x_{n}}
    Which is:

    x_{n+1}=\frac{x_n}{2}+\frac{1}{2x_n}

    But your initial value is so large, that for the first few itterations this behaves like:

    x_{n+1}=\frac{x_n}{2}

    CB
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member Twig's Avatar
    Joined
    Mar 2008
    From
    Gothenburg
    Posts
    396

    hi

    Hi CB

    Yeah ok, so what does this tell me about convergence rates? That it is 1/2 ?

    I donīt even know what the word "asymptotic" means
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Twig View Post
    Hi CB

    Yeah ok, so what does this tell me about convergence rates? That it is 1/2 ?

    I donīt even know what the word "asymptotic" means
    It tells you that the initial convergence rate when x_0=10^6 is linear (we know that this is going to go to x_{\infty}=+1).

    That is the error on the n-th iteration is approximately a constant multiple of the error on the n-1 th iteration.

    CB
    Last edited by CaptainBlack; May 3rd 2009 at 10:41 PM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member Twig's Avatar
    Joined
    Mar 2008
    From
    Gothenburg
    Posts
    396
    hey

    So if my function was instead  f(x)=x^{3}+1 , then:

    x_{n+1}= x_{n} - \frac{x_{n}^{3}+1}{3x^{2}}

    Which behaves like  x_{n+1}=\frac{2}{3}x_{n} if x_{n} is large ?

    Is my rate of convergence linear here also?
    Will the error on the n-th iteration be the constant 2/3 times the error on the n-1 th iteration ?

    Thanks!

    PS: Any good links to pages about this subject?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Twig View Post
    hey

    So if my function was instead  f(x)=x^{3}+1 , then:

    x_{n+1}= x_{n} - \frac{x_{n}^{3}+1}{3x^{2}}

    Which behaves like  x_{n+1}=\frac{2}{3}x_{n} if x_{n} is large ?

    Is my rate of convergence linear here also?
    Will the error on the n-th iteration be the constant 2/3 times the error on the n-1 th iteration ?

    Thanks!

    PS: Any good links to pages about this subject?
    Start with x_0=10^6, \varepsilon_0 \approx 10^6, x_1\approx 0.67 \times 10^6 and \varepsilon_1\approx 0.67 \times 10^6 etc

    All this is because the root that this iteration is heading for has |x|=1 \ll x_0 (it is heading for the real root x=-1)

    (Convergence is faster close to the root)

    CB
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Rate of Convergence
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: October 19th 2010, 10:24 PM
  2. rate of convergence
    Posted in the Pre-Calculus Forum
    Replies: 0
    Last Post: May 2nd 2009, 01:18 PM
  3. rate of convergence
    Posted in the Calculus Forum
    Replies: 1
    Last Post: September 14th 2008, 06:50 AM
  4. rate of convergence
    Posted in the Calculus Forum
    Replies: 3
    Last Post: June 30th 2008, 01:55 AM
  5. Rate of Convergence
    Posted in the Calculus Forum
    Replies: 0
    Last Post: March 18th 2008, 06:42 PM

Search Tags


/mathhelpforum @mathhelpforum