On approximate zeros and rootfinding algorithms for a complex polynomial

Kim, Myong-Hi

doi:10.1090/S0025-5718-1988-0958638-1

On approximate zeros and rootfinding algorithms for a complex polynomial
HTML articles powered by AMS MathViewer

by Myong-Hi Kim PDF

Math. Comp. 51 (1988), 707-719 Request permission

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 kth-order Euler method. An approximate zero for the kth-order Euler method is an initial point from which the method converges with an order $(k + 1)$ Also, we construct families of Newton (and Euler) type algorithms which are surely convergent.

References

Lars V. Ahlfors, Complex analysis, 3rd ed., International Series in Pure and Applied Mathematics, McGraw-Hill Book Co., New York, 1978. An introduction to the theory of analytic functions of one complex variable. MR 510197
Louis de Branges, A proof of the Bieberbach conjecture, Acta Math. 154 (1985), no. 1-2, 137–152. MR 772434, DOI 10.1007/BF02392821
Peter Henrici, Applied and computational complex analysis, Pure and Applied Mathematics, Wiley-Interscience [John Wiley & Sons], New York-London-Sydney, 1974. Volume 1: Power series—integration—conformal mapping—location of zeros. MR 0372162
Einar Hille, Analytic function theory. Vol. II, Introductions to Higher Mathematics, Ginn and Company, Boston, Mass.-New York-Toronto, Ont., 1962. MR 0201608

Computational Complexity of the Euler Type Algorithms for the Roots of Complex Polynomials

Morris Marden, Geometry of polynomials, 2nd ed., Mathematical Surveys, No. 3, American Mathematical Society, Providence, R.I., 1966. MR 0225972
Curt McMullen, Families of rational maps and iterative root-finding algorithms, Ann. of Math. (2) 125 (1987), no. 3, 467–493. MR 890160, DOI 10.2307/1971408
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
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, DOI 10.1137/0215011
Michael Shub and Steve Smale, On the existence of generally convergent algorithms, J. Complexity 2 (1986), no. 1, 2–11. MR 925341, DOI 10.1016/0885-064X(86)90020-8
Steve Smale, The fundamental theorem of algebra and complexity theory, Bull. Amer. Math. Soc. (N.S.) 4 (1981), no. 1, 1–36. MR 590817, DOI 10.1090/S0273-0979-1981-14858-8
Steve Smale, On the efficiency of algorithms of analysis, Bull. Amer. Math. Soc. (N.S.) 13 (1985), no. 2, 87–121. MR 799791, DOI 10.1090/S0273-0979-1985-15391-1
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