祝平，陈小雕，*，马维银，姜霓裳

（1.杭州电子科技大学计算机学院，浙江杭州 310018； 2.香港城市大学 机械工程学系，中国香港； 3.杭州电子科技大学理学院，浙江杭州 310018）

0 引 言

求根在计算机辅助几何设计［1］、计算机图形学［2-3］、机器人技术［4］及地磁导航中具有广泛应用。理论上，利用结式等消元方法，可将多项式方程组转化为一元多项式方程。本文只讨论单变量方程的求根问题，线性方程组的其他求解方法可参见文献［1，5-6］等。

计算稳定性与计算效率是求根的2 个关键问题。效率因子（efficiency index，EI）常用于衡量算法的计算效率。设某算法的收敛阶为p，需进行n次函数计算（functional evaluation，FE），则对应的EI 定义为p1/n。文献［7］猜想：任何需要n次FE 的求根方法对应的收敛阶都不会超过最优次数2n-1。

下文着重介绍求解光滑函数实根的3 种方法。

（1） 类牛顿法，包走 Newton，Halley 和Ostrowski 法［8-10］。从初始值开始，获得近似于根的点序列，通常用第k个点的信息计算第(k+1)个点，计算性能取决于初始值的选取，当初始值选取错误时，易发散。文献［9-10］以收敛阶8 得到了最佳效率指数，但不易扩展至更高收敛阶［11］。理论上相应的区间方法可提高计算稳定性，但将耗费更多的计算时间［12-13］。基于笛卡尔法则与Sturm 定理的多项式求根方法虽具有较好的计算稳定性，但收敛速度较低。

（2）基于Bernstein-Bézier 形式的裁剪法［1，14-17］。利用Bernstein-Bézier 形式具有的系数扰动稳定性特点，通过不断裁剪不包含实根的小区间，获取较好的计算稳定性［18］，收敛速度通常优于Sturm方法［19］。

（3）渐进法［20-21］。从包含根的初始区间开始，利用前k个点（而非仅第k个点）的信息渐进式计算第(k+1)个点。……