دانلود رایگان مقاله روش برش مکعب گویا برای محاسبه ریشه های حقیقی یک چند جمله ای

Abstract

Many problems in computer aided geometric design and computer graphics can be turned into a root-finding problem of a polynomial equation. Among various solutions, clipping methods based on the Bernstein–Bézier form usually have good numerical stability. A traditional clipping method using polynomials of degree r can achieve a convergence rate of r+1 for a single root. It utilizes two polynomials of degree r to bound the given polynomial f(t) of degree n , where r=2,3, and the roots of the bounding polynomials are used for clipping off the subintervals containing no roots of f(t). This paper presents a rational cubic clipping method for finding the roots of a polynomial f(t) within an interval. The bounding rational cubics can achieve an approximation order of 7 and the corresponding convergence rate for finding a single root is also 7. In addition, differently from the traditional cubic clipping method solving the two bounding polynomials in O(n2), the new method directly constructs the two rational cubics in O(n) which can be used for bounding f(t) in many cases. Some examples are provided to show the efficiency, the approximation effect and the convergence rate of the new method.

5. Conclusions

This paper presents a rational cubic clipping method (denoted as Mr) for finding the roots of a polynomial f (t) within an interval, which can achieve a convergence rate of 7 for a single root by using rational cubic polynomials. Different from previous clipping methods in Bartonˇ and Jüttler (2007), Liu et al. (2009) for computing two bounding polynomials in O(n2) time, Mr directly constructs two rational cubic polynomials, which can be used to bound f (t) in many cases and leads to a computational complexity of O(n). Numerical examples also show that Mr can achieve a much higher convergence rate, much better approximation effect and much higher computation efficiency than previous clipping methods in Bartonˇ and Jüttler (2007), Liu et al. (2009). As for future work, it should also be feasible to achieve a higher computation efficiency by using two bounding B-spline curves, or to achieve a higher convergence rate by combining with reparameterization techniques. Another possible future work is to extend Mr from the curve case to surface cases, which can be used for the root-finding problem of an equation system consisting of two bivariate polynomials.