Re: REPOST: Re: Flies in the ointment.

From: r.e.s. (r.s_at_ZZmindspring.com)
Date: 03/18/05 

Date: Fri, 18 Mar 2005 19:34:32 GMT

"Tim Peters" <tim.one@comcast.net> wrote ...

> [r.e.s.]
>> Please see also my comment that it is a simple fixed-point iteration
>> obtainable without Newton's method.
>
> Don't you think that's a stretch, though? I do, for two reasons:
>
> 1. General. A zero r of a function f(x) is always a fixed point of a
> Newton-method iteration (well, assuming f'(r) is defined). Deriving
> the same formula from a fixed-point perspective may be an exercise
> in cleverness, but if you can get the same thing directly from
> applying Newton's method, the latter is preferable because entirely
> straightforward.
>
> 2. Specific. You can find the n'th-root Newton method all over the
> web, in its weighted-average and "raw" forms. Heck, it's frequently
> given as a programming assignment in intro numerical analysis
> courses. In these contexts, it's always presented as an application
> of Newton-Raphson (proof: I looked at a lot of course handouts
> Google could find <wink>).

I want to add one more comment to my previous reply on those
two points. The following is a well-known method intended to
improve convergence of fixed-point iterations (or to produce
convergence where there otherwise is none):

If y = h(y), then y = y + p*(h(y)-y), where p is arbitrary.
This is sometimes called a "dampening" or "averaging"
method, with p in [0,1]; note that y = p*h(y) + (1-p)*y.
By adjusting p, the iteration y <- y + p*(h(y)-y) can often
be made to converge in cases where y <- h(y) does not.

In the present case of y^n = x, the natural first attempt
at a fixed-point iteration is y = x/y^(n-1) = h(y), and the
averaging method then gives the revised iteration

y <- p*x/y^(n-1) + (1-p)*y

which is the same algorithm as obtained by Newton-Raphson
if one takes p = 1/n (although other values of p also work).

This method is not so well-known as Newton-Raphson, to be
sure, but I recall it from a numerical analysis course back
in the '60s. It seems remotely possible that the wikipedia
page on the so-called "John Gabriel's" method may have
originated along these lines.