On the existence of generally convergent algorithms

DOI10.1016/0885-064X(86)90020-8MaRDI QIDQ1077876zbMATH OpenOpenAlexFDO

Authors Michael Shub, Stephen Smale

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

convergenceiterative algorithmsNewton's methodzeros of polynomials

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)

Recommendations

• Braiding of the attractor and the failure of iterative algorithms
• scientific article; zbMATH DE number 3856296
• scientific article; zbMATH DE number 4095835
• Families of rational maps and iterative root-finding algorithms
• How to be sure of finding a root of a complex polynomial using Newton's method

Cites work

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

Cited in

(23)

• On invariant volumes of codimension-one Anosov flows and the Verjovsky conjecture
• On Approximate Zeros and Rootfinding Algorithms for a Complex Polynomial
• Perspectives on information-based complexity
• McMullen’s root-finding algorithm for cubic polynomials
• scientific article; zbMATH DE number 4144336 (Why is no real title available?)
• Some informational requirements for convergence
• Recent developments in information-based complexity
• Algorithms with mediant convergents and their metrical theory
• A polynomial-time algorithm, based on Newton's method, for linear programming
• Julia sets for the super-Newton method, Cauchy’s method, and Halley’s method
• scientific article; zbMATH DE number 13215 (Why is no real title available?)
• On a general \(\rho\)-algorithm
• Newton's method and complex dynamical systems
• Geometric analysis of nondeterminacy in dynamical systems
• On a generalization of the \(\epsilon\)-algorithm
• Some remarks on Smale's “Algorithms for solving equations”
• Families of rational maps and convergence basins of Newton's method
• Solving the quintic by iteration
• Braiding of the attractor and the failure of iterative algorithms
• On general convergence in extracting radicals via a fundamental family of iteration functions
• Families of rational maps and iterative root-finding algorithms
• Some connections of complex dynamics
• Some aspects of studying an optimization or decision problem in different computational models

This page was built for publication: On the existence of generally convergent algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1077876)