Using Newton's method calculate $ \frac{1}{\sqrt{a}} $ without division

Solution 1:

After using dark magic to make an initial guess $y_0$, the fast inverse square root algoritm essentially approximates $y=1/\sqrt{x}$, $x > 0$, by using the iteration

$$ y_{n+1} = \frac{3}{2}y_n - \frac{1}{2}xy_n^3. $$

There is no division here, unless you count the multiplication by the constants $3/2$ and $1/2$.

If the limit as $n \to \infty$ exists then it is a solution to the cubic equation

$$ y = \frac{3}{2}y - \frac{1}{2}xy^3. $$

Of course the only solutions are $y=0$ and $y=\pm 1/\sqrt{x}$. We can do some analysis using the standard techniques for discrete dynamical systems to determine when the iteration will converge and to which point.

Let

$$ f(y) = \frac{3}{2}y - \frac{1}{2}xy^3. $$

Then $f'(0) = 3/2 > 1$, so $y=0$ is an unstable equilibrium of the system. We also have $f'(1/\sqrt{x}) = 0$, which is $<1$ in absolute value, so that the points $y=\pm 1/\sqrt{x}$ are stable equilibria.

In other words, if $y_0$ is close enough to $\pm 1/\sqrt{x}$ then $y_n$ will converge to $\pm 1/\sqrt{x}$. We can determine how close we need to be by calculating

$$ f'(y) = \frac{3}{2}\left(1-xy^2\right). $$

We require $|f'(y)| < 1$ in order for $f$ to be a contraction, and this is equivalent to

$$ -\frac{2}{3} < 1 - xy^2 < \frac{2}{3}. $$

Rearranging, we end up with

$$ \frac{1}{3x} < y^2 < \frac{5}{3x}. $$

So, if

$$ \sqrt\frac{1}{3x} < y_0 < \sqrt\frac{5}{3x} $$

then $y_n \to 1/\sqrt{x}$ as $n \to \infty$, and if

$$ -\sqrt\frac{5}{3x} < y_0 < -\sqrt\frac{1}{3x} $$

then $y_n \to -1/\sqrt{x}$ as $n \to \infty$.

Like the traditional Newton's method, this iterative scheme also converges quadratically. If we let $y_n = 1/\sqrt{x} + \epsilon_n$, then the system becomes

$$ \epsilon_{n+1} = -\frac{3\sqrt{x}}{2} \epsilon_n^2 - \frac{x}{2} \epsilon_n^3. $$

Solution 2:

Apply Newton's Method to $f(x) = x^{-2} - a$.