1
$\begingroup$

Consider solving the equation $\exp(x) - x - 1 = 0$.

It is obvious that $x^* = 0$ is a solution of the equation. Suppose you don't know this and you would like to approximate $x^*$ numerically by one of the following four methods. Which method will lead to a convergent algorithm for approximating $x^*$?

Why are the others not suitable?

The four methods are bisection method, fixed point iteration, Newton's Method, and Secant method.

Attempt: I tried each method on the equation but I have found that each converges which I know is not correct.

For fixed point iteration, I put the equation in the form $x = \exp(x) - 1$.

I don't know where to start in terms of the "inverval" to begin with i.e. with bisection the first thing I do is try $x=0$ and I get that it is the root. So am I done? Is bisection method the "correct" method in this case?

$\endgroup$
  • 2
    $\begingroup$ $0$ doesn't solve that. Do you have some signs wrong? $\endgroup$ – Randall Sep 23 at 18:56
  • 2
    $\begingroup$ or did you leave out some parentheses? $\endgroup$ – J. W. Tanner Sep 23 at 19:04
  • 1
    $\begingroup$ I had a sign wrong in the original equation. Fixed it. $\endgroup$ – Tim Sep 23 at 19:59
  • $\begingroup$ If you can compute the Lambert W function it's $-W(-\exp(-1))-1$ ... $\endgroup$ – Ben Bolker Sep 23 at 22:52
2
$\begingroup$

$$ \exp(x)-1-x=\frac12x^2\left(1+\frac13x+\frac1{12}x^2+...\right) $$ has a minimum in $x=0$ and behaves locally like $\frac12 x^2$.

plot of the function

Note that you pretend to not know the root. Starting the one of the methods at the point $x=0$ has thus to be considered extremely unlikely.

  • bisection method: fails before the first step as all function values away from $x=0$ have positive sign, no interval with sign alteration exists,
  • fixed point iteration: depends on the iteration function,
  • Newton's Method: converges linearly, and
  • Secant method: Convergence, as always, depends on the initial pair. If the secant becomes horizontal, the iteration can move far away from zero. It might recover or it might oscillate chaotically.
$\endgroup$
  • $\begingroup$ Rather than write out my own answer, I'll just add that for the suggested fixed-point iteration of $h(x) = e^x - 1$, we have $x < h(x)$ for all $x$ and $x<0 \iff h(x)<0$, so this converges for $x<0$ and diverges for $x>0$. $\endgroup$ – Misha Lavrov Sep 23 at 21:43

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.