On the number of iterations of Newton's method for complex polynomials

DIERK SCHLEICHER

doi:10.1017/S0143385702000482

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We use methods from conformal geometry to give an explicit estimate for how many iterations of Newton's method it takes, at most, to find all the roots of an arbitrary complex polynomial of fixed degree with prescribed precision.

Crossref Citations

This article has been cited by the following publications. This list is generated based on data provided by Crossref.

Mayer, Sebastian and Schleicher, Dierk 2006. Immediate and Virtual Basins of Newton’s Method for Entire Functions. Annales de l'Institut Fourier, Vol. 56, Issue. 2, p. 325.

2007. Numerical Methods for Roots of Polynomials, Part I. Vol. 14, Issue. , p. 131.

Chaiya, Somjate and Atakishiyev, Natig 2011. On the Distance to a Root of Polynomials. Abstract and Applied Analysis, Vol. 2011, Issue. 1,

Smit, Thorsten Türckheim, Friedrich and Mores, Robert 2012. Fast and robust formant detection from LP data. Speech Communication, Vol. 54, Issue. 7, p. 893.

Wahls, Sander and Poor, H. Vincent 2015. Fast Numerical Nonlinear Fourier Transforms. IEEE Transactions on Information Theory, Vol. 61, Issue. 12, p. 6957.

Schleicher, Dierk and Stoll, Robin 2017. Newton's method in practice: Finding all roots of polynomials of degree one million efficiently. Theoretical Computer Science, Vol. 681, Issue. , p. 146.

Leterrier, Nikos 2018. ARES: An efficient approach to adaptive time integration for stiff Differential-Algebraic Equations. Computers & Chemical Engineering, Vol. 119, Issue. , p. 46.

Fontana, Federico and Bozzo, Enrico 2019. Newton–Raphson Solution of Nonlinear Delay-Free Loop Filter Networks. IEEE/ACM Transactions on Audio, Speech, and Language Processing, Vol. 27, Issue. 10, p. 1590.

De Zotti, Alexandre 2020. Advancements in Complex Analysis. p. 519.

Campos, Beatriz Canela, Jordi Garijo, Antonio and Vindel, Pura 2021. DYNAMICS OF A FAMILY OF RATIONAL OPERATORS OF ARBITRARY DEGREE. Mathematical Modelling and Analysis, Vol. 26, Issue. 2, p. 188.

Chaiya, Malinee and Chaiya, Somjate 2022. A Uniform Bound for the Distance to a Root of Complex Polynomials Under Newton’s Method. Bulletin of the Iranian Mathematical Society, Vol. 48, Issue. 6, p. 3619.

Faulstich, Fabian M. and Laestadius, Andre 2023. Homotopy continuation methods for coupled-cluster theory in quantum chemistry. Molecular Physics,

Schleicher, Dierk 2023. On the efficient global dynamics of Newton’s method for complex polynomials. Nonlinearity, Vol. 36, Issue. 2, p. 1349.

Faulstich, Fabian M. 2024. Recent mathematical advances in coupled cluster theory. International Journal of Quantum Chemistry, Vol. 124, Issue. 13,

Randig, Marvin Schleicher, Dierk and Stoll, Robin 2024. Newton’s method in practice, II: The iterated refinement Newton method and near-optimal complexity for finding all roots of some polynomials of very large degrees. Journal of Computational and Applied Mathematics, Vol. 437, Issue. , p. 115427.

Article contents

On the number of iterations of Newton's method for complex polynomials

Abstract

Information

Save article to Kindle

Save article to Dropbox

Save article to Google Drive

Reply to: Submit a response

Your details

You have entered the maximum number of contributors

Conflicting interests