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

1 Answer 1

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$
1
  • $\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$ Commented Sep 23, 2019 at 21:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .