發(fā)布時間：2018-06-06 04:06

  本文選題：多項式方程求根 + SLEFE裁剪算法��； 參考：《合肥工業(yè)大學(xué)》2016年碩士論文

【摘要】：多項式方程求根是計算機(jī)輔助幾何設(shè)計領(lǐng)域的基本問題之一,在碰撞檢測、干涉檢查等領(lǐng)域有著非常多的應(yīng)用。隨著計算機(jī)科學(xué)技術(shù)的不斷進(jìn)步,需要處理的數(shù)據(jù)量和計算量越來越大,對多項式方程求根算法的要求也越來越高。為了能夠又快又好地求得多項式方程的根,本文基于SLEFE (Subdividable Linear Efficient Function Enclose)的理論,結(jié)合裁剪算法在速度和穩(wěn)定性上的優(yōu)勢,提出SLEFE分離算法和SLEFE裁剪算法。對于給定的多項式,SLEFE分離算法能夠快速有效地將多項式方程所有實根所在的區(qū)間分離開來。對于分離所得的每一個子區(qū)間,應(yīng)用SLEFE裁剪算法提高區(qū)間的精度,通過不斷地迭代,得到滿足一定精度的實根所在的區(qū)間,最終得到根的近似解。通過與其他算法進(jìn)行比較,SLEFE裁剪算法用于解決固定區(qū)間內(nèi)只有一個實根的多項式方程求根問題所需的迭代次數(shù)與時間較少。本文還從理論方面證明了SLEFE裁剪算法的收斂速率為2。針對多項式曲線保凸的特殊情況,為了提高計算效率,達(dá)到更高的精度,本文給出了特殊情況下的SLEFE裁剪算法代替SLEFE裁剪算法,實例顯示在多項式曲線保凸的情況下,能達(dá)到更好的逼近效果,計算效率更高。最后,通過分析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.
【學(xué)位授予單位】：合肥工業(yè)大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2016
【分類號】：O151.1;TP391.72

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 李天巖;;求多項式方程組的所有孤立解[J];數(shù)學(xué)進(jìn)展;1988年03期

2 孟實華;關(guān)于有限域上多項式方程組的解數(shù)估計[J];數(shù)學(xué)理論與應(yīng)用;2000年02期

3 劉慶江;使用多項式方程方法的線性二次控制[J];阜新礦業(yè)學(xué)院學(xué)報(自然科學(xué)版);1997年06期

4 劉安心;;求多項式方程組全部解的連續(xù)法[J];工程兵工程學(xué)院學(xué)報;1999年01期

5 馬昭坤,馬躍峰;多項式方程根的求解方法[J];曲阜師范大學(xué)學(xué)報(自然科學(xué)版);2000年03期

6 林永;陳浩;;用二分法求解一元實系數(shù)多項式方程的全部實根[J];大學(xué)數(shù)學(xué);2008年04期

7 范翠香，，馮民權(quán);用牛頓法求多項式方程的全部實根及迭代初值的確定[J];黑龍江水專學(xué)報;1994年02期

8 肖麗霞;包玉蘭;張永富;;關(guān)于多項式方程重根一種求法的探討[J];內(nèi)蒙古民族大學(xué)學(xué)報(自然科學(xué)版);2009年02期

9 胡承鈞;;多項式方程式的解的探討[J];濮陽職業(yè)技術(shù)學(xué)院學(xué)報;2009年05期

10 劉衛(wèi)江;解稀疏多項式方程組特征值方法的第二等價性定理[J];吉林大學(xué)學(xué)報(理學(xué)版);2003年01期

相關(guān)博士學(xué)位論文 前1條

1 張金濤;解多項式方程組和計算多項式矩陣最小多項式的幾個快速算法[D];大連理工大學(xué);2013年

相關(guān)碩士學(xué)位論文 前6條

1 吳星橋;多項式方程求根的裁剪算法研究[D];合肥工業(yè)大學(xué);2016年

2 張金濤;具有m-齊次結(jié)構(gòu)多項式方程組的同倫算法[D];吉林大學(xué);2005年

3 黃海燕;求解多項式方程組的幾種方法[D];東北師范大學(xué);2011年

4 杜配冰;多項式方程求根的高精度算法研究[D];國防科學(xué)技術(shù)大學(xué);2012年

5 王禮萍;理想的Groebner基與特征列[D];吉林大學(xué);2008年

6 賈曉燕;Groebner基的改進(jìn)算法與應(yīng)用研究[D];暨南大學(xué);2009年

本文編號：1984994