上海交通大学学报

上海交通大学学报（自然版）

• 自动化技术、计算机技术 •    下一篇

一种改进的多项式实根隔离算法

刘栋1，冯勇1，张彩环2，赵向辉1
  

  1. (1.中国科学院 成都计算机应用研究所， 成都 610041； 2.洛阳师范学院 数学科学学院， 河南 洛阳 471022)
  • 收稿日期:2010-01-18 修回日期:1900-01-01 出版日期:2010-11-30 发布日期:2010-11-30

An Improved Algorithm for Real Root Isolation of Univariate Polynomials

LIU Dong1，FENG Yong1，ZHANG Caihuan2，ZHAO Xianghui1   

  1. (1.Chengdu Institute of Computer Applications, Chinese Academy of Sciences, Chengdu 610041, China；
    2.Department of Mathematics, Luoyang Normal University, Luoyang 471022, Henan，China)
  • Received:2010-01-18 Revised:1900-01-01 Online:2010-11-30 Published:2010-11-30

摘要： 基于Maple软件包Discoverer中Trealroot算法，提出了一个整系数一元多项式实根隔离的改进算法.采用以Descartes法则和一个特殊的高效区间牛顿算法为根数法则的二分法，彻底抛弃了泰勒平移，避免了泰勒平移在高次稀疏情况下对性能的拖累；同时避免使用Trealroot中2个经验值.改进算法对于高次稀疏多项式特别有效，而且越是稀疏，算法的效率越高.对大量随机多项式进行测试，并与Trealroot和realroot(Maple中的实根隔离程序)进行比较.实验数据表明，该算法对高次稀疏多项式的实根隔离有很高的效率.

关键词: 实根隔离, 一元多项式, 区间运算, 区间牛顿算法, 二分法

Abstract: An improved algorithm for real root isolation of univariate polynomials was proposed mainly based on bisection method and a kind of specially designed efficient interval Newton operator. Its structure is similar to Trealroot, a function in Maple package Discoverer, however, it is more efficient than Trealroot for sparse polynomials with large degrees and few terms. Generally speaking, performing Taylor shift is very costly, so Trealroot uses many techniques to decrease the number of Taylor shifts. Different from Trealroot, the proposed algorithm performs a specially designed efficient exact interval Newton operator to rule out intervals not containing real zeros quickly and avoids completely Taylor shifts. The algorithm is super efficient for sparse polynomials. The polynomial is sparser, and the algorithm is more efficient. A large number of polynomials generated randomly by Maple were tested, compared with Trealroot and realroot (a function in Maple), and the result was reported.

中图分类号: