计算机科学 ›› 2018, Vol. 45 ›› Issue (3): 63-66.doi: 10.11896/j.issn.1002-137X.2018.03.010
金佳培,陈小雕,史甲尔,陈立庚
JIN Jia-pei, CHEN Xiao-diao, SHI Jia-er and CHEN Li-geng
摘要： 非线性方程的求根在计算机辅助几何设计、计算机图形学、信号处理、机器人等方面有着较为广泛的应用。文中提出基于重新参数化的三次裁剪求根算法,该算法可以用于非多项式方程的求根。首先,求解出插值四点的三次多项式；然后,寻找重新参数化函数,使得复合的插值多项式也插值对应的导数,从而提升对应的逼近阶和收敛阶。与已有的三次裁剪方法相比,所提方法能达到9次或更高的收敛阶。在区间内单根且有理三次裁剪方法需要计算包围多项式的某些情形下,所提方法可以包住对应的根。实例表明,在某些Newton方法失效的情形下,该方法也可以收敛到相应的实根。
| [1] 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. [2] ELBER G,KIM M S.Geometric constraint solver using multivariate rational spline functions[C]∥ACM Symposium on Solid Modeling and Applications.DBLP,2001:1-10. [3] FAROUKI R T,GOODMAN T.On the optimal stability of the Bernstein basis[J].Mathematics of Computation,1996,65(216):1553-1566. [4] BARTO Nˇ M,JTTLER B.Computing roots of polynomials by quadratic clipping[J].Computer Aided Geometric Design,2007,24(3):125-141. [5] 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. [6] CHEN X D,MA W.A planar quadratic clipping method forcomputing a root of a polynomial in an interval[J].Computers &Graphics,2015,46(C):89-98. [7] 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. [8] CHEN X D,MA W.Rational cubic clipping with linear complexi-ty for computing roots of polynomials[J].Applied Mathematics &Computation,2016,273:1051-1058. [9] EFREMOV A,HAVRAN V,SEIDEL H P.Robust and numerically stable Bézier clipping method for ray tracing NURBS surfaces[C]∥Spring Conference on Computer Graphics.2005:127-135. [10] JTTLER B.The dual basis functions for the Bernstein polynomials[J].Advances in Computational Mathematics,1998,8(4):345-352. [11] MRKEN K,REIMERS M.An unconditionally convergentmethod for computing zeros of splines and polynomials[J].Mathematics of Computation,2007,76(258):845-865. [12] 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 and Computer Graphics,2011,23(2):193-207.(in Chinese) 卫飞飞,周飞,冯结青.CAGD/CG领域中一元多项式方程求根问题综述[J].计算机辅助设计与图形学学报,2011,23(2):193-207. [13] DAVIS P J.Interpolation and approximation[J].Unt Theses & Dissertations,2001,3(1):59-67. [14] LI X,MU C,MA J,et al.Sixteenth-order method for nonlinear equations[J].Applied Mathematics & Computation,2010,215(10):3754-3758. [15] SHARMA J R,ARORA H.A new family of optimal eighth order methods with dynamics for nonlinear equations[J].Applied Mathematics & Computation,2016,273:924-933. |
| No related articles found! |
|
||
首页