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
29 June 1993
0 references
root of a complex polynomial
0 references
Newton's method
0 references
Julia set
0 references
0 references
0.902846097946167
0 references
0.8646947741508484
0 references
0.863819420337677
0 references
0.858299970626831
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