Newton-Raphson Iteration §

---

Want to find the root of $f(x)$, for example a value for $x$ such that $f(x)=0$.

Newton-Raphson starts with an initial estimate, $x_0$, and computes a better estimate, $x_1$ $x_1=x_0-\frac{f(x_0)}{f^{\prime }(x_0)}$

For example, to compute $\frac{1}{b}$, we use: $f(x)=\frac{1}{x}-b$ $=$ $x^{-1}-b$

$f^{\prime }(x)=-x^{-2}$

Leading to the formula: $x_1=x_0-\frac{x_0^{-1}-b}{-x_0^{-2}}$ $=$ $2x_0-b{x}_0^2$

Division §

$c=\frac{a}{b}$

Compute $r=\frac{1}{b}$, then $c=r\ast a$

Algorithm:

• $r_0$ as guess for $\frac{1}{b}$.
• $r_{i+1}=2r_i=b{r}_i^2$ (Newton-Raphson)

Second order convergent, so $O(logr)$.

---

See Also §