0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ How did you get $r-x_1 = ...$ $\endgroup$ – voo oool Dec 5 '18 at 5:51
  • $\begingroup$ Expand RHS, subtract $r$ from both sides, change signs. $\endgroup$ – mlerma54 Dec 5 '18 at 5:59
  • $\begingroup$ 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$ $\endgroup$ – voo oool Dec 5 '18 at 6:07
  • $\begingroup$ What is $r_1$? I do not see it defined. $\endgroup$ – mlerma54 Dec 5 '18 at 6:11
  • $\begingroup$ $r_i = 1/R_i$. I defined it without the subscript i $\endgroup$ – voo oool Dec 5 '18 at 6:12
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.