On the distance to a root of complex polynomials under Newton's method
1
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
In this paper, we derive an upper bound for the distance from a point in the immediate basin of a root of a complex polynomial to the root itself. We establish that if $z$ is a point in the immediate basin of a root $\alpha$ of a polynomial $p$ of degree $d\geq 12$, then $|z-\alpha|\leq \frac{3}{\sqrt{d}}\left(6\sqrt{310}/35\right)^d|N_p(z)-z|$, where $N_p$ is the Newton map induced by $p$. This bound leads to a new bound of the expected total number of iterations of Newton's method required to reach all roots of every polynomial $p$ within a given precision, where $p$ is normalized so that its roots are in the unit disk.
Abstract
In this paper, we derive an upper bound for the distance from a point in the immediate basin of a root of a complex polynomial to the root itself. We establish that if $z$ is a point in the immediate basin of a root $\alpha$ of a polynomial $p$ of degree $d\geq 12$, then $|z-\alpha|\leq \frac{3}{\sqrt{d}}\left(6\sqrt{310}/35\right)^d|N_p(z)-z|$, where $N_p$ is the Newton map induced by $p$. This bound leads to a new bound of the expected total number of iterations of Newton's method required to reach all roots of every polynomial $p$ within a given precision, where $p$ is normalized so that its roots are in the unit disk.
참고문헌 (8)
- T. Bilarev, "On the speed of convergence of Newton's method for complex polynomials", Math. Comp, 85(298), pp.693~705 (2016)[DOI]
- S. Chaiya, "On the distance to a root of polynomials", Abstr. Appl. Anal., 2011, pp.6~ (2011)[DOI]
- J. Hubbard, "How to nd all roots of complex polynomials by Newton's method", Invent. Math, 146(1), pp.1~33 (2001)[DOI]
- F. Przytycki, "Dynamical systems and ergodic theory", pp.229~235 (1986), Banach Center Publ
- D. Schleicher, "On the number of iterations of Newton's method for complex polynomials", Ergodic Theory Dynam. Systems, 22(3), pp.935~945 (2002)[DOI]
- D. Schleicher, "On the ecient global dynamics of Newton's method for complex polynomials", arXiv:1108.5773v3, ~ (2016)
- D. Schleicher, "Newton's method in practice : Finding all roots of polynomials of degree one million eciently", Theoret. Comput. Sci, 681, pp.146~166 (2017)[DOI]
- M. Shishikura, "Complex dynamics", pp.257~276 (2009), A K Peters