Mathematics – Dynamical Systems
Scientific paper
2011-08-29
Mathematics
Dynamical Systems
20 pages, 2 figures
Scientific paper
We investigate Newton's method for complex polynomials of arbitrary degree $d$, normalized so that all their roots are in the unit disk. We specify an explicit universal set of starting points, consisting of $O(d\log^2d)$ points and depending only on $d$, so that among them there are $d$ points that converge very quickly to the $d$ roots: we prove that the expected total number of Newton iterations required to find all $d$ roots with precision $\eps$ is $O(d^3\log^3d+d\log|\log\eps|)$, which can be further improved to $O(d^2\log^4d+d\log|\log\eps|)$; in the worst case possibly with near-multiple roots, the complexity is $O(d^3\log^2d(d+|\log\eps|))$. The arithmetic complexity for all these Newton iterations is the same as the number of Newton iterations, up to a factor of $\log d$.
No associations
LandOfFree
On the Efficient Global Dynamics of Newton's Method for Complex Polynomials does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On the Efficient Global Dynamics of Newton's Method for Complex Polynomials, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Efficient Global Dynamics of Newton's Method for Complex Polynomials will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-728637