Re: Vector Rotation


"Carlos Moreno" <moreno_at_mochima_dot_com@xxxxxxxxxxxxxx> wrote in message
news:5aOMf.25582$Qs1.604698@xxxxxxxxxxxxxxxxxxxxxxx
Clay S. Turner wrote:

I'm pretty certain that for the square root, N-R is guaranteed
to work (don't know of any proof, but I wouldn't be surprised
if it has been rigorously proven) -- if you start with an initial
estimate of x (for the sqrt(x)) if x > 1, and 1 if x < 1.

Actually the Newton - Raphson method is quadratically convergent in the
limit of the point of convergence. However, it can be painfully slow. For
example try using this for sqrt(x) with x near zero. Here the derivative
causes a real problem. The region of convergence is very small for x
small. And it is easy to have a seed fall outside of this region

Huh?? You can not fall outside the region of convergence if you
are at a value that is greater than the square root. That's why
if you start at x = 1 (to compute x = sqrt(a) where a < 1), there
is no way that the algorithm can diverge.

In fact, now that I think about it, for *any* value greater than
the solution, the algorithm converges, which means that for any
starting value > 0, the algorithm converges (floating-point
inaccuracy and rounding errors aside), since in the worst case,
the first iteration will send the value from a very small number
to a very large value, but then, from that large value we have
the guarantee that we'll converge.

For instance, it takes 20 iterations to obtain the square root of
0.01 with an initial estimate of 10 million. About 13 iterations
if we start at 0.0000001, since after the first iteration, the
estimate jumps to 50000 -- and then, from there it begins to go
monotonically down, approaching 0.1

If you start at 1, it takes 7 iterations to get to 0.1 (with
6 decimal places accuracy) -- I guess that's quite slow,
depending on the application.

Binary search, I guess?

Carlos
--

Hello Carlos,

One of the standard tricks in hardware is to have a fixed number of
iterations. This is so the algo can be pipelined. So using the constraint of
a fixed number of iterations is how I arrived at a region of convergence
that gets smaller for x small. The region is determined as the domain of the
seed so that after the fixed number of iterations the result is within a
prespecified epsilon of the true answer. The algo that pairs bits and uses
trial subtractions, will produce a known precision given a priori known
number of iterations. In this algo, the square root is the same order of
complexity as a division.

Clay




.

Relevant Pages

  • Re: CMS: where are the zeroes ?
    ... of iterations, that appear to the left of the y,-y axis ... convergence to $z=3D1$ is of order $\frac}$. ... showing the scaled zeros and that ...
    (sci.math)
  • Re: Fixed point iteration
    ... Perhaps if you can point me to some standard techniques ... >> proofs which prove that lattice is of fixed height. ... are you looking for convergence in the limit or after a finite ... > number of iterations? ...
    (comp.theory)
  • Re: Attaction of Fixed Points
    ... >understanding this. ... I am not sure if there is a non-empirical way to tell "how many" iterations ... multiplier of a fixed point is, the fastest the convergence. ...
    (sci.math)
  • help on a proof of convergence (an exercise problem)
    ... I have a question on how to prove the convergence of the following ... For iterations ... Can anyone give me a help or hint? ...
    (sci.math)
  • Re: Loop Efficiency
    ... although the array is untouched. ... Algo 1 took 24828ms for 10000 iterations ... private void makeData{ ...
    (comp.lang.java.programmer)