Re: Vector Rotation

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
--
.

Relevant Pages

  • Re: Recursion to Iteration
    ... Willem writes: ... Almost any algorithm involving a ... )> loop can be rewritten recursively. ... the first iteration the code will access freed memory at q=p->next. ...
    (comp.programming)
  • Re: Recursion to Iteration
    ... Almost any algorithm involving a ... )> loop can be rewritten recursively. ... the first iteration the code will access freed memory at q=p->next. ... You all think I'm paranoid, ...
    (comp.programming)