8
$\begingroup$

I have to find a real root of the equation $x=\ e^{-x}$ , using the Newton-Raphson Method.

I solved the example writing the function in the form $f(x)=x -\ e^{-x}=0$ which is straightforward and i found the approximates after 3 iteration and confirm it in 4th iteration.

But in the book from which i am solving exercise, they rewrite the equation in the form $f(x)=x\ e^{x}-1=0$. Also here the solution is obtained after 3 iteration.

Is there any advantage if i rewrite the function , that is , is there any matter of convergence here?

| cite | improve this question | | | | |
$\endgroup$
12
$\begingroup$

Let's look at the iterations you get from each.

With $f(x) = x - e^{-x}$, you get

$$F(x) = x - \frac{f(x)}{f'(x)} = x - \frac{x-e^{-x}}{1+e^{-x}} = \frac{x + xe^{-x} - x + e^{-x}}{1+e^{-x}} = \frac{x+1}{e^x+1}.$$

That's a nice function, defined on all of $\mathbb{R}$, gets you close to the solution real fast when you start at a non-negative $x_0$, but is not so good for negative $x$, then it approaches the fixed point slowly at first.

With $g(x) = xe^x - 1$, you get

$$G(x) = x - \frac{g(x)}{g'(x)} = x - \frac{xe^x-1}{(x+1)e^x} = \frac{x^2e^x+1}{(x+1)e^x} = \frac{x^2+e^{-x}}{x+1}.$$

That function has a pole in $-1$, and $G(x) < -1$ for $x < -1$, so doesn't reach the fixed point from there. For large positive $x$, it doesn't approach the fixed point fast (basically, it's $x \mapsto \frac{x}{x+1}\cdot x$ there).

So looking at the global behaviour, your choice behaves much better.

Now, for the local behaviour near the fixed point, the Newton iteration roughly behaves like

$$\alpha + \delta \mapsto \alpha + \frac{f''(\alpha)}{2f'(\alpha)}\delta^2$$

when $f'$ doesn't vanish in the zero of $f$, as is the case here, so let's look at the corresponding quotient for the two candidates.

$$\begin{align} \frac{g''(\alpha)}{2g'(\alpha)} &= \frac{(\alpha+2)e^\alpha}{2(\alpha+1)e^\alpha} = \frac{\alpha + 2}{2(\alpha+1)} = \frac12 + \frac{1}{2(\alpha+1)}\\ \frac{f''(\alpha)}{2f'(\alpha)} &= \frac{-e^{-\alpha}}{2(1+e^{-\alpha})} = \frac{-\alpha}{2(1+\alpha)} = \frac{1}{2(\alpha+1)} - \frac12 \end{align}$$

using $e^{-\alpha} = \alpha$ for the latter.

So $G$ approaches the fixed point from above, while $F$ approaches it from below ($f''(\alpha) < 0 < f'(\alpha)$), and the factor of the square has smaller absolute value for $F$, that means the convergence of $F$ is faster near the fixed point $\alpha$ (but that doesn't matter much against the quadratic convergence, nevertheless).

So, altogether, yours was the better choice globally (converges to the solution from all starting points), and locally (converges faster near the fixed point).

| cite | improve this answer | | | | |
$\endgroup$
  • 1
    $\begingroup$ Very enlightening solution. It makes me wonder what the author of the textbook was thinking :) $\endgroup$ – Tyler Aug 3 '13 at 13:21
  • 1
    $\begingroup$ Probably the author didn't like $e^{-x}$ and preferred $e^x$. If you start somewhat near the solution, it doesn't make much difference anyway. There's a giveaway that $x-e^{-x}$ may be nicer: that one is concave (globally), while $xe^x -1$ switches between being concave and convex. Also $f'(x) > 0$ always, while $g'$ has a zero. $\endgroup$ – Daniel Fischer Aug 3 '13 at 13:28

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.