On the maximum computing time of the bisection method for real root isolation

详细信息    查看全文

• 作者：George E. Collins ^{gcollins8@charter.net" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Polynomial roots ; Real roots ; Root isolation ; Computing time ; Algorithm analysis ; Dominance
• 刊名：Journal of Symbolic Computation
• 出版年：2017
• 出版时间：March-April 2017
• 年：2017
• 卷：79
• 期：part_P2
• 页码：444-456
• 全文大小：359 K

文摘

The bisection method for polynomial real root isolation was introduced by Collins and Akritas in 1976. In 1981 Mignotte introduced the polynomials A_a,n(x)=xⁿ−2(ax−1)²$A_{a,n}(x)=x^n-2{(ax-1)}^2$, a   an integer, 11b475d" title="Click to view the MathML source">a≥2$a\ge 2$ and n≥3$n\ge 3$. First we prove that if a   is odd then the computing time of the bisection method when applied to A_a,n$A_{a,n}$ dominates $n^5{(\log d)}^2$ where d   is the maximum norm of A_a,n$A_{a,n}$. Then we prove that if A is any polynomial of degree n with maximum norm d   then the computing time of the bisection method, with a minor improvement regarding homothetic transformations, is dominated by $n^5{(\log d)}^2$. It follows that the maximum computing time of the bisection method is codominant with $n^5{(\log d)}^2$.