《计算机应用》唯一官方网站 ›› 2022, Vol. 42 ›› Issue (5): 1531-1537.DOI: 10.11772/j.issn.1001-9081.2021030440

• 先进计算 • 上一篇    下一篇

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

葛昕钰1,2(), 陈世平3, 刘忠1,4   

  1. 1.中国科学院 成都计算机应用研究所,成都 610041
    2.中国科学院大学,北京 100049
    3.四川省贸易学校 财经商贸系,四川 雅安 625107
    4.乐山职业技术学院 电子信息工程系,四川 乐山 614000
  • 收稿日期:2021-03-22 修回日期:2021-07-14 接受日期:2021-07-14 发布日期:2022-06-11 出版日期:2022-05-10
  • 通讯作者: 葛昕钰
  • 作者简介:葛昕钰(1995—),女,河南安阳人,博士研究生,CCF会员,主要研究方向:自动推理、机器证明 geeexy@163.com
    陈世平(1970—),男,四川遂宁人,高级讲师,博士,主要研究方向:机器证明、符号计算
    刘忠(1968—),男,四川乐山人,教授,博士,主要研究方向:自动推理、机器证明。
  • 基金资助:
    四川省科学技术厅科技计划项目(2016GFW0048)

Real root isolation algorithm for exponential function polynomials

Xinyu GE1,2(), Shiping CHEN3, Zhong LIU1,4   

  1. 1.Chengdu Institute of Computer Application,Chinese Academy of Sciences,Chengdu Sichuan 610041,China
    2.University of Chinese Academy of Sciences,Beijing 100049,China
    3.Department of Finance and Commerce,Sichuan Trade School,Ya’an Sichuan 625107,China
    4.Department of Electronic Information Engineering,Leshan Vocational and Technical College,Leshan Sichuan 614000,China
  • Received:2021-03-22 Revised:2021-07-14 Accepted:2021-07-14 Online:2022-06-11 Published:2022-05-10
  • Contact: Xinyu GE
  • About author:GE Xinyu, born in 1995,Ph. D. candidate. Her research interestsinclude automated reasoning,mechanical proving.
    CHEN Shiping, born in 1970, Ph. D., senior lecturer. Hisresearch interests include mechanical proving,symbolic computation.
    LIU Zhong, born in 1968, Ph. D., professor. His researchinterests include automated reasoning,mechanical proving.
  • Supported by:
    Scientific and Technological Program of Science and Technology Department of Sichuan Province(2016GFW0048)

摘要:

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

关键词: 指数函数多项式, 实根分离, 泰勒替换法, 区间列, 终止性

Abstract:

For addressing real root isolation problem of transcendental function polynomials, an interval isolation algorithm for exponential function polynomials named exRoot was proposed. In the algorithm, the real root isolation problem of non-polynomial real functions was transformed into sign determination problem of polynomial, then was solved. Firstly, the Taylor substitution method was used to construct the polynomial nested interval of the objective function. Then, the problem of finding the root of the exponential function was transformed into the problem of determining the positivity and negativity of the polynomial in the intervals. Finally, a comprehensive algorithm was given and applied to determine the reachability of rational eigenvalue linear system tentatively. The proposed algorithm was implemented in Maple efficiently and easily with readable output results. Different from HSOLVERand numerical calculation method fsolve, exRoot avoids discussing the existence of roots directly, and theoretically has termination and completeness. It can reach any precision and can avoid the systematic error brought by numerical solution when being applied into the optimization problem.

Key words: exponential function polynomial, real root isolation, Taylor substitution method, sequence of intervals, termination

中图分类号: