Xref: utzoo sci.math:3036 comp.graphics:1998
Path: utzoo!mnetor!uunet!husc6!cca!g-rh
From: g-rh@cca.CCA.COM (Richard Harter)
Newsgroups: sci.math,comp.graphics
Subject: Speed of iterative solutions
Message-ID: <25618@cca.CCA.COM>
Date: 16 Mar 88 21:24:26 GMT
References: <1656@thorin.cs.unc.edu> <7662@agate.BERKELEY.EDU> <7741@alice.UUCP> <7735@agate.BERKELEY.EDU>
Reply-To: g-rh@CCA.CCA.COM.UUCP (Richard Harter)
Organization: Computer Corp. of America, Cambridge, MA
Lines: 48
Keywords: Sturm chains, Newton's method

In article <7735@agate.BERKELEY.EDU> greg@skippy.UUCP (Greg) writes:
>
>The whole point of the algorithm is that the root is bracketed in such a way
>that Newton's method will work beautifully.  As a general rule, Newton's
>method either crashes, stumbles in the dark, or converges much more quickly
>than an uninspired method such as regula falsi.  In this case, there are
>no inflection points to interfere.  There may be two roots, which would
>make regula falsi choke, but Newton steps from the two endpoints will
>get you both roots.  If there is one root, you pick the starting endpoint
>based on concavity and again Newton's method can't fail. 

A point that should be mentioned is that there are two algorithms which
look very similar, but which have quite difference performance.  These
are the regula-falsi and the secant algorithms.  The regula falsi algorithm
maintains two bracket points, interpolates between them linearly to get a
new estimate and moves on of the bracket points in.

The secant method retains the *last* two guesses and estimates the zero
using a linear fit to the last two guesses.  The similarity resides in
the fact that both algorithms keep two guesses.  However regula-falsi
has geometric convergence, whereas the convergence rate for the secant
method is e_n+1 = Const * e_n ** 1.618...

The Newton-Raphson iteration convergence rate is quadratic, i.e.
e_n+1 = const * e_n ** 2.  However the Newton-Raphson method requires
two evaluations per iteration, whereas the secant method only requires
one.  The number of places gained, per evaluation, grows geometrically
with a factor of 1.414 for Newton and 1.618 for secant, so that the
secant method is more efficient.

The secant method and the Newton method both are subject to failure of
convergence, and both can be tamed by combining them with a bracketing
strategy.  The secant method is tricky to code correctly because it is
subject to numerical instability.

It should also be noted that the common trick of computing the derivative
by taking the difference between two close points is not the Newton method
and does not have the Newton convergence rate.

If one is creating a routine ad-hoc to iteratively solve an equation
the Newton method is simplest to code and implement.  If one is creating
an iterative zero finder as a library routine, the secant method is
superior.
-- 

In the fields of Hell where the grass grows high
Are the graves of dreams allowed to die.
	Richard Harter, SMDS  Inc.