Take the 2-minute tour ×
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.

I'm doing a MATLAB assignment in which you work out and implement a better version of Newton-Raphson using a second degree Taylor polynomial instead of a first degree one. I have the algorithm worked out and it is working good. The second part of the assignment is to study the order of convergence empirically. The problem is that with all the functions I've come up with so far gets a very good answer after only 2-4 iterations which doesn't give me a very reliable grounds for analyzing the order of convergence.

Can you help me come up with a function that the N-R method works on pretty badly, so that it, for some starting value, takes some more iterations to get to a good value?

share|improve this question
1  
I expect you have tested Newton-Raphson, and your alternative, on say $x^8=0$. –  André Nicolas Dec 7 '11 at 21:10
1  
I presume you've seen this? –  J. M. Dec 7 '11 at 23:13
1  
If you follow through the proof that standard Newton-Raphson squares the error at each step, you should be able to find that your modified version cubes the error at each step. The point is that the usual first derivative takes out the linear term in the Taylor series near the root. Your modification will get rid of the quadratic term as well. –  Ross Millikan Dec 8 '11 at 0:41
add comment

2 Answers

up vote 6 down vote accepted

As lhf points out, it isn't hard to produce examples where Newton's Method performs poorly -- pick a function whose derivative vanishes near a root, or whose second derivative is unbounded near a root. Or pick an initial guess far from the root.

However, studying such examples is counterproductive if you're trying to determine its order of convergence: the reason why the method performs poorly in these corner cases is because they violate the assumptions needed to guarantee typical convergence!

In other words, to determine the order of convergence of Newton's method empirically, you should study the best, usual case, not the degenerate cases where the method converges slowly (and where your method will have trouble as well.) If you use double-precision numbers you should have enough digits to estimate the order.

share|improve this answer
    
With double-precision numbers you can only see four or five rounds of precision doubling... Newton's method shines when shown with lots of digits. –  lhf Dec 7 '11 at 22:50
1  
@lhf is spot-on; Newton is most impressively demonstrated in an environment that supports arbitrary precision. If the seed is good enough, you rarely see more than five iterations; not enough to appreciate the quadratic convergence. –  J. M. Dec 7 '11 at 23:13
1  
A more geometric way of looking at things: remember that Newton-Raphson essentially amounts to replacing your function with its tangent line, and finding the root of that tangent line. Since horizontal lines which aren't the horizontal axis don't cross the horizontal axis, it stands to reason that Newton-Raphson will behave quite badly whenever there are tangent lines in the vicinity of your starting point that are horizontal, or nearly so. –  J. M. Dec 7 '11 at 23:19
add comment

Newton's method can get trapped in a periodic cycle. Try for instance $f(x)=x^3-x-3$ with $x_0=0$. For other examples, see

share|improve this answer
    
I also quite like the example with the arctangent and $\mathrm{sign}(x)\sqrt{|x|}$ for displaying cycling... –  J. M. Dec 7 '11 at 23:14
add comment

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.