Find the range of initial values for which Newton–Raphson's method for $f(x) = a - \frac{1}{x}$ converges

Question

I'm tryig to use Newton–Raphson's method to compute the inverse of $a$. Given $f(x) = a - \frac{1}{x}, a \neq 0$ we are looking for $x^*$ such that $f(x^*) = 0$. Newton–Raphson's method gives the sequence $x_{n+1} = -ax_n^2 + 2x_n$. For example let $a = 2$, so $x_{n+1} = -2x_n^2 + 2x_n$. So want to find for which initial values $x_0$ the method converges. Playing around with an algorithm I implemented I found that $x_0$ must be in $(0, 1)$ for it to converge.

But how can I prove that? And in the more general case of $a$. Any help would be appreciated.

Answer 1

Have you heard of Kantorovich's theorem for Newton's method?

Theorem of Kantorovich. Let $I\subseteq \mathbb{R}$ a interval and $F:{I}\to \mathbb{R}$ a continuous function, continuously differentiable on $\mathrm{int}(I)$. Take $x_0\in \mathrm{int}(I)$, $L,\, b>0$ and suppose that

• $F '(x_0)$ is non-singular,

• $ \| F'(y)- F'(x) \| \leq L\|x-y\| \;\;$ for any $x,y\in I$,

• $ \|F'(x_0)^{-1}\cdot F(x_0)\|\leq b$,

• $2\cdot b\cdot L\leq 1$.

Define $ t_*:=\frac{1-\sqrt{1-2bL}}{L}. $ If $ [x_0-t_*,x_0+t_*]\subset I, $ then the sequences $\{x_k\}$ generated by Newton's Method for solving $F(x)=0$ with starting point $x_0$, $$ x_{k+1} ={x_k}-F'(x_k) ^{-1}F(x_k), \qquad k=0,1,\cdots, $$ is well defined, is contained in $(x_0-t_*,x_0+t_*)$, converges to a point $x_*\in [x_0-t_*,x_0+t_*]$ which is the unique zero of $F$ in $[x_0-t_*,x_0+t_*]$.

Here a expository Article: Kantorovich's s theorem on Newton's method.. See too other expository Article here.. See Ortega's paper here for a simple proof.

See personal home page of Prof. Ferreira for articles of Newton-Kantorovich method and variants in Banach spaces.

Answer 2

Hint.

A coarse appreciation.

The Newton-Raphson recurrence formula is $x_{k+1} = \phi(x_k)$ then

$$ x_{k+1}-x_k = \phi(x_k)-\phi(k_{k-1})=\phi'(\zeta)(x_k-x_{k-1}),\ \ \zeta\in B(x_k,x_{k-1}) $$

For convergence it is sufficient then that $|\phi'(\zeta)| < 1$ for $\zeta\in B(x_k,x_{k-1})$

Here $B(x_k,x_{k-1})$ is an open neighbourn containing $(x_k,x_{k-1})$.

In our case $\phi(x) = -ax^2+2x$ and $\phi'(x) = -2ax+2$