# Reciprocal using Newton Raphson

Say you want to calculate 1/R using Newton-Rapshon method. Then we let,

$$f(x) = 1/x - R$$

This means the root of the this function is at $$f(1/R)$$. So to find $$1/R$$, you can find the root of this function using Newton-Raphson method.

I got this part. Your first Newton-Raphson iteration would be:

$$x_1 = x_0 + x(1-xR)$$ as you know that $$\frac{f(x)}{f'(x)}=-x(1-xR)$$

Now I'd like to prove that the error satisfies:

$$\frac{r-r_1}{r} = (\frac{r-r_0}{r})^2$$

Where $$r=1/R$$

How can I prove this?

I found on Wikipedia:

https://en.wikipedia.org/wiki/Division_algorithm#Newton%E2%80%93Raphson_division

It says that the number of correct digits doubles each time. This should mean that the relative error is squared each time. So relative error of $$r_1$$ should be the square of relative error of $$r_0$$... So I should be able to prove this statement true.

We have $$x_1 = x_0 + x_0\left(1-\frac{x_0}{r}\right)$$, hence $$r - x_1 = \frac{x_0^2}{r} - 2x_0 + r$$, and $$\frac{r - x_1}{r} = \frac{x_0^2 - 2x_0 r + r^2}{r^2}= \left(\frac{r-x_0}{r}\right)^2$$.

• How did you get $r-x_1 = ...$ – voo oool Dec 5 '18 at 5:51
• Expand RHS, subtract $r$ from both sides, change signs. – mlerma54 Dec 5 '18 at 5:59
• The final result I need is $\frac{r-r_1}{r}$, not $\frac{r-x_1}{r}$. Might be hard to read but it's $r_1$ not $x_1$ – voo oool Dec 5 '18 at 6:07
• What is $r_1$? I do not see it defined. – mlerma54 Dec 5 '18 at 6:11
• $r_i = 1/R_i$. I defined it without the subscript i – voo oool Dec 5 '18 at 6:12

For the sake of easy algebra I'll work with signed errors. Since $$x_1=x_0(2-Rx_0)$$, the absolute errors $$\epsilon_i:=x_i-\frac{1}{R}$$ satisfy $$\epsilon_1=(\epsilon_0+\frac{1}{R})(1-R\epsilon_0)-\frac{1}{R}=-R\epsilon_0^2$$, so the relative errors $$\delta_i:=R\epsilon_i$$ satisfy $$\delta_1=-\delta_0^2$$.

Simply plug the values of $$r_0$$ and $$r_1$$:

$$\frac{r-r_1}{r} = \left(\frac{r-r_0}{r}\right)^2$$ comes from $$\frac{r-(r_0 + r_0(1-r_0R))}{r} = \left(\frac{r-r_0}{r}\right)^2$$

which is true because

$$\frac{r-(r_0 + r_0(1-r_0R))}{r}=\frac{r^2-2rr_0 +r_0^2}{r^2}.$$