多項式方程求根的裁剪算法研究.pdf

1、多項式方程求根是計算機輔助幾何設(shè)計領(lǐng)域的基本問題之一，在碰撞檢測、干涉檢查等領(lǐng)域有著非常多的應(yīng)用。隨著計算機科學(xué)技術(shù)的不斷進步，需要處理的數(shù)據(jù)量和計算量越來越大，對多項式方程求根算法的要求也越來越高。
　　為了能夠又快又好地求得多項式方程的根，本文基于SLEFE(SubdividableLinear Efficient Function Enclose)的理論，結(jié)合裁剪算法在速度和穩(wěn)定性上的優(yōu)勢，提出SLEFE分離算法和SLEFE

2、裁剪算法。對于給定的多項式，SLEFE分離算法能夠快速有效地將多項式方程所有實根所在的區(qū)間分離開來。對于分離所得的每一個子區(qū)間，應(yīng)用SLEFE裁剪算法提高區(qū)間的精度，通過不斷地迭代，得到滿足一定精度的實根所在的區(qū)間，最終得到根的近似解。通過與其他算法進行比較，SLEFE裁剪算法用于解決固定區(qū)間內(nèi)只有一個實根的多項式方程求根問題所需的迭代次數(shù)與時間較少。本文還從理論方面證明了SLEFE裁剪算法的收斂速率為2。針對多項式曲線保凸的特殊情況，