Fixed-Point iteration technique.

I have to find the root of $x-e^{-x}=0$ by using fixed-point iteration.

when i rewrite the equation as $x=e^{-x}$ , the iterative process converges to $0.567$ after $12$ iteration.

But when i rewrite the equation as $x=-\ln(x)$ , the iterative process diverges. Why?

• @Amzoti my initial guess is $0.5$ – ABC Aug 1 '13 at 0:57

We give an informal reason for the problem. Note that near the root, the derivative of $-\ln x$ is $-\frac{1}{x}$. Since the root is around $0.567$, that means that near the root the derivative of $-\ln x$ has absolute value significantly bigger than $1$. That means that the root is a repelling fixed point. Let $f(x)--\ln x$, and let $r$ be the root, Let $x_n$ be the $n$-th iterate. Note that $x_{n+1}=f(x_n)$. We have $x_{n+1}-r=x_{n+1}-f(r)=f(x_n)-f(r)$.
But $$\frac{f(x_n)-f(r)}{x_n-r}\approx f'(r)$$ if $x_n$ is close to $r$. If $|f'(r)|\gt 1$, that means that $f(x_n)$ is further from $r$ than $x_n$!
Remark: For any root finding problem, we have a number of ways of putting the problem in the form $g(x)=x$. A good choice has the property that $|g'(x)|$ is well under $1$ near the root.
The Newton Method can be put in the form $g(x)=x$. It turns out that the Newton Method (in situations where it behaves well) has the property that $g'(x)=0$ at the root. This partly accounts for its remarkable speed of convergence.
• Could you please explain when i starts to find the approximation of the root, i don't have opportunity to check $|g\prime(x)|=|g\prime(.567)|=1.76366843>1$. In that case, how can i understand whether $g(x)=-\ln(x)$ will converge or not?. or am i doing mistake understanding you? – ABC Aug 1 '13 at 1:13
• It will not converge, unless by freak chance you start at exactly the root! I have tried to explain why in the post, to which I have added quite a bit. But basically the problem is that at the root, the absolute value of the derivative of $-\ln x$ is bigger than $1$. The reason $e^{-x}=x$ worked reasonably nicely is that the absolute value of the derivative of $e^{-x}$ is significantly less than $1$ at and near the root. Derivative with small absolute value, good; derivative with absolute value greater than $11: very very bad. – André Nicolas Aug 1 '13 at 1:18 • So you are not making a mistake, the iteration$x=-\ln x$doesn't work, if we happen to start near the root we get pushed away from it. – André Nicolas Aug 1 '13 at 1:20 A sufficient condition to ensure the convergence is to apply the Banach fixed point theorem: if$f$is contraction function defined on a closed interval$I$(and in general a complete metric space) then it has a unique fixed point$x^*$which can be found as follows: start with an arbitrary element$x_0$in$I$and define a sequence$(x_n)$by$x_n = f(x_{n−1})$so$(x_n)$is convergent to$x^*$. If$f(x)=e^{-x}$we have $$|f(x)-f(y)|\leq e^{-a}|x-y|,\, \forall x,y\geq a>0$$ so$f$is a contraction function. If$f(x)=-\ln x$then its derivative isn't bounded and then it's not a contraction on$(0,+\infty)\$