Newton iteration for the reciprocal

Text

Show that Newton’s method applied to $f(x)=\dfrac{1}{x}-a$ produces the iteration $x_{n+1}=x_n(2-ax_n),$ an algorithm for the reciprocal $1/a$ that uses no divisions (it was used by old computers).

Solution

The function $f(x)=\dfrac{1}{x}-a$ has derivative $f'(x)=-\dfrac{1}{x^2}$. The Newton iteration is $x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} = x_n - \frac{\frac{1}{x_n}-a}{-\frac{1}{x_n^2}}.$ The quotient simplifies by multiplying numerator and denominator by $-x_n^2$: $x_{n+1} = x_n + x_n^2\!\left(\frac{1}{x_n}-a\right) = x_n + x_n - a x_n^2 = \boxed{x_n(2-ax_n)}.$ The zero of $f$ is $x=1/a$, so the iteration converges to the reciprocal of $a$. The formula uses only multiplications and one subtraction: no division, which is why it was used in hardware that had no division unit.

Links

Topics: Continuity
Concepts: Newton-Raphson method
Methods: Newton-Raphson
Skills: Proving · Using formulae
Exercise types: Proof