Newton's Method - Slow Convergence

Question

I'm using Newton's method to find the root of the equation $\frac{1}{2}x^2+x+1-e^x=0$ with $x_0=1$. Clearly the root is $x=0$, but it takes many iterations to reach this root. What is the reason for the slow convergence? Thanks for any help :)

Answer 1

Newton's method has quadratic convergence near simple zeros, but the derivative of $\frac{1}{2}x^2+x+1-e^x$ at $x=0$ is zero and so $x=0$ is not a simple zero.

Answer 2

If $f(x) =\frac{1}{2}x^2+x+1-e^x $, $f'(x) =x+1-e^x $, so $f'(0) = 0$.

Since the iteration is $x^* = x-\dfrac{f(x)}{f'(x)} $, the next value will be far away if you start at $x=0$.

You were probably saved by rounding error.

It would have helped if your question showed what your iterations actually were.

Answer 3

Define ${\rm F}\left(x\right) \equiv 2\left({\rm e}^{x} - 1 - x\right)/x^{2}$. We write the iteration as follows:

$$ x_{n + 1} = x_{n} - 1 + {1 \over {\rm F}\left(x_{n}\right)} $$

The ${\rm F}\left(x\right)$ evaluation is performed 'carefully': For 'small $x$ $$ {\rm F}\left(x\right) \approx 1 + {1 \over 3}\,x + {1 \over 12}\,x^{2} + {1 \over 60}\,x^{3}\,, \qquad\qquad \left\vert x\right\vert \gtrsim 0 $$ We neglect the cubic term whenever $\left\vert x\right\vert^{3}/60 < \delta_{\rm mp}$ where $\delta_{\rm mp}$ is the ${\it\mbox{machine precision}}$. It means $\left\vert x\right\vert < 60^{1/3}\delta_{\rm mp}^{1/3}$. The computer evaluation of ${\rm F}\left(x\right)$ is performed strictly according to the following definition: $$ {\rm F}\left(x\right) = \left\{% \begin{array}{ll} 1 + {x \over 3}\left(1 + {x \over 4}\right)\,, & \mbox{if}\qquad \left\vert x\right\vert < 60^{1/3}\,\delta_{\rm mp}^{1/3} \\[1mm] {2\left({\rm e}^{x} - 1 - x\right) \over x^{2}}\,, & \mbox{if}\qquad \left\vert x\right\vert \geq 60^{1/3}\,\delta_{\rm mp}^{1/3} \end{array}\right. $$

For example, in $\tt\mbox{C++}$, $\delta_{\rm mp}$ is defined in the $\tt\mbox{<cfloat>}$ library as $\tt\mbox{FLT_EPSILON}$, $\tt\mbox{DBL_EPSILON}$ and $\tt\mbox{LDBL_EPSILON}$ for $\tt\mbox{float}$, $\tt\mbox{double}$ and $\tt\mbox{long double}$ types, respectively.