Results 1 to 6 of 6

Math Help - Archimedean Algorithm for Approximating Square Roots

  1. #1
    Member
    Joined
    Mar 2010
    Posts
    144

    Archimedean Algorithm for Approximating Square Roots

    An algorithm for approximating the sqrt (square root) of A is the following: To approximate sqrt A, begin with the initial approximation (obtained by "eyeballing it") of x0. Then, let the next approximation be x1 = ((x0)^2 + A)/(2*x0), then x2 = ((x1)^2 + A)/(2*x1) and generally, use the recursive definition xn+1 = ((xn)^2 + A)/(2*xn).

    Assuming that the sequence of successive approximations converges to a limit L, show that L = sqrt A.

    I think that I need to take limits of both sides of xn+1 = ((xn)^2 + A)/(2*xn). I do not know how I would go about doing this.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    Hint -

    What can you say about
    (sqrt(A) - x_n) and (sqrt(A) - x_n+1)

    It should be a bounded and monotonic sequence and hence will converge
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by MATNTRNG View Post
    Assuming that the sequence of successive approximations converges to a limit L, show that L = sqrt A.

    I think that I need to take limits of both sides of xn+1 = ((xn)^2 + A)/(2*xn).
    Yes, that is exactly what you need to do. You are told that x_n converges to \scriptstyle L as n\to\infty, and that means that x_{n+1} also converges to \scriptstyle L. So let n\to\infty on both sides of that equation, and it will give you an equation for \scriptstyle L.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Mar 2010
    Posts
    144
    I am sorry but I am still not getting anywhere. I have a weak understanding of limits. Would you be so kind as to show me how I would get the equation for L?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    I think what Opalg is suggesting is the in limit n->infinity; x_n = x_n+1 = L (though you have not proved it but that is not needed as this is given in the question)

    Now look at x_n+1 = (x_n^2 + A) / 2*x_n
    In the limit n-> infinity this eq will become
    L = (L^2 + A) / 2L
    solve for L
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Mar 2010
    Posts
    144
    Quote Originally Posted by aman_cc View Post
    I think what Opalg is suggesting is the in limit n->infinity; x_n = x_n+1 = L (though you have not proved it but that is not needed as this is given in the question)

    Now look at x_n+1 = (x_n^2 + A) / 2*x_n
    In the limit n-> infinity this eq will become
    L = (L^2 + A) / 2L
    solve for L
    Thank you so much!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. square roots
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: December 7th 2009, 06:01 PM
  2. simple question - approximating a square root
    Posted in the Calculus Forum
    Replies: 1
    Last Post: November 18th 2009, 04:11 PM
  3. Chi Square Algorithm
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: October 29th 2009, 02:10 AM
  4. square roots
    Posted in the Algebra Forum
    Replies: 4
    Last Post: February 9th 2009, 06:30 AM
  5. square roots
    Posted in the Algebra Forum
    Replies: 3
    Last Post: December 16th 2007, 01:26 PM

Search Tags


/mathhelpforum @mathhelpforum