Please wait a minute...
浙江大学学报（理学版）
浙江大学学报（理学版）  2021, Vol. 48 Issue (2): 143-150    DOI: 10.3785/j.issn.1008-9497.2021.02.002
图形计算     
光滑函数实根计算的渐进显式公式
祝平1, 陈小雕1,2, 马维银2, 姜霓裳3
1.杭州电子科技大学 计算机学院，浙江 杭州 310018
2.香港城市大学 机械工程学系，中国 香港
3.杭州电子科技大学 理学院，浙江 杭州 310018
Explicit formulae for progressively computing a real root of the smooth function
ZHU Ping1, CHEN Xiaodiao1,2, MA Weiyin2, JIANG Nichang3
1.School of Computer, Hangzhou Dianzi University,Hangzhou 310018, China
2.Department of Mechanical Engineering, City University of Hong Kong,Hong Kong,China
3.School of Science, Hangzhou Dianzi University, Hangzhou 310018, China
 全文: PDF(946 KB)   HTML  
摘要： 求根问题在计算机图形学、机器人技术、地磁导航等领域应用广泛。基于重新参数化方法（reparamaterization-based method，RBM），给出了用于计算给定光滑函数在某区间内唯一实根的渐进式显式公式。给定光滑函数f（t），用有理多项式Ai（s）对曲线C（t）=（t，f（t））进行插值，得到重新参数化函数t =?i（s），使得Ai（sj）=C（?i（sj））。提出了基于重新参数化函数?i（s）的显式公式用于渐进式逼近f（t）对应的实根，在n个函数计算的成本下，收敛阶可达到3·2n-2，其中n≥3。与类牛顿法相比，本文方法提高了计算稳定性，且收敛速度更快、计算效率更高。与裁剪法相比，本文方法不需要求解包围多项式，且可用于非多项式函数计算，计算效率更高。数值实例表明，每增加一个插值点，逼近阶可提高一倍，且可获得较传统裁剪法更高的计算效率。
关键词： 裁剪方法;  求根计算;  数值迭代法;  收敛阶;  重新参数化    
Abstract: The issue of finding the roots of equations has wide applications in computer graphics, robotics, and geomagnetic navigation. Based on the reparameterization technique, this paper presents an explicit formula for computing the real root of a smooth function within a certain interval. Given a smooth function f (t), by using the rational polynomial Ai(s) to interpolate the curve C(t)=(t,f (t)), it deduces a reparameterization function t =?i(s) such that Ai(sj)= C(?i(sj)). This paper proposes an explicit formula based on the reparameterized function ?i(s) to progressively approximate the root of f (t), which can achieve the convergence order of 3·2n-2 at the cost of n functions, where n≥3. Compared with the Newton-like method, it improves the computational stability, and can achieve faster convergence rate and better efficiency. Compared with the clipping methods, it does not need to solve the bounding polynomial, and is applicable for solving non-polynomial functions. Numerical examples show that each time one more interpolation point is added, the approximation order will be doubled, hence much better computational efficiency than traditional clipping methods.
Key words: convergence order    clipping method    reparameterization    root-?nding    numerical iterative method
收稿日期: 2020-09-30 出版日期: 2021-03-18
CLC:  TP  
基金资助: 国家自然科学基金资助项目(61972120).
通讯作者: ORCID:http://orcid.org/0000-0002-7523-7657，E-mail:xiaodiao@hdu.edu.cn.     E-mail: xiaodiao@hdu.edu.cn
作者简介: 祝平(1998—)，ORCID:http://orcid.org/0000-0001-6338-5110，男，主要从事计算机辅助几何设计研；
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　
祝平
陈小雕
马维银
姜霓裳

引用本文:

祝平, 陈小雕, 马维银, 姜霓裳. 光滑函数实根计算的渐进显式公式[J]. 浙江大学学报（理学版）, 2021, 48(2): 143-150.

ZHU Ping, CHEN Xiaodiao, MA Weiyin, JIANG Nichang. Explicit formulae for progressively computing a real root of the smooth function. Journal of Zhejiang University (Science Edition), 2021, 48(2): 143-150.

链接本文:

https://www.zjujournals.com/sci/CN/10.3785/j.issn.1008-9497.2021.02.002    或    https://www.zjujournals.com/sci/CN/Y2021/V48/I2/143

1 LIU L，ZHANG L，LIN B，et al.Fast approach for computing roots of polynomials using cubic clipping［J］.Computer Aided Geometric Design，2009，26（5）：547-559. DOI：10.1016/j.cagd.2009.02.003
2 AIZENSHTEIN M，BARTOŇ M，ELBER G. Global solutions of well-constrained transcendental systems using expression trees and a single solution test［J］. Computer Aided Geometric Design，2012，29（5）：265-279. DOI：10.1016/j.cagd.2011.07.002
3 BARTOŇ M，ELBER G，HANNIEL I.Topologically guaranteed univariate solutions of underconstrained polynomial systems via no-loop and single-component tests［J］.Computer-Aided Design，2011，43（8）：1035-1044. DOI：10.1016/j.cad.2011.03.009
4 CHOI Y K，WANG W，LIU Y，et al.Continuous collision detection for two moving elliptic disks［J］.IEEE Transactions on Robotics，2006，22（2）：213-224. DOI：10.1109/TRO.2005.862479
5 ELBER G，KIM M.Geometric constraint solver using multivariate rational spline functions［C］//ACM Symposium on Solid Modeling and Applications.Ann Arbor：ACM，2001：1-10. DOI：10.1145/376957.376958
6 卫飞飞，周飞，冯结青. CAGD/CG领域中一元多项式方程求根问题综述［J］.计算机辅助设计与图形学学报，2011（2）：193-207. DOI：10.1631/jzus.C0910717 WEI F F，ZHOU F，FENG J Q. Survey of real root finding of univariate polynomial equation in CAGD/CG［J］.Journal of Computer-Aided Design & Computer Graphics，2011，23（2）：193-207. DOI：10.1631/jzus.C0910717
7 KUNG H T，TRAUB J F.Optimal order of one-point and multipoint iteration［J］.Journal of the ACM，1974，21（4）：643-651. DOI：10.1145/321850. 321860
8 CORDERO A，TORREGROSA J R，VASSILEVA M P，et al. A family of modified Ostrowski’s methods with optimal eighth order of convergence［J］.Applied Mathematics Letters，2011，24（12）：2082-2086. DOI：10.1016/j.aml.2011.06.002
9 SHARMA J R，ARORA H.An efficient family of weighted-Newton methods with optimal eighth order convergence［J］. Applied Mathematics Letters，2014，29：1-6. DOI：10.1016/j.aml.2013.10.002
10 SHARMA J R，ARORA H.A new family of optimal eighth order methods with dynamics for nonlinear equations［J］. Applied Mathematics and Computation，2016，273：924-933. DOI：10.1016/j.amc.2015.10.049
11 LI X，MU C，MA J，et al.Sixteenth-order method for nonlinear equations［J］.Applied Mathematics and Computation，2010，215（10）：3754-3758. DOI：10.1016/j.amc.2009.11.016
12 MOORE R E. Methods and Applications of Interval Analysis［M］. Philadelphia：DBLP，1979.
13 MOORE R E，KEARFOTT R B，CLOUD M J.Introduction to Interval Analysis［M］.Cambridge： Cambridge University Press，2009.
14 BARTOŇ M，JÜTTLER B.Computing roots of polynomials by quadratic clipping［J］.Computer Aided Geometric Design，2007，24（3）：125-141. DOI：10.1016/j.cagd.2007.01.003
15 CHEN X D，MA W，YE Y.A rational cubic clipping method for computing real roots of a polynomial［J］.Computer Aided Geometric Design，2015，38：40-50. DOI：10.1016/j.cagd.2015.08.002
16 CHEN X D，MA W.Rational cubic clipping with linear complexity for computing roots of polynomials［J］.Applied Mathematics and Computation，2016，273：1051-1058. DOI：10.1016/j.amc.2015.10.054
17 SEDERBERG T W，NISHITA T. Curve intersection using Bézier clipping［J］.Computer-Aided Design，1990，22（9）：538-549. DOI：10.1016/0010-4485（90）90039-f
18 JUTTLER B.The dual basis functions for the Bernstein polynomials［J］.Advances in Computational Mathematics，1998，8（4）：345-352. 10.1023/A:1018912801267
19 FAROUKI R T，GOODMAN T N.On the optimal stability of the Bernstein basis［J］.Mathematics of Computation，1996，65（216）：1553-1566. DOI：10.1090/s0025-5718-96-00759-4
20 CHEN X D，ZHANG Y，SHI J，et al.An efficient method based on progressive interpolation for solving non-linear equations［J］.Applied Mathematics Letters，2016，61（11）：67-72. DOI：10.1016/j.aml.2016.05.007
21 CHEN X D，SHI J，MA W. A fast and robust method for computing real roots of nonlinear equations［J］.Applied Mathematics Letters，2017，68：27-32. DOI：10.1016/j.aml.2016.12.013
22 MORKEN K，REIMERS M.An unconditionally convergent method for computing zeros of splines and polynomials［J］. Mathematics of Computation，2007，76（258）：845-865.
23 GARCIAZAPATA J L，MARTIN J C D，FACILA A C.An adaptive subdivision method for root finding of univariate polynomials［J］.Journal of Computational and Applied Mathematics，2019，325：146-164. 10.1016/j.cam.2018.11.023
24 DAVIS P J.Interpolation and Approximation［M］.NewYork：Dover，1975. DOI：10.1137/1007028
[1] 孙方裕. 一个并行计算多项式全部零点的圆盘迭代法[J]. 浙江大学学报（理学版）, 2000, 27(4): 355-360.