# 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?

Mar 8, 2016

This is an application of Newton's method.

Let $f \left(x\right) = {x}^{2} - S \implies f ' \left(x\right) = 2 x$

Then the zeros of $f$ are $\pm \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 \frac{{x}_{n}}{f ' \left({x}_{n}\right)}$

$= {x}_{n} - \left(\frac{{x}_{n}^{2} - S}{2 {x}_{n}}\right)$

$= {x}_{n} - {x}_{n} / 2 + \frac{S}{2 {x}_{n}}$

$= \frac{{x}_{n}}{2} + \frac{S}{2 {x}_{n}}$

$= \frac{1}{2} \left({x}_{n} + \frac{S}{x} _ n\right)$