# Convergence of algorithm (bisection, fixed point, Newton's method, secant method)

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?

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

$$\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$$.
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,
• 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$. – Misha Lavrov Sep 23 at 21:43