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.

Solutions Collecting From Web of "Computing the square root function with Newton's method"

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.

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.

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.