# convergence of newton algorithm when looking for roots of $f(x) = xe^x$

I want to show the convergence of newton's algorithm when calculating the root of $f(x)=xe^x$ using an $x_0 \geq 0$.

The resulting recursion is

$$x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)} = x_k - \frac{x_k e^{x_k}}{x_ke^{x_k}+e^x}$$

Any hints? The only estimate I got so far was

$$|x_{k+1} - 0| = |x_k - \frac{x_k}{x_k+1}| \leq \quad?$$

$$|x_{k+1} - x_k| = |x_k - \frac{x_k}{x_k+1} - x_k| = |\frac{x_k}{x_k+1}| \leq \quad1?$$

where $f(0)=0$ is the root.

-
You might first identify $x^*$, then correct your computation of $f(x_k)/f'(x_k)$. –  Did Feb 2 '13 at 17:05
Well, $f(x)=xe^x$ is Lipschitz Continuous (It is everywhere differentiable). –  Inquest Feb 2 '13 at 22:32

You've made an error in computing $f'$, which likely accounts for your confusion. We should have $f'(x)=e^x+xe^x=(x+1)e^x$ by product rule, so since $e^x>0$ for all real $x$, then $$x_{k+1}=x_k-\frac{x_ke^{x_k}}{(x_k+1)e^{x_k}}=x_k-\frac{x_k}{x_k+1}.$$ See if you find that more tractable to work with.

Also, as a side note, since $e^x\neq 0$ for any $x$, you should be able to explicitly determine what the unique root of $f(x)$ is.

-
The root is $f(0)=0$. I got the $f'$ wrong. But now thinking about it using the proper one I still don't manage to show convergence.. –  fritz Feb 2 '13 at 22:23
Note that $f'(x)=(x+1)\mathrm e^x$ hence $x_{k+1}=u(x_k)$ where $u:x\mapsto x^2/(x+1)$.
Since $u(x)\lt x$ for every $x\gt0$ and $x_0\gt0$, the sequence $(x_k)_{k\geqslant0}$ is decreasing and converges to $0$. Assume without loss of generality that $x_0\lt1$. Then $x_{k+1}\lt x_k^2$ for every $k$ hence $$x_k\leqslant(x_0)^{2^k}.$$ To refine this, note that $x_k=(x_0)^{2^k}/z_k$, where $$z_k=\prod_{i=0}^k(1+x_i).$$ The sequence $(z_k)_k$ is increasing. Since $x_i\leqslant(x_0)^{2^i}$ and $x_0\lt1$, the series $\sum\limits_ix_i$ converges, hence the sequence $(z_k)_k$ is bounded. Finally, calling $z$ the limit of $(z_k)_k$, one gets $$\lim\limits_{k\to\infty}x_k\cdot(x_0)^{-2^k}=z^{-1}.$$