Question

Let \(f(x)=x^{2}-a\). Show that the Newton Method leads to the recurrence
\[
x_{n+1}=\frac{1}{2}\left(x_{n}+\frac{a}{x_{n}}\right) .
\]
Heron of Alexandria (60 CE?) used a pre-algebra version of the above recurrence. It is still at the heart of computer algorithms for finding square roots.

Answer 1

We have \(f(x)=2 x\). The Newton Method therefore leads to the recurrence
\[
x_{n+1}=x_{n}-\frac{f\left(x_{n}\right)}{f^{\prime}\left(x_{n}\right)}=x_{n}-\frac{x_{n}^{2}-a}{2 x_{n}} .
\]
Bring the expression on the right hand side to the common denominator \(2 x_{n}\). We get
\[
x_{n+1}=\frac{2 x_{n}^{2}-\left(x_{n}^{2}-a\right)}{2 x_{n}}=\frac{x_{n}^{2}+a}{2 x_{n}}=\frac{1}{2}\left(x_{n}+\frac{a}{x_{n}}\right) .
\]