[math-fun] "Solving Cubic Equations By the Quadratic Formula"
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
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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
[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
participants (2)
-
Henry Baker -
Mike Speciner