3
$\begingroup$

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?

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

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – ABC Aug 1 '13 at 1:13
  • 1
    $\begingroup$ 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. $\endgroup$ – André Nicolas Aug 1 '13 at 1:18
  • $\begingroup$ 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. $\endgroup$ – André Nicolas Aug 1 '13 at 1:20
3
$\begingroup$

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)$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.