Reciprocal using Newton Raphson

Question

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.

Answer 1

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$.

Answer 2

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$.

Answer 3

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}.$$