×

On the geometry of polynomials and a theory of cost. I. (English) Zbl 0603.65027

The general field of the research reported here is the study of algorithms for polynomial root finding, and in particular an algorithm which the authors describe as an ”incremental” version of that of Euler for determining an approximate zero of a complex polynomial. The authors’ principal result is to show that the number of iterations of the algorithm is linearly related to the degree of the polynomial. Indeed their main theorem, which requires a somewhat lengthy proof, gives a good estimate of the number of iterations required.
Reviewer: J.Oliver

MSC:

65H05 Numerical computation of solutions to single equations
30C15 Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral)
PDF BibTeX XML Cite
Full Text: DOI Numdam EuDML

References:

[1] K. ATKINSON , An Introduction to Numerical Analysis , Wiley, New York, 1978 . MR 80a:65001 | Zbl 0402.65001 · Zbl 0402.65001
[2] E. DURAND , Solutions Numériques de Équations Algébriques , Masson, Paris, 1960 . · Zbl 0099.10801
[3] P. DUREN , Coefficients of Univalent Functions (Bull. Amer. Math. Soc., Vol. 83, No. 5, 1977 , pp. 891-911). Article | MR 57 #9943 | Zbl 0372.30012 · Zbl 0372.30012
[4] L. EULER , Institutiones Calculi Differentialis II , exp. IX. Opera Omnia, Serie I, Vol. X, pp. 422-455.
[5] W. HAYMAN , Multivalent Functions , Cambridge Univ. Press : Cambridge, Eng., 1958 . Zbl 0082.06102 · Zbl 0082.06102
[6] P. HENRICI , Applied and Computational Complex Analysis , Wiley, New York, 1977 . MR 56 #12235 · Zbl 0363.30001
[7] E. HILLE , Analytic Function Theory , II Ginn, Boston, 1962 . MR 34 #1490 | Zbl 0102.29401 · Zbl 0102.29401
[8] A. S. HOUSEHOLDER , The Numerical Treatment of a Single Nonlinear equation , McGraw-Hill, New York, 1970 . MR 52 #9593 | Zbl 0242.65047 · Zbl 0242.65047
[9] S. LANG , Algebra , Addison-Wesley, Reading, Mass, 1965 . MR 33 #5416 | Zbl 0193.34701 · Zbl 0193.34701
[10] A. OSTROWSKI , Solutions of equations in Euclidean and Banach Spaces , Academic Press, New York, 1973 . MR 50 #11760 | Zbl 0304.65002 · Zbl 0304.65002
[11] G. SAUNDERS , Thesis , U. C. Berkeley, 1982 .
[12] E. SCHRÖDER , Ueber unendlich viele Algorithmen zur Auflösing der Gleichungen (Math. Ann. 2, 1870 , pp. 317-365). Article | JFM 02.0042.02 · JFM 02.0042.02
[13] S. SMALE , The Fundamental Theorem of Algebra and Complexity Theory (Bull, Amer. Math. Soc., Vol. 4, No. 1, 1981 , pp. 1-36. Article | MR 83i:65044 | Zbl 0456.12012 · Zbl 0456.12012
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.