Calculating $\frac{1}{a}$ using Newton-Raphson method

Question

I have a computer that doesn't implement division operation (it has only addition, substraction and multiplication). I need to find a method to find the approximate value of $\frac{1}{a}$, where $a\in \mathbb R \setminus\{0\}$. I'm supposed to do that with Newton-Raphson method ($x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)}$) and there mustn't be any division operation in the final formula.

So far I have tried obvious $f(x)=ax-1$, but then: $$ x_{k+1}=x_k-\frac{a\cdot x_k-1}{a}=\frac{1}{a} $$ which obviously haven't brought me any closer to the answer. Do you have any ideas what $f$ function should I take to solve this?

Answer 1

We take function: $f(x)=a-\frac{1}{x}$. $$ x_{k+1}=x_k-\frac{a-\frac{1}{x_k}}{\frac{1}{x_k^2}}=\frac{\frac{1}{x_k}-a+\frac{1}{x_k}}{\frac{1}{x_k^2}}=2x_k-a\cdot x_k^2 $$

Answer 2

I complete the answer above. Observe that the recursion formula $x_{k+1}=2x_k-ax_k^2$ is equivalent to $1-ax_{k+1}=(1-ax_k)^2$. Thus, for every $k \in \mathbb{N}$, $1-ax_k=(1-ax_0)^{2^k}$. The method works provided $|1-ax_0|<1$.

A similar method applies to compute the inverse of a matrix $A \in GL_n(\mathbb{C})$. The recursion formula becomes $X_{k+1}=2X_k-X_kAX_k$. One has to start with a matrix $X_0$ such that the spectral radius of $I-AX_0$ is $<1$. An example of such a matrix is $\overline{A}^\top/\mathrm{tr}(A\overline{A})$. Indeed, for this choice of $X_0$, the matrix $AX_0$ is hermitian, definite positive with trace equal to $1$, so its eigenvalues belong to $]0,1]$ and the eigenvalues of $I-AX_0$ belong to $[0,1[$.