How do you prove that the square root of a number S can be approximated by using the recurrence relation: x_(n+1) = 1/2(x_n+S/x_n) ?

Not sure how to prove this or why it works?

1 Answer
sente
Mar 8, 2016

This is an application of Newton's method.

Let f(x) = x^2 - S => f'(x) = 2x

Then the zeros of f are +-sqrt(S) and thus, applying Newton's method, can be approximated by selecting an x_0 that is "close" to the desired root and applying the recurrence relation

x_(n+1) = x_n - f(x_n)/(f'(x_n))

=x_n - ((x_n^2-S)/(2x_n))

=x_n - x_n/2 + S/(2x_n)

=(x_n)/2+S/(2x_n)

=1/2(x_n+S/x_n)

Related questions
See all questions in Square Roots and Irrational Numbers
Impact of this question
2013 views around the world
You can reuse this answer
Creative Commons License