Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question

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.

share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.