Mathematics – Dynamical Systems
Scientific paper
2012-02-11
Mathematics
Dynamical Systems
11 pages, 1 figure
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. For each degree $d$, we give an explicit set $\mathcal{S}_d$ of $3.33d\log^2 d(1 + o(1))$ points with the following universal property: for every normalized polynomial of degree $d$ there are $d$ starting points in $\mathcal{S}_d$ whose Newton iterations find all the roots. If the roots are uniformly and independently distributed, we show that the number of iterations for these $d$ starting points to reach all roots with precision $\varepsilon$ is $O(d^2\log^4 d + d\log|\log \varepsilon|)$ (with probability $p_d$ tending to 1 as $d\to\infty$). This is an improvement of an earlier result in \cite{D}, where the number of iterations is shown to be $O(d^4\log^2 d + d^3\log^2d|\log \varepsilon|)$ in the worst case (allowing multiple roots) and $O(d^3\log^2 d(\log d + \log \delta) + d\log|\log \varepsilon|)$ for well-separated (so-called $\delta$-separated) roots. Our result is almost optimal for this kind of starting points in the sense that the number of iterations can never be smaller than $O(d^2)$ for fixed $\eps$.
Aspenberg Magnus
Bilarev Todor
Schleicher Dierk
No associations
LandOfFree
On the speed of convergence 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 speed of convergence 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 speed of convergence of Newton's method for complex polynomials will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-371368