葛昕钰，陈世平，刘忠

（1.中国科学院 成都计算机应用研究所，成都 610041； 2.中国科学院大学，北京 100049；3.四川省贸易学校 财经商贸系，四川 雅安 625107；4.乐山职业技术学院 电子信息工程系，四川 乐山 614000）（∗通信作者电子邮箱geeexy@163.com）

指数函数多项式的实根分离算法

葛昕钰1，2*，陈世平3，刘忠1，4

（1.中国科学院 成都计算机应用研究所，成都 610041； 2.中国科学院大学，北京 100049；3.四川省贸易学校 财经商贸系，四川 雅安 625107；4.乐山职业技术学院 电子信息工程系，四川 乐山 614000）（∗通信作者电子邮箱geeexy@163.com）

针对超越函数多项式的实根分离问题，提出了一种指数函数多项式的区间分离算法exRoot，将非多项式型实函数的实根分离问题转化为多项式正负性判定问题进而对其求解。首先，利用泰勒替换法构造目标函数的多项式区间套；然后，将指数函数的求根问题转化为多项式在区间内正负性的判定问题；最后，给出综合算法，并且试探性地应用于实特征值线性系统的可达性判定问题。所提算法在Maple中实现，输出的结果可读，且高效易行。区别于HSOLVER和数值计算方法fsolve，exRoot回避了直接讨论根的存在性问题，理论上具有终止性和完备性，且可达到任意精度，应用于最优化问题时可避免数值解带来的系统误差。

指数函数多项式；实根分离；泰勒替换法；区间列；终止性

0 引言

实根分离算法作为实代数的基本算法之一，不仅具有很强的理论意义，还有着广泛的应用前景。除了GCD（Greatest Common Divisor）算法、Sylvester结式、Descartes符号法则等经典工具外，对于多项式型函数实根分离的研究也有进展，例如Becker等［1］提出的Cisolate算法和Mehlhorn等［2］提出的渐进方法。……