How to be sure of finding a root of a complex polynomial using Newton's method (Q5285715)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 222764
Language Label Description Also known as
default for all languages
No label defined
    English
    How to be sure of finding a root of a complex polynomial using Newton's method
    scientific article; zbMATH DE number 222764

      Statements

      How to be sure of finding a root of a complex polynomial using Newton's method (English)
      0 references
      0 references
      29 June 1993
      0 references
      root of a complex polynomial
      0 references
      Newton's method
      0 references
      Julia set
      0 references
      For a complex polynomial \(p\) the rational map \(N(z)=z-p(z)/p'(z)\) on the Riemann sphere is considered. The main result is presented as an algorithm: ``There is a constant \(c<800\) with the following property. Let \(p\) be any complex polynomial \(p(z)=z^ d+a_{d-2} z^{d-2}+\cdots+ a_ 1 z+a_ 0\) with \(d\geq 10\) for which each \(| a_ i|\leq 1\) and let \(\varepsilon>0\). Put \(R=(19.2d \log d+2)\pi\), \(\omega=\exp(2\pi i/R)\) and \(\rho=1-2\pi/R\). Define an array \(A\) of points \(\{\rho^ j d\omega^ k: 0\leq j<-(R/2\pi)\log(1-d^{-1}-2d^{-2})+1,\;0\leq k<R\}\) and consider the following algorithm. For each \((j,k)\) in turn evaluate successively \(w=N^ \ell(\rho^ i d\omega^ k)\) for \(1\leq \ell\leq [d \log(d^ 3/\varepsilon)]\). If at any stage \(| w|>d\) go to the next value of \((j,k)\). If \(| w- N(w)|<\varepsilon/d\) stop. Then this algorithm does stop and, when it stops, \(w\) is within \(\varepsilon\) of some root of \(p\). The number of times \(N\) has been evaluated is at most \(cd^ 2(\log d)^ 2\log(d^ 3/\varepsilon)\)''.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references