# Thread: Archimedean Algorithm for Approximating Square Roots

1. ## 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.

2. Hint -

(sqrt(A) - x_n) and (sqrt(A) - x_n+1)

It should be a bounded and monotonic sequence and hence will converge

3. Originally Posted by MATNTRNG
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.$

4. 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?

5. 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

6. Originally Posted by aman_cc
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!