Xref: utzoo sci.physics:17538 sci.math:15804 comp.theory.dynamic-sys:193
Path: utzoo!news-server.csri.toronto.edu!csri.toronto.edu!hofbauer
Newsgroups: sci.physics,sci.math,comp.theory.dynamic-sys
From: hofbauer@csri.toronto.edu (John Hofbauer)
Subject: Re: Newton's method (was square roots by hand or computer)
Message-ID: <1991Mar17.120702.9205@jarvis.csri.toronto.edu>
Organization: CSRI, University of Toronto
Date: 17 Mar 91 17:07:02 GMT
Lines: 21

> Now the only problem is a starting value. ...
    [lots of stuff deleted]

It must be remembered that Newton's Method is only locally convergent.
If you start within the region of local convergence it will converge
quadratically (the number of correct digits doubles with each iteration).
The problem is finding the region of local convergence. This is generally
impractical and so you just rely on luck. Pick an arbitrary starting
value and let the algorithm bounce around until you fall into the
region of local convergence and then away you go. For square root
you are actually finding the positive root of x**2 - a = 0, which
has a comfortably large region of local convergence. The SQRT routine
on your favourite computer uses Newton's Method. The starting value
is determined from a simple linear min-max approximation which guarantees
that the first 3 bits are correct. Three iterations gives full 24-bit
single precision accuracy. Finding roots of arbitrary polynomials gets
trickier. Some roots lie arbitrarily close to one end of the region of
local convergence, so even if you started with a value very close to
the root, the iteration may converge to some other root. This can
be vary frustrating if you are trying to find all the roots. I speak
from first hand experience.