多项式方程求根的裁剪算法研究

发布时间：2018-06-06 04:06

本文选题：多项式方程求根 + SLEFE裁剪算法　；参考：《合肥工业大学》2016年硕士论文

【摘要】：多项式方程求根是计算机辅助几何设计领域的基本问题之一,在碰撞检测、干涉检查等领域有着非常多的应用。随着计算机科学技术的不断进步,需要处理的数据量和计算量越来越大,对多项式方程求根算法的要求也越来越高。为了能够又快又好地求得多项式方程的根,本文基于SLEFE (Subdividable Linear Efficient Function Enclose)的理论,结合裁剪算法在速度和稳定性上的优势,提出SLEFE分离算法和SLEFE裁剪算法。对于给定的多项式,SLEFE分离算法能够快速有效地将多项式方程所有实根所在的区间分离开来。对于分离所得的每一个子区间,应用SLEFE裁剪算法提高区间的精度,通过不断地迭代,得到满足一定精度的实根所在的区间,最终得到根的近似解。通过与其他算法进行比较,SLEFE裁剪算法用于解决固定区间内只有一个实根的多项式方程求根问题所需的迭代次数与时间较少。本文还从理论方面证明了SLEFE裁剪算法的收敛速率为2。针对多项式曲线保凸的特殊情况,为了提高计算效率,达到更高的精度,本文给出了特殊情况下的SLEFE裁剪算法代替SLEFE裁剪算法,实例显示在多项式曲线保凸的情况下,能达到更好的逼近效果,计算效率更高。最后,通过分析Hybrid曲线与Hybrid裁剪算法,证明了k次Hybrid裁剪算法的收敛速率为k+1。
[Abstract]:Root finding of polynomial equations is one of the basic problems in computer aided geometric design (CAD). It has many applications in collision detection, interference detection and so on. With the development of computer science and technology, the amount of data and computation needed to be processed is increasing, and the requirement of polynomial equation root algorithm is becoming higher and higher. In order to find the root of polynomial equation quickly and well, based on the theory of SLEFE subdividable Linear Efficient Function Enclose) and combining the advantages of clipping algorithm in speed and stability, this paper proposes SLEFE separation algorithm and SLEFE clipping algorithm. For a given polynomial SLEFE separation algorithm, the interval of all real roots of polynomial equation can be separated quickly and effectively. For each subinterval, the SLEFE clipping algorithm is used to improve the accuracy of the interval. By iterating continuously, the interval where the real root is satisfied with a certain accuracy is obtained, and the approximate solution of the root is obtained. Compared with other algorithms, the SLEFE clipping algorithm requires less iterative times and less time to solve the root problem of polynomial equations with only one real root in a fixed interval. The convergence rate of SLEFE clipping algorithm is also proved to be 2. 2. In order to improve the calculation efficiency and achieve higher precision for the special case of preserving convex polynomial curves, this paper presents the SLEFE clipping algorithm instead of the SLEFE clipping algorithm in special cases. The example shows that the polynomial curve preserves convexity in the case of preserving the convexity of polynomial curves. It can achieve better approximation effect and higher computational efficiency. Finally, by analyzing the Hybrid curve and Hybrid clipping algorithm, the convergence rate of k degree Hybrid clipping algorithm is proved to be k 1.
【学位授予单位】：合肥工业大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O151.1;TP391.72

【相似文献】