Thread: 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.

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

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 converges to as , and that means that also converges to . So let on both sides of that equation, and it will give you an equation for

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?

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

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!