##
**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.

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