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?
On
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)$
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.