8
$\begingroup$

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?

$\endgroup$
3
  • 1
    $\begingroup$ I expect you have tested Newton-Raphson, and your alternative, on say $x^8=0$. $\endgroup$
    – André Nicolas
    Commented Dec 7, 2011 at 21:10
  • 1
    $\begingroup$ I presume you've seen this? $\endgroup$
    – J. M. ain't a mathematician
    Commented Dec 7, 2011 at 23:13
  • 1
    $\begingroup$ 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. $\endgroup$
    – Ross Millikan
    Commented Dec 8, 2011 at 0:41

2 Answers 2

Reset to default
7
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – lhf
    Commented Dec 7, 2011 at 22:50
  • 1
    $\begingroup$ @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. $\endgroup$
    – J. M. ain't a mathematician
    Commented Dec 7, 2011 at 23:13
  • 2
    $\begingroup$ 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. $\endgroup$
    – J. M. ain't a mathematician
    Commented Dec 7, 2011 at 23:19
6
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ I also quite like the example with the arctangent and $\mathrm{sign}(x)\sqrt{|x|}$ for displaying cycling... $\endgroup$
    – J. M. ain't a mathematician
    Commented Dec 7, 2011 at 23:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .