On the existence of generally convergent algorithms
Let \(F_ d\) be the space of polynomials of degree \(\leq d\) and let S be the Riemann sphere \({\mathbb{C}}\cup \{\infty \}\). Then Newton's method \(N: F_ d\times S\to S\) with \(N(f,z):=z-f(z)/f'(x)\) is rational over \({\mathbb{C}}\) in f and z. If f is sufficiently close to a zero \(\zeta\) of f, then the iterates \(z_ k=N^ k(f,z_{k-1})\) converge to \(\zeta\) as \(k\to \infty\). However it has been shown, e.g., in earlier papers of the second author that there is an open set U in \(F_ d\times S\) (if \(d>2)\) such that this convergence will not happen for (f,z)\(\in U\). In the present paper it is shown that if one adds the operation of complex conjugation to the rational operations, then there do exist convergent purely iterative algorithms for finding zeros of polynomials.
- 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
- scientific article; zbMATH DE number 3791008 (Why is no real title available?)
- scientific article; zbMATH DE number 3055967 (Why is no real title available?)
- Invariant manifolds
- Morse Theory. (AM-51)
- On Algorithms for Solvingf(x)=0
- On the dynamics of rational maps
- On the efficiency of algorithms of analysis
- On the Efficiency of Newton's Method in Approximating All Zeros of a System of Complex Polynomials
- Rate of Approach to Minima and Sinks--The Morse-Smale Case
- The fundamental theorem of algebra and complexity theory
- Families of rational maps and iterative root-finding algorithms
- Some informational requirements for convergence
- Braiding of the attractor and the failure of iterative algorithms
- A polynomial-time algorithm, based on Newton's method, for linear programming
- Newton's method and complex dynamical systems
- Families of rational maps and convergence basins of Newton's method
- On a generalization of the -algorithm
- Some aspects of studying an optimization or decision problem in different computational models
- On general convergence in extracting radicals via a fundamental family of iteration functions
- Some connections of complex dynamics
- scientific article; zbMATH DE number 4144336 (Why is no real title available?)
- On Approximate Zeros and Rootfinding Algorithms for a Complex Polynomial
- Recent developments in information-based complexity
- scientific article; zbMATH DE number 13215 (Why is no real title available?)
- Perspectives on information-based complexity
- McMullen’s root-finding algorithm for cubic polynomials
- Some remarks on Smale's “Algorithms for solving equations”
- Julia sets for the super-Newton method, Cauchy’s method, and Halley’s method
- On a general -algorithm
- On the algebraic complexity of rational iteration procedures
- Geometric analysis of nondeterminacy in dynamical systems
- Algorithms with mediant convergents and their metrical theory
- Solving the quintic by iteration
- On invariant volumes of codimension-one Anosov flows and the Verjovsky conjecture
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)
