Using Newtons Method to approximate intersection of Graphs

Question

Using Newtons Method, I am to try to approximate the point R where the graphs of

$y = e^{-x}$ and $y = ln(1 + x)$

First I was supposed to propose a function, f(x) for which the method can be used, and using methods taught I came up with the function

$f(x) = e^{-x} - ln(1 + x)$

However, now I am to propose an initial approximation, $x_0$, so that I am able to guarantee convergence, and this is where I am stumped. I have tried $X_0$ = 0, 1, .5, -1... and have been unsuccessful because when using Newtons method every initial guess I have goes on to infinity. Can someone clear this up for me?

Answer 1

That's a good choice for $f$. You're required to show that Newton's method is guaranteed to converge? That's ordinarily quite a tall order; one sufficient set of conditions that will guarantee this is to show that, on some interval $I = [a,b]$,

1. $f$ is $C^2$,
2. $f$ has at least one root, e.g. $f(a)f(b) < 0$
3. $f' \neq 0$,
4. $f$ is convex, e.g. $f'' > 0$.

Luckily, it is fairly easy to pick $I$ and verify all of these conditions for your particular function.

EDIT: More explicit hints. Well, let's take a look at where each of these conditions is satisfied.

1. This one is easy: the only thing that can go wrong here is that $\log 1+x$ is undefined, which means we need $I \subset (-1,\infty)$.
2. We'll get back to this one.
3. $f' = -e^{-x} - \frac{1}{x+1}$. Since both terms are negative when $x>-1$, we're still OK on the entire interval $(-1,\infty)$.
4. $f'' = e^{-x} + \frac{1}{(x+1)^2}$. Again, both terms are positive on $(-1,\infty)$ so $f$ is convex on the whole interval.

So now we just need to check that $f$ has at least one root on $(-1,\infty)$. This basically boils down to guess and check: we can try $a=0$ which gives $f(0) = 1$ and clearly $f(x) < 0$ for $x$ sufficiently large. So any initial guess on $(-1,\infty)$ is guaranteed to converge.

Answer 2

In order to ensure convergence without any overshoot of the solution, I think that you must start iterating from a point $x_0$ such that $$f(x_0) \times f''(x_0) \gt 0$$ Since, for any $x$, $f''(x)>0$, this only requires $f(x_0)>0$.

Newton iterate is given by $$x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}$$ and, for sure, $x_{n+1}$ must be larger than $-1$. A look at function $$g(x)=x-\frac{f(x)}{f'(x)}$$ shows that $g(x)=-1$ for $x \approx 2.71457$. So, your starting guess $x_0$ must be such that $-1 <x_0 \leq 2.7$; no overshoot of the solution is you start at any $x_0$ such that $f(x_0)>0$.