next up previous
Next: Towers of Algorithms. Up: Solving the quintic by Previous: Galois Theory of Rigid

Purely Iterative Algorithms.

In this section, generally convergent purely iterative algorithms are introduced and we prove that the correspondences they compute are rigid.

Definitions. An purely iterative algorithm tex2html_wrap_inline1967 is a rational map


carrying the input variety V into the space of tex2html_wrap_inline1971 of rational endomorphisms of the Riemann sphere of degree d. To avoid special considerations of `elementary rational maps', we will always assume that d is >1.

Let k denote the function field K(V); then T is simply an element of k(z).

The algorithm is generally convergent if tex2html_wrap_inline1987 converges for all (v,z) in an open dense subset of tex2html_wrap_inline1991 . (Here tex2html_wrap_inline1993 denotes the nth iterate of the map T).

The map tex2html_wrap_inline1999 can be thought of as a fixed procedure for improving the initial guess z. The output of the algorithm is described by the set


Since different w may converge to different limits, the output can be multivalued.

A family of rational maps is rigid if there is a fixed rational map f(z) such that tex2html_wrap_inline2007 is conjugate to f(z) for all v in a Zariski open subset of V.

T 3.1. A generally convergent algorithm is a rigid family of rational maps.

This is a consequence of the general rigidity theorem for stable algebraic families, exactly as in Theorem 1.1 of [11].

C 3.2. The output of a purely iterative algorithm is a finite union of rigid correspondences.

Proof. The output W is a finite union of components of the algebraic set tex2html_wrap_inline2017 ; each component is a variety. The Möbius transformation conjugating tex2html_wrap_inline2019 to the fixed model f(z) carries the output of tex2html_wrap_inline2023 to the attractor A of f, so each component is a rigid correspondence.

To make examples of generally convergent algorithms, one must check that a given iteration will converge for most initial guesses. Here is one special but useful criterion. A rational map f(z) is critically finite if every critical point c is eventually periodic (there exist n > m > 0 such that tex2html_wrap_inline2035 ). A periodic cycle which includes a critical point is said to be superattracting.

T 3.3. Let f(z) be a critically finite rational map, A the union of its superattracting cycles. Then either

A is empty and the action of f on tex2html_wrap_inline2043 is ergodic, or
A is nonempty, and tex2html_wrap_inline2047 tends to a cycle of A for all z in an open, full measure subset of tex2html_wrap_inline2051 .

In case every critical point eventually lands in A, f(z) belongs to the general class of `expanding' rational maps, for which the result is proven in [18]. The general case can be handled similarly, using orbifolds. This is sketched for polynomials by Douady and Hubbard [3]; the orbifold approach for general critically finite maps is discussed in [19].

All examples of generally convergent algorithms we will consider employ critically finite maps. In practical terms, these maps have two benefits: convergence is assured almost everywhere, not just on an open dense set; and convergence is asymptotically quadratic (for a fixed convergent initial guess, tex2html_wrap_inline2057 digits of accuracy are obtained in O(N) iterations).

Examples of purely iterative algorithms.


(1) Newton's method. Let tex2html_wrap_inline2063 and let tex2html_wrap_inline2065 . Then T is a purely iterative algorithm, and it is generally convergent for d=2 but not for d=3 or more (Figure 2; see also [17]).

Figure 2: Newton's method can fail for cubics.

(2) Extracting radicals. Let tex2html_wrap_inline2073 denote the set of polynomials tex2html_wrap_inline2075 . The restriction of Newton's method to V is generally convergent; thus one can reliably extract radicals. The critical points of tex2html_wrap_inline2079 occur at the roots of p (which are fixed) and at z=0 (which maps to tex2html_wrap_inline2085 under one iteration, and then remains fixed); thus tex2html_wrap_inline2087 is critically finite, and by Theorem 3.3, almost every initial guess converges to a root.

Rigidity of the algorithm tex2html_wrap_inline2089 is easily verified, using the affine invariance of Newton's method.

(3) Solving the cubic. The roots of tex2html_wrap_inline2091 can be reliably determined by applying Newton's method to the rational function


The critical points of tex2html_wrap_inline2093 coincide with the roots of p, and are fixed, so again Theorem 3.3 may be applied to verify convergence.

(4) Insolvability of the quartic. Since the roots of two quartics are generally not related by a Möbius transformation (the cross-ratio of the roots must agree), the roots of polynomials of degree 4 (or more) cannot be computed by a generally convergent algorithm.

A more topological discussion of the insolvability of the quartic, using braids, appears in [12].

next up previous
Next: Towers of Algorithms. Up: Solving the quintic by Previous: Galois Theory of Rigid

Peter Doyle