Any iteration for polynomial equations using linear information has infinite complexity

G. W. Wasilkowski

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


This is the third paper in which we study iterations using linear information for the solution of nonlinear equations. In Wasilkowski [1] and [2] 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 φ{symbol} and any integer k, there exists a complex polynomial f{hook} with all simple zeros such that the first k approximations produced by φ{symbol} do not approximate any solution of f{hook}=0 better than a starting approximation x0. This holds even if the distance between x0 and the nearest solution of f{hook}=0 is arbitrarily small.

Original languageEnglish
Pages (from-to)195-208
Number of pages14
JournalTheoretical Computer Science
Issue number1-2
StatePublished - 1983

Bibliographical note

Funding Information:
L‘~I\ rcsct;lrch ua\supporred in part Science Foundation under Grant MCS75-222-55 ,md the 0fL~ of Natal RIbsearch under Contract NO0014-764.1~0370, NRO44-422. ** On leave from the University of Warsaw, Present address: Department of Computer Science, C‘olumb a Liniversib, New I’ork. NY l&)27, IJ.S.A.

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Any iteration for polynomial equations using linear information has infinite complexity'. Together they form a unique fingerprint.

Cite this