Results 1 to 6 of 6

Thread: 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
    10
    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 $\displaystyle x_n$ converges to $\displaystyle \scriptstyle L$ as $\displaystyle n\to\infty$, and that means that $\displaystyle x_{n+1}$ also converges to $\displaystyle \scriptstyle L$. So let $\displaystyle n\to\infty$ on both sides of that equation, and it will give you an equation for $\displaystyle \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: Dec 7th 2009, 05:01 PM
  2. simple question - approximating a square root
    Posted in the Calculus Forum
    Replies: 1
    Last Post: Nov 18th 2009, 03:11 PM
  3. Chi Square Algorithm
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: Oct 29th 2009, 01:10 AM
  4. square roots
    Posted in the Algebra Forum
    Replies: 4
    Last Post: Feb 9th 2009, 05:30 AM
  5. square roots
    Posted in the Algebra Forum
    Replies: 3
    Last Post: Dec 16th 2007, 12:26 PM

Search Tags


/mathhelpforum @mathhelpforum