On approximate zeros and rootfinding algorithms for a complex polynomial
Author:
MyongHi Kim
Journal:
Math. Comp. 51 (1988), 707719
MSC:
Primary 65H05; Secondary 30C15, 65E05
MathSciNet review:
958638
Fulltext PDF Free Access
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 kthorder Euler method. An approximate zero for the kthorder 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., McGrawHill 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
(80c:30001)
 [2]
Louis
de Branges, A proof of the Bieberbach conjecture, Acta Math.
154 (1985), no. 12, 137–152. MR 772434
(86h:30026), http://dx.doi.org/10.1007/BF02392821
 [3]
Peter
Henrici, Applied and computational complex analysis,
WileyInterscience [John Wiley & Sons], New YorkLondonSydney, 1974.
Volume 1: Power series—integration—conformal
mapping—location of zeros; Pure and Applied Mathematics. MR 0372162
(51 #8378)
 [4]
Einar
Hille, Analytic function theory. Vol. II, Introductions to
Higher Mathematics, Ginn and Co., Boston, Mass.New YorkToronto, Ont.,
1962. MR
0201608 (34 #1490)
 [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
(37 #1562)
 [8]
Curt
McMullen, Families of rational maps and iterative rootfinding
algorithms, Ann. of Math. (2) 125 (1987), no. 3,
467–493. MR
890160 (88i:58082), http://dx.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
(87m:68043)
 [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
(87m:68044), http://dx.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
(89d:65054), http://dx.doi.org/10.1016/0885064X(86)900208
 [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
(83i:65044), http://dx.doi.org/10.1090/S027309791981148588
 [13]
Steve
Smale, On the efficiency of algorithms of
analysis, Bull. Amer. Math. Soc. (N.S.)
13 (1985), no. 2,
87–121. MR
799791 (86m:65061), http://dx.doi.org/10.1090/S027309791985153911
 [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
(88e:65076)
 [1]
 L. V. Ahlfors, Complex Analysis, International Series in Pure and Applied Math., 1979. MR 510197 (80c:30001)
 [2]
 L. De Branges, "A proof of the Bieberbach conjecture," Acta Math., v. 154, 1985, pp. 137152. MR 772434 (86h:30026)
 [3]
 P. Henrici, Applied and Computational Complex Analysis, Wiley, New York, 1977. MR 0372162 (51:8378)
 [4]
 E. Hille, Analytic Function Theory, Ginn, Boston, Mass., 1962. MR 0201608 (34:1490)
 [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]
 M. Marden, Geometry of Polynomials, Math. Surveys, No. 3, Amer. Math. Soc., Providence, R. I., 1966. MR 0225972 (37:1562)
 [8]
 C. McMullen, "Families of rational maps and iterative rootfinding algorithms," Ann. of Math., v. 125, 1987, pp. 467494. MR 890160 (88i:58082)
 [9]
 M. Shub & S. Smale, "Computational complexity: On the geometry of polynomials and a theory of cost; Part I," Ann. Sci. École Norm. Sup. Ser. (4), v. 18, 1985, pp. 107142. MR 803197 (87m:68043)
 [10]
 M. Shub & S. Smale, "Computational complexity: On the geometry of polynomials and a theory of cost; Part II," SIAM J. Comput., v. 15, 1986, pp. 145161. MR 822199 (87m:68044)
 [11]
 M. Shub & S. Smale, "On the existence of generally convergent algorithms," J. of Complexity, v. 2, 1986, pp. 211. MR 925341 (89d:65054)
 [12]
 S. Smale, "The fundamental theorem of algebra and complexity theory," Bull. Amer. Math. Soc., v. 4, 1981, pp. 136. MR 590817 (83i:65044)
 [13]
 S. Smael, "On the efficiency of algorithms of analysis," Bull. Amer. Math. Soc., v. 13, 1985, pp. 87121. MR 799791 (86m:65061)
 [14]
 S. Smale, "Newton's method estimates from data at one point," The Merging Disciplines: New Directions in Pure, Applied and Computational Mathematics, pp. 185 196, SpringerVerlag, 1986. MR 870648 (88e:65076)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
65H05,
30C15,
65E05
Retrieve articles in all journals
with MSC:
65H05,
30C15,
65E05
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718198809586381
PII:
S 00255718(1988)09586381
Article copyright:
© Copyright 1988
American Mathematical Society
