Question

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?

Answer 1

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)`