On approximate zeros and rootfinding algorithms for a complex polynomial

Author:
Myong-Hi Kim

Journal:
Math. Comp. **51** (1988), 707-719

MSC:
Primary 65H05; Secondary 30C15, 65E05

DOI:
https://doi.org/10.1090/S0025-5718-1988-0958638-1

MathSciNet review:
958638

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper we give criteria for a complex number to be an approximate zero of a polynomial *f* for Newton's method or for the *k*th-order Euler method. An approximate zero for the *k*th-order Euler method is an initial point from which the method converges with an order Also, we construct families of Newton (and Euler) type algorithms which are surely convergent.

**[1]**Lars V. Ahlfors,*Complex analysis*, 3rd ed., McGraw-Hill Book Co., New York, 1978. An introduction to the theory of analytic functions of one complex variable; International Series in Pure and Applied Mathematics. MR**510197****[2]**Louis de Branges,*A proof of the Bieberbach conjecture*, Acta Math.**154**(1985), no. 1-2, 137–152. MR**772434**, https://doi.org/10.1007/BF02392821**[3]**Peter Henrici,*Applied and computational complex analysis*, Wiley-Interscience [John Wiley & Sons], New York-London-Sydney, 1974. Volume 1: Power series—integration—conformal mapping—location of zeros; Pure and Applied Mathematics. MR**0372162****[4]**Einar Hille,*Analytic function theory. Vol. II*, Introductions to Higher Mathematics, Ginn and Co., Boston, Mass.-New York-Toronto, Ont., 1962. MR**0201608****[5]**M. Kim,*Computational Complexity of the Euler Type Algorithms for the Roots of Complex Polynomials*, Thesis, City University of New York, 1985.**[6]**M. Kim, "Improved criteria for an approximate zero and experimental results on the polynomial root finding problem," in preparation.**[7]**Morris Marden,*Geometry of polynomials*, Second edition. Mathematical Surveys, No. 3, American Mathematical Society, Providence, R.I., 1966. MR**0225972****[8]**Curt McMullen,*Families of rational maps and iterative root-finding algorithms*, Ann. of Math. (2)**125**(1987), no. 3, 467–493. MR**890160**, https://doi.org/10.2307/1971408**[9]**Mike Shub and Steven Smale,*Computational complexity. On the geometry of polynomials and a theory of cost. I*, Ann. Sci. École Norm. Sup. (4)**18**(1985), no. 1, 107–142. MR**803197****[10]**M. Shub and S. Smale,*Computational complexity: on the geometry of polynomials and a theory of cost. II*, SIAM J. Comput.**15**(1986), no. 1, 145–161. MR**822199**, https://doi.org/10.1137/0215011**[11]**Michael Shub and Steve Smale,*On the existence of generally convergent algorithms*, J. Complexity**2**(1986), no. 1, 2–11. MR**925341**, https://doi.org/10.1016/0885-064X(86)90020-8**[12]**Steve Smale,*The fundamental theorem of algebra and complexity theory*, Bull. Amer. Math. Soc. (N.S.)**4**(1981), no. 1, 1–36. MR**590817**, https://doi.org/10.1090/S0273-0979-1981-14858-8**[13]**Steve Smale,*On the efficiency of algorithms of analysis*, Bull. Amer. Math. Soc. (N.S.)**13**(1985), no. 2, 87–121. MR**799791**, https://doi.org/10.1090/S0273-0979-1985-15391-1**[14]**Steve Smale,*Newton’s method estimates from data at one point*, The merging of disciplines: new directions in pure, applied, and computational mathematics (Laramie, Wyo., 1985) Springer, New York, 1986, pp. 185–196. MR**870648**

Retrieve articles in *Mathematics of Computation*
with MSC:
65H05,
30C15,
65E05

Retrieve articles in all journals with MSC: 65H05, 30C15, 65E05

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1988-0958638-1

Article copyright:
© Copyright 1988
American Mathematical Society