1
$\begingroup$

I'm trying to determine why the upper bound for the first approximation $p_0$ of the root $p$ of a function $f \in C^2$ must satisfy the condition: $$|p-p_0|\leq \frac{2|f'(p)|}{|f''(p)|}$$ when $p$ is a simple root, i.e.: $f(p)=0$, but $f'(p)\neq 0$. I've tried to rationalize this from the theorem of convergence of Newton-Raphson's method for a simple root: $$ \frac{|p_{n+1}-p|}{|p_n-p|^2} = \frac{|f''(p)|}{2|f'(p)|}, n \gg 0 $$ , but I suspect I'm moving in the wrong direction. I know the solution has something to do with the second Taylor expansion of the function about $p_0$ when deriving Newton's method (I'm working out of Burden and Faires' Numerical Analysis textbook): $$ f(p) = 0 = f(p_0)+f'(p_0)(p-p_0)+\frac{1}{2!}f''(\xi)(p-p_0)^2 $$, where $\xi$ lies between $p_0$ and $p$. (I know you have to assume that since $p-p_0$ is small, $(p-p_0)^2$ is negligible and therefore you can drop the error term.) Help would be greatly appreciated -- I'm studying for my exams.

$\endgroup$
0
$\begingroup$

The statement you're trying to prove is actually incorrect. That is, there are $C^2$ functions with simple roots for which Newton’s method may very well converge even if the condition $|p-p_0|\leq \frac{2|f'(p)|}{|f''(p)|}$ is violated.

As a simple example, let $f(x)=e^x-1$, for which zero is the only root. In this case, $\frac{2|f'(p)|}{|f''(p)|}=2$, but you’ll find, for example, that Newton’s method converges just fine with $p_0=5$. In fact, the function $f$ of this example is globally convergent (it converges for any starting point). More generally, one can show that if $f$ is simultaneously (i) $C^2$, (ii) monotonically increasing, (iii) convex, and (iv) has a zero, then the zero is unique and Newton’s method will converge to it from any starting point.

The criteria $|p-p_0|\leq \frac{2|f'(p)|}{|f''(p)|}$ is in fact a sufficient but not necessary condition for the local convergence of Newton’s method. Perhaps your difficulty with this problem arose from the mistaken assumption that the criteria was also a necessary condition for convergence.

$\endgroup$

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.