多項(xiàng)式方程求根的裁剪方法及應(yīng)用研究.pdf

1、多項(xiàng)式求根和計(jì)算點(diǎn)到曲線的最小距離是計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)領(lǐng)域的基本問(wèn)題之一。它有著廣泛的應(yīng)用,比如游戲中普遍存在的碰撞檢測(cè)、數(shù)控加工中加工刀具與加工物體的干涉檢測(cè)、幾何造型系統(tǒng)中點(diǎn)到曲面的距離查詢(xún),也可用于評(píng)價(jià)曲線的擬合精度和輪廓度誤差、曲線曲面的匹配等。
　　本文的主要研究?jī)?nèi)容包括:首先,針對(duì)多項(xiàng)式求根問(wèn)題,提出了基于R1空間相切的三次幾何裁剪方法。跟傳統(tǒng)的方法相比,新方法具有相同的逼近階,同時(shí)顯著地提高了計(jì)算效率。直接構(gòu)造出

2、兩條三次多項(xiàng)式,使得很多情形下都可以在給定區(qū)間內(nèi)直接包住給定的多項(xiàng)式,從而避免了現(xiàn)有方法中耗時(shí)的誤差估算。在一定條件下,直接構(gòu)造的多項(xiàng)式同時(shí)還是誤差最小的包圍多項(xiàng)式,改善了逼近誤差。其次,針對(duì)多項(xiàng)式求根問(wèn)題,提出了基于R2空間內(nèi)的三次幾何裁剪新方法。同以往的基于R1空間內(nèi)的方法相比,新方法具有更高的逼近階,即5階。幾何裁剪方法仍保留了Bernstein基函數(shù)較好的計(jì)算穩(wěn)定性,同時(shí)提高了收斂速度,顯示了較明顯的優(yōu)勢(shì)。很多情況下,給定多項(xiàng)式

3、f(t)的根,可被新方法中直接構(gòu)造的三次多項(xiàng)式對(duì)應(yīng)的實(shí)根包住,因此節(jié)省了計(jì)算包圍多項(xiàng)式的大量計(jì)算。實(shí)例也說(shuō)明了新方法具有更高的計(jì)算效率和更快的收斂速度。最后,提出了基于曲線逼近的點(diǎn)到曲線最小距離計(jì)算方法。將本文的幾何裁剪思路應(yīng)用到點(diǎn)/曲線最小距離的計(jì)算中。首先用若干段二次曲線去逼近給定的曲線,點(diǎn)/二次曲線的最小距離可以有顯式的解析解,求解計(jì)算可以較為簡(jiǎn)便高效。同時(shí),利用幾何逼近的理論來(lái)估算給定曲線與二次逼近曲線間相應(yīng)的誤差,從而快速排除