I haven't been following this thread, but I want to mention that Peter Doyle and Curt McMullen made a global analysis of all possible root-finding algorithms for polynomials that involve iterating an complex analytic function of one variable with parameters depending on the coefficients of the polynomial. (Newton's method is one such iteration, but it gets trapped in unproductive loops with positive probability already for cubics. They showed that algorithms can be constructed that converge a.s. for polynomials of degrees 1 through 5, but no such method converges a.s. to a root for polynomials of degree 6 or higher. The proof is based on the fact that the simple parts of Galois groups through degree 5 are all automorphism groups of polyhedra, but this is false for higher degrees. The construction for quintics is ingenious, making essential use of the theory Klein developed describing invariants for the icosahedral group, expressing them in terms of the rational functions that describes the map of CP^1 to its symmetry quotient by the icosahedral group. I think these methods are all super-exponential once they're in the attracting basin, but I don't remember Bill On Sep 17, 2010, at 7:41 AM, Fred lunnon wrote:
That's one sophisticated root-finding algorithm!
Henry has evidently researched Henrici's algorithm more thoroughly than I --- but my recollection is that there's no connection. WFL
On 9/16/10, Victor Miller <victorsmiller@gmail.com> wrote:
How is it related to Schonhage's splitting circle method? http://en.wikipedia.org/wiki/Splitting_circle_method
Victor
On Thu, Sep 16, 2010 at 1:29 PM, Fred lunnon <fred.lunnon@gmail.com> wrote:
On 9/16/10, Joerg Arndt <arndt@jjj.de> wrote:
... This may not be what you have in mind but there are methods to find _all_ roots simultaneously, see e.g. http://en.wikipedia.org/wiki/Durand-Kerner_method and the references at the bottom of the page
A very elegant method which computes all roots simultaneously, yielding circles in which they are guaranteed to lie, is buried (I don't remember exactly where --- anybody else know?) in the strangely neglected
Henrici P., Applied and Computational Complex Analysis (Wiley). [Three volumes: 1974, 1977, 1986.]
It's interesting that these methods actually gain in speed and stability by simultaneity, as opposed to attempting to exclude the other roots.
WFL
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun