Any Iteration for Polynomial Equations Using Linear Information has Infinite Complexity.
Abstract
This is the third paper in which we study iterations using linear information for the solution of nonlinear equations. We have considered the existence of globally convergent iterations for the class of analytic functions. Here we study the complexity of such iterations. We prove that even for the class of scalar complex polynomials with simple zeros, any iteration using arbitrary linear information has infinite complexity. More precisely, we show that for any iteration and any integer k, there exists a complex polynomial f with all simple zeros such that the first k approximations produced by the iteration do not approximate any solution of f = 0 better than a starting approximation x sub 0. This holds even if the distance between x sub 0 and the nearest solution of f = 0 is arbitrarily small.
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 01, 1979
- Accession Number
- ADA081437
Entities
People
- G. W. Wasilkowski
Organizations
- Carnegie Mellon University