Using newton-raphson method to generate following schemes

Question

Using newton's raphson method, generate following schemes:

• $x_{n+1}=\frac12\left(x_n+\frac{a}{x_n}\right)$ for computing $\sqrt a$
• $x_{n+1}=x_n(2-ax_n)$ for computing $a^{-1}$

what I understand is, the square root of $a$ is the number of $x$ which satisfies the following equations: $$\sqrt x=\sqrt a\implies\sqrt x-\sqrt a=0$$ Now, letting $f(x)=\sqrt x-\sqrt a$ , we can apply newton's raphson method:

$$x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}=x_n-\frac{\sqrt x_n-\sqrt a}{\frac{1}{2\sqrt x_n}}=-x_n+2\sqrt a\sqrt x_n$$

Which seems not the correct form for what they asked. Even same for second one also. Another question is, "When I write program for second one, it always blow up to infinity for any number $>1$". Is there any typo in $x_{n+1}=x_n(2-ax_n)$ for computing $a^{-1}$?

Answer 1

The square root of $a$ is not the number that satisfies $\sqrt x=\sqrt a$ (this is $a$ itself). It is the positive number that satisfies $x=\sqrt a$, or $x^2=a$.

Iterative methods have a domain of convergence, meaning that for some starting values they can fail to converge. Convergence is ensured when the distance to the root decreases on every iteration.

In the case of the inverse, you should ensure that $2-ax>0$ to keep positive estimates, hence the initial values must no be too large. For instance, it works well with $a=2,x_0=0.1$, giving the iterates

$$0.1,0.18,0.2952,0.41611392,0.4859262511645,0.4996038591874,0.4999996861449\cdots$$

---

A simple way to find good initial values is to determine the integer power of $2$ closest to the given $a$, let $2^n$. Then

$$\sqrt a\approx 2^{n/2}\text{ or }\sqrt2\,2^{(n-1)/2}$$

and

$$a^{-1}\approx 2^{-n}.$$

Answer 2

The method shown as

$$ x_{n+1}=\frac 12\left(x_n+\frac{a}{x_n}\right) $$

comes from considering the zeros of $f(x) = x^2-a$. It converges to $\pm \sqrt a$

A method to obtain $a^{-1}$, considering $f(x) = x^2-\frac{1}{a^2}$ can be posed as

$$ x_{n+1} = \frac 12\left(x_n+\frac{1}{a^2 x_n}\right) $$

converging to $\pm a^{-1}$

NOTE

A method to compute reciprocals without the use of reciprocals can be obtained by considering $f(x) = \frac{1}{x^2}-a^2$ when the fixed point is obtained by iterating

$$ x_{n+1}=-\frac{x_n}{2}(a^2x_n^2-3) $$

It is assumed known $\frac 12 = 0.5$

EDIT

The convergence for the second method $(a^{-1})$ can be justified analyzing the sufficient convergence condition which follows. If in

$$ x_{n+1} = \phi(x_n),\ x_{n} = \phi(x_{n-1}),\Rightarrow x_{n+1}-x_n = \phi'(\xi)(x_n-x_{n-1}) $$

we have that if $|\phi'(\xi)| < 1$ the sequence converges. Follows the graphics for $\phi'(\xi)$ when $a = 3$.