[We're talking about the case where p'(z) doesn't have a double root.] Yes, I noticed that, too, after I made the posting. The paper said that the algorithm was starting from the roots of p'(z), and that it was using a Newton iteration. I looked at the paper again, briefly, but the particular equation for the iteration was too dense. Perhaps I should email the author. At 05:07 AM 5/16/2014, Mike Speciner wrote:
Huh? Isn't p'(z_0) == 0 ?
On 2014-05-15 15:50, Henry Baker wrote:
FYI -- basins of attraction; Voronoi cells.
Given a monic cubic equation p(z)=0, consider the roots r1,r2 of quadratic equation p'(z)=0.
Timeshare/interlace 2 Newton methods [z_n+1 = z_n-p(z_n)/p'(z_n)] on quadratic solutions z_0=r1, r2. The Newton method of one of these starting points is guaranteed to converge to a root z_oo=r3 of p(z), i.e., p(r3)=0.
Yes, we double the work per iteration, but we are at least guaranteed to converge to one root.
Then solve the quadratic p(z)/(z-r3) for the other 2 roots.
http://arxiv.org/abs/1401.5148
Bahman Kalantari