 Rational cubic clipping with linear complexity for computing roots of polynomialsXiao-diao Chen and Weiyin Ma Applied Mathematics and Computation, 2016, vol. 273, issue C, 1051-1058 Abstract: Many problems in computer aided geometric design and computer graphics can be turned into a root-finding problem of polynomial equations. Among various clipping methods, the ones based on the Bernstein–Bézier form have good numerical stability. One of such clipping methods is the k-clipping method, where k=2,3 and often called a cubic clipping method when k=3. It utilizes O(n2) time to find two polynomials of degree k bounding the given polynomial f(t) of degree n, and achieves a convergence rate of k+1 for a single root. The roots of the bounding polynomials of degree k are then used for bounding the roots of f(t). This paper presents a rational cubic clipping method for finding two bounding cubics within O(n) time, which can achieve a higher convergence rate 5 than that of 4 of the previous cubic clipping method. When the bounding cubics are obtained, the remaining operations are the same as those of previous cubic clipping method. Numerical examples show the efficiency and the convergence rate of the new method. Keywords: Approximation order; Fast cubic clipping method; Root-finding; Convergence rate; Linear computational complexity (search for similar items in EconPapers) Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:273:y:2016:i:c:p:1051-1058 DOI: 10.1016/j.amc.2015.10.054 Access Statistics for this article Applied Mathematics and Computation is currently edited by Theodore Simos More articles in Applied Mathematics and Computation from Elsevier |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.