Computer Science ›› 2018, Vol. 45 ›› Issue (3): 63-66.doi: 10.11896/j.issn.1002-137X.2018.03.010

Previous Articles     Next Articles

Reparameterization-based Clipping Method for Root-finding Problem of Non-linear Equations

JIN Jia-pei, CHEN Xiao-diao, SHI Jia-er and CHEN Li-geng   

  • Online:2018-03-15 Published:2018-11-13

Abstract: The root-finding problem of non-linear equations has wide applications in computer aided geometric design,computer graphics,robotics,etc.This paper presented a reparameterization-based cubic clipping method for finding the roots of a non-linear equation. Firstly,it computes a cubic polynomial interpolating the given smooth function f(t) at four points.Then,it searches two reparameterization functions so that the reparameterized functions have the same derivatives,which leads to higher approximation order and convergence rate.Compared with the prevailing cubic clipping methods,the new method can achieve the convergence rate 9 or higher for single root cases,and directly bound the root without computing the bounding polynomials.Numerical examples show that it can converge to the proper solution even in some cases that Newton’s methods fail.

Key words: Root-finding of non-linear equations,Reparameterization,Cubic clipping,Convergence rate

[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,JTTLER 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] JTTLER B.The dual basis functions for the Bernstein polynomials[J].Advances in Computational Mathematics,1998,8(4):345-352.
[11] MRKEN 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!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!