Families of rational maps and iterative root-finding algorithms. (English) Zbl 0634.30028

This paper develops a rigidity theorem for algebraic families of rational maps with application to the theory of iterative root-finding algorithms.
It answers a question of Smale by showing there is no generally convergent algorithm for finding the roots of a polynomial of degree 4 or more, and settles the case of degree 3 by exhibiting the first known generally convergent algorithm for cubics. (Such an algorithm assigns to each polynomial p a rational map \(T_ p(z)\), depending algebraicly on p, such that under iteration \(T^ n_ p(z)\) tends to a root of p for almost all p and z.)
In the context of conformal dynamics, the main result is: a stable algebraic family of rational maps is either trivial (all its members are conjugate by Möbius transformations) or affine (its members are obtained as quotients of iterated addition on a family of complex tori.) The classification of generally convergent algorithms follows easily from this result.
Another consequence of this rigidity result: the multipliers of a nonaffine rational map along its periodic cycles determine the map up to finite many choices.
The techniques of proof include the theory of holomorphic motions (à la Mañe-Sad-Sullivan), elementary algebraic geometry, and Thurston’s uniqueness result for critically finite rational maps.
Reviewer: C.McMullen


30D05 Functional equations in the complex plane, iteration and composition of analytic functions of one complex variable
65H05 Numerical computation of solutions to single equations
30C62 Quasiconformal mappings in the complex plane
Full Text: DOI Link