From: Peter Percival <peter.percival@cwcom.net>
Subject: Re: Square Root Error
Date: Wed, 24 May 2000 22:15:32 +0100
Newsgroups: sci.math
Summary: [missing]

"Zdislav V. Kovarik" wrote:
> 
> In article <8ges9v$32e$1@nnrp1.deja.com>,  <cs31415926@my-deja.com> wrote:
> :Using the formula x[new] = (1/2)(x + a/x), one can approximate the
> :square root of a. But how quickly does it converge, and what is the
> :maximum possible error?
> 
> This is a classic - and no chaos is involved.
> 
> Change the variable by
> 
>   (x - sqrt(a)) / (x + sqrt(a)) = y
> 
>   (x[new] - sqrt(a)) / (x[new] + sqrt(a)) = y[new]
> 
> simplify and see what happens. (I mean, establish an equation between
> y[new] and y.) Do the algebra.
> 
>  As for "maximum error", the the question needs restatement. Guessing what
> it might be, I'd answer that the maximum error between the first two
> iterations does not exist (individual errors can be arbitrarily large).
> Any extra conditions on the starting guess?
> 
>  Fractal boundary, in complex case, occurs for cube root calculations
> using Newton's method. I am told that it was Cayley who found out that he
> did not have the machinery to describe the regions of attraction, and it

A one-page paper "The Newton-Fourier Imaginary Problem" by Sir Arthur
Cayley in the American Journal of Mathematics, 2, 1879 describes the
"Newton formula" x_next = x - f(x)/f'(x)  [his notation is different]
and proposes considering equations with complex coefficients thus
generating a sequence of points P, P_1, ... in the plane.  His paper
ends:
"... The problem is to determine the regions of the plane, such that P
being taken at pleasure anywhere within one region we arrive ultimately
at the point A; anywhere within another region at point B; and so for
the several points representing the roots of the equation.
  The solution is easy and elegant in the case of a quadratic equation,
but the next succeeding case of the cubic equation appears to present
considerable difficulty."
Quoted without permission.

> was Julia anf Fatou who started the study of iterations along these lines.
> 
> Cheers, ZVK(Slavek)