文档介绍：多项式求根的 Hybrid 裁剪算法研究
论文作者签名:
指导教师签名:
论文评阅人 1:
评阅人 2:
评阅人 3:
评阅人 4:
评阅人 5:
答辩委员会主席:
委员 1:
委员 2:
委员 3:
委员 4:
委员 5:
答辩日期:
Study on Hybrid clipping method for solving polynomial
roots
Author’s signature:
Supervisor’s signature:
Thesis reviewer 1:
Thesis reviewer 2:
Thesis reviewer 3:
Thesis reviewer 4:
Thesis reviewer 5:
Chair:
(Committee of oral defence)
Committeeman 1:
Committeeman 2:
Committeeman 3:
Committeeman 4:
Committeeman 5:
Date of oral defence:
浙江大学研究生学位论文独创性声明
本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的
研究成果。除了文中特别加以标注和致谢的地方外,论文中不包含其他人已经发
表或撰写过的研究成果,也不包含为获得浙江大学或其他教育机构的学位或
证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文
中作了明确的说明并表示谢意。
学位论文作者签名: 签字日期: 年月日
学位论文版权使用授权书
本学位论文作者完全了解浙江大学有权保留并向国家有关部门或机构
送交本论文的复印件和磁盘,允许论文被查阅和借阅。本人授权浙江大学可
以将学位论文的全部或部分内容编入有关数据库进行检索和传播,可以采用影印、
缩印或扫描等复制手段保存、汇编学位论文。
(保密的学位论文在解密后适用本授权书)
学位论文作者签名: 导师签名:
签字日期: 年月日签字日期: 年月日
浙江大学硕士学位论文 Abstract
摘要
随着计算机技术的飞速发展,计算机图形学、图像处理方面需要存储和计算
的数据量越来越大,高效、快速、简便的数据处理算法也越来越被需求。
针对目前这种问题,本文提出了用于多项式求根的三次 Hybrid 裁剪方法,这
是一种算法简单、易于编程实现,在计算重根时快速、高效的新方法。该方法将
任意一条 n 阶(n>3)Bézier 曲线等效于一条三次 Hybrid 曲线;该 Hybrid 曲线有一
个移动控制顶点,而其余控制顶点固定;通过比较求出离坐标轴最近和最远的移
动控制顶点,和其余固定控制顶点一起可以得到两条三次 Bézier 曲线;这两条
Bézier 曲线完全包围住原曲线,通过这两条曲线可以求出一个包含所求根的区间;
将原曲线离散化仅保留所求得的区间内的部分,发重复上述过程,反复进行迭代
计算,直到得到的区间长度小于给定允许误差值。针对 Hybrid 裁剪方法,本文继
续推广出四次 Hybrid 裁剪方法。本文通过数值试验证明了提出的三次 Hybrid 裁
剪方法和四次 Hybrid 裁剪方法用于多项式求根时都能得出正确的结果。
本文将已有的二次 Hybrid 裁剪方法和本文提出的三次 Hybrid 裁剪方法作数
值试验对比。可以看出在计算多项式重根时,三次 Hybrid 裁剪方法明显要好于二
次 Hybrid 裁剪方法。本文并将 Hybrid 裁剪方法同多项式裁剪方法做了详细的数
值试验比较,虽然试验结果显示 Hybrid 裁剪方法并不占优势,但是在算法逻辑、
编程实现的简便性和占用存储空间等方面 Hybrid 裁剪方法明显都要好于多项式
裁剪方法。
关键词: Hybrid 裁剪多项式裁剪多项式求根 Bézier 曲线 Hybrid 曲线
iv
浙江大学硕士学位论文 Abstract
Abstract
With the rapid development puter technology, the storage capacity and
amount of data calculation needed puter graphics and image proc