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 n id="bbr0020">1976n>. In n id="bbr0090">1981n> Mignotte introduced the polynomials n id="mmlsi1" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S074771711600033X&_mathId=si1.gif&_user=111111111&_pii=S074771711600033X&_rdoc=1&_issn=07477171&md5=96f96cf24a97bf95b34fb6bf353ec878" title="Click to view the MathML source">A_a,n(x)=xⁿ&minus;2(ax&minus;1)²n>n class="mathContainer hidden">n class="mathCode">n>n>n>, a   an integer, n id="mmlsi2" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S074771711600033X&_mathId=si2.gif&_user=111111111&_pii=S074771711600033X&_rdoc=1&_issn=07477171&md5=6458292c70dff58fc0b60b4f911b475d" title="Click to view the MathML source">a≥2n>n class="mathContainer hidden">n class="mathCode">n>n>n> and n id="mmlsi3" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S074771711600033X&_mathId=si3.gif&_user=111111111&_pii=S074771711600033X&_rdoc=1&_issn=07477171&md5=244321b719d2355609e6a8c5d4574604" title="Click to view the MathML source">n≥3n>n class="mathContainer hidden">n class="mathCode">n>n>n>. First we prove that if a   is odd then the computing time of the bisection method when applied to n id="mmlsi12" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S074771711600033X&_mathId=si12.gif&_user=111111111&_pii=S074771711600033X&_rdoc=1&_issn=07477171&md5=2aeadb845361eeb0481963c8e4a1fc56" title="Click to view the MathML source">A_a,nn>n class="mathContainer hidden">n class="mathCode">$A_{a,\mathrm{<font\; color="red">n</font>}}$n>n>n> dominates n id="mmlsi11" class="mathmlsrc">nce?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S074771711600033X&_mathId=si11.gif&_user=111111111&_pii=S074771711600033X&_rdoc=1&_issn=07477171&md5=592b2422ae0a5cff8e366abab9709e79">nlineImage" height="16" width="62" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S074771711600033X-si11.gif"><noscript>n:bottom" width="62" alt="View the MathML source" title="View the MathML source" src="http://origin-ars.els-cdn.com/content/image/1-s2.0-S074771711600033X-si11.gif">noscript>n class="mathContainer hidden">n class="mathCode">n>n>n> where d   is the maximum norm of n id="mmlsi12" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S074771711600033X&_mathId=si12.gif&_user=111111111&_pii=S074771711600033X&_rdoc=1&_issn=07477171&md5=2aeadb845361eeb0481963c8e4a1fc56" title="Click to view the MathML source">A_a,nn>n class="mathContainer hidden">n class="mathCode">$A_{a,\mathrm{<font\; color="red">n</font>}}$n>n>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 id="mmlsi11" class="mathmlsrc">nce?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S074771711600033X&_mathId=si11.gif&_user=111111111&_pii=S074771711600033X&_rdoc=1&_issn=07477171&md5=592b2422ae0a5cff8e366abab9709e79">nlineImage" height="16" width="62" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S074771711600033X-si11.gif"><noscript>n:bottom" width="62" alt="View the MathML source" title="View the MathML source" src="http://origin-ars.els-cdn.com/content/image/1-s2.0-S074771711600033X-si11.gif">noscript>n class="mathContainer hidden">n class="mathCode">n>n>n>. It follows that the maximum computing time of the bisection method is codominant with n id="mmlsi11" class="mathmlsrc">nce?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S074771711600033X&_mathId=si11.gif&_user=111111111&_pii=S074771711600033X&_rdoc=1&_issn=07477171&md5=592b2422ae0a5cff8e366abab9709e79">nlineImage" height="16" width="62" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S074771711600033X-si11.gif"><noscript>n:bottom" width="62" alt="View the MathML source" title="View the MathML source" src="http://origin-ars.els-cdn.com/content/image/1-s2.0-S074771711600033X-si11.gif">noscript>n class="mathContainer hidden">n class="mathCode">n>n>n>.