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

McMullen, Curt

Ann. Math. (2) 125, 467-493 (1987).

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

MSC:

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

Keywords:

rational maps; algorithms; conformal dynamics; trivial; affine