# Computing the square root function with Newton's method

Show that Newton's method can be used to compute the square root function $\sqrt a$ using the formula

$$x_{n+1} = \frac{1}{2}\left(x_{n} + \frac{a}{x_{n}}\right)$$

show that the error is

$$\sqrt a - x_{n+1} = -\frac{1}{2x_{n}}\left(\sqrt a - x_{n}\right)^2$$

edit: As pointed out below $x^2-a$ has $\sqrt a$ as a root.

I have done as suggested below and plugged in $\sqrt a + \epsilon$ for $x_n$ giving me

$$x_{n+1} = \frac{2\epsilon\sqrt a + \epsilon^2}{2(\sqrt a + \epsilon)}$$ and once again not sure where to proceed.

-
What exactly have you tried to do here? Where do you need help? –  Ron Gordon Feb 20 '13 at 13:42
I suppose I simply need help getting started. I know x1=x0-(f(x1)/f'(x1)) (denominator is f prime but it doesnt show) but what do I do with this? –  BMEdwards37 Feb 20 '13 at 13:48
My first instinct would be to graph, pick a guess, plug in and go but this is a definition for xn+1 not a function of x. –  BMEdwards37 Feb 20 '13 at 13:52
Why not just plug the formula for $x_{n+1}$ into $\sqrt a - x_{n+1} = -\frac{1}{2x_{n}}\left(\sqrt a - x_{n}\right)^2$ and check that you get an identity? –  Hurkyl Feb 20 '13 at 22:46
So you're saying do $$\sqrt a - \frac{1}{2}\left(x_{n} + \frac{a}{x_{n}}\right) = -\frac{1}{2x_{n}}\left(\sqrt a - x_{n}\right)^2$$ and solve? –  BMEdwards37 Feb 20 '13 at 23:23

Hint: start with the fact that $f(x) = x^2-a$ has $\sqrt{a}$ as a root.

Use the Newton's Method formula:

$$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$$

where $f(x_n) = x_n^2-a$ and $f'(x_n) = 2 x_n$.

Plug these into the above equation and the first result is obtained with a little algebra. For the second result, note that

$$\sqrt{a}-x_{n+1} = \sqrt{a}-\frac{1}{2} \left (x_n + \frac{a}{x_n} \right )$$

What you can do here is multiply that last piece out and factor out $-1/(2 x_n)$. What you should get is 3 terms that fit a pattern of a binomial squared. Look at the result you are trying to show to guide you.

-
So from here would I follow my first instincts? Graph, make a guess at x0, and then attempt to work out the root by following the formula for xn+1 above? Also, assuming that is what I should do, I have no idea what to do with the error. –  BMEdwards37 Feb 20 '13 at 13:56
This isn't anything numerical is it? It's a proof. I hate, and suck at, proofs and I regret to say I'm as lost now as I ever was. –  BMEdwards37 Feb 20 '13 at 14:01
@BMEdwards37: a lot of numerical analysis involves non-numerical analysis, and algebra. The ugly, numerical part of this involves knowing where you can start the sequence; remember, there are two roots here, and you'd hate to converge to the wrong one. –  Ron Gordon Feb 20 '13 at 14:46
Wow totally missed the fact that you added to the body of your post and didn't just comment. Maybe it would have saved me some hassle! I must just be doing my algebra wrong on the first part, will keep looking at it. –  BMEdwards37 Feb 20 '13 at 22:47
@BMEdwards37: I sometimes make edits to my posts like that if I think they'll be helpful or if I catch an error. Keep working at it, you'll get it. Humans always win. –  Ron Gordon Feb 20 '13 at 22:53

We have Newton's method as \begin{align} x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)} \end{align} And Newton's method is used to solve $f(x)=0$. As rlgordonma pointed out,if you want to calculate $\sqrt{a}$ you need to solve $f(x)=0$ for a function $f$ that fulfills $f(\sqrt{a})=0$. He also told, that such a function is $f(x) = x^2-a$. Now combine the two information.

-
I see where how I would solve this rather easy numerically but I'm just not seeing it otherwise. I get that f(x)=x^2-a for f(sqrt(a))=0 and I know how to apply the method, I'm just not really sure how this translates to the proof. I have not had a proof class yet and am horrible at them, as you can probably tell. –  BMEdwards37 Feb 20 '13 at 21:25

You can find what it converges to by plugging in $x$ for $x_{n+1}$ and $x_n$. To show that it converges, let $x_n=\sqrt a + \epsilon_n$. Plug this into the equation and compute $x_{n+1}$. You should be able to find that $x_{n+1}-\sqrt a$ is of order $\epsilon^2$, so if $\epsilon \lt 1$ it will converge.

Added: So $x_{n+1}=\frac 12 (x_n+\frac a{x_n})$

Let $x_n=\sqrt a + \epsilon_n$ (and we imagine that $\epsilon_n \ll 1$)

Then $x_{n+1}=\sqrt a + \epsilon_{n+1}=\frac 12(\sqrt a + \epsilon_n+\frac a{\sqrt a - \epsilon_n}) \\ \approx \frac 12(\sqrt a + \epsilon_n+ \sqrt a(1-\frac {\epsilon_n}{\sqrt a} +\frac {\epsilon_n^2}a))\\ =\sqrt a+\frac {\epsilon_n^2}{\sqrt a}$

So $\epsilon_{n+1}\approx \frac {\epsilon_n^2}{\sqrt a}$ showing the error gets squared each iteration.

-
I noticed this just before having to leave for class and I'm not sure I totally understand. I plug x in the top equation giving me x=.5(x+a/x)? The second part I understand, I can plug in sqrt(a)+E to work out xn+1. Will i have to do multiple steps of this to get to the error? I need to head to class now, going to study some while I'm there and maybe I'll have a magical breakthrough. I'll check back this afternoon, thank you for the attempted help even though I fear I'm helpless. –  BMEdwards37 Feb 20 '13 at 14:45
@BMEdwards37: no, the error gets squared every iteration. That is why people like Newton's method. If you have four places at some point, one more iteration makes it eight and another makes it sixteen. –  Ross Millikan Feb 20 '13 at 14:47
So I've done as you said and plugged in sqrt(a)+E for xn, and I've got it down to (a+2E(sqrt(a))+E^2)/(sqrt(a)+e), but I'm not really seeing the Xn+1-sqrt(a) part. Am I on the right track? Mind giving me a nudge? –  BMEdwards37 Feb 20 '13 at 21:50
@BMEdwards37: $\frac a{\sqrt a + \epsilon}=\frac {\sqrt a}{1+\frac \epsilon{\sqrt a}} \approx \sqrt a(1-\frac \epsilon {\sqrt a}+\frac {\epsilon^2}a)$ It would be much easier to read your comment if you $\LaTeX$ it. You could see meta.math.stackexchange.com/questions/1773/… –  Ross Millikan Feb 20 '13 at 22:21
I'm sorry, I actually thought that LaTeX didn't work in comments, that is my mistake. I'm not sure that i realize where your comment is supposed to apply to though. –  BMEdwards37 Feb 20 '13 at 22:28