On the existence of generally convergent algorithms

DOI10.1016/0885-064X(86)90020-8zbMath0595.65048OpenAlexW1969872508MaRDI QIDQ1077876

Stephen Smale, Michael Shub

Publication date: 1986

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0885-064x(86)90020-8

zbMATH Keywords

convergenceNewton's methodzeros of polynomialsiterative algorithms

Mathematics Subject Classification ID

Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral) (30C15) Numerical computation of solutions to single equations (65H05)

Related Items

Some remarks on Smale's “Algorithms for solving equations”, Perspectives on information-based complexity, Braiding of the attractor and the failure of iterative algorithms, A polynomial-time algorithm, based on Newton's method, for linear programming, Geometric analysis of nondeterminacy in dynamical systems, Newton's method and complex dynamical systems, McMullen’s root-finding algorithm for cubic polynomials, Recent developments in information-based complexity, Solving the quintic by iteration, Some Connections of Complex Dynamics, Julia sets for the super-Newton method, Cauchy’s method, and Halley’s method, On invariant volumes of codimension-one Anosov flows and the Verjovsky conjecture, Families of rational maps and convergence basins of Newton's method, On Approximate Zeros and Rootfinding Algorithms for a Complex Polynomial, Some aspects of studying an optimization or decision problem in different computational models

Cites Work

• Unnamed Item
• Unnamed Item
• Families of rational maps and iterative root-finding algorithms
• Any iteration for polynomial equations using linear information has infinite complexity
• On the dynamics of rational maps
• Rate of Approach to Minima and Sinks--The Morse-Smale Case
• On the efficiency of algorithms of analysis
• Morse Theory. (AM-51)
• The fundamental theorem of algebra and complexity theory
• Global Convergence of a Modified Newton Iteration for Algebraic Equations
• On Algorithms for Solvingf(x)=0
• On the Efficiency of Newton's Method in Approximating All Zeros of a System of Complex Polynomials
• Invariant manifolds