提出一種線性計(jì)算復(fù)雜度的有理五次裁剪方法,需要求解三次方程。對(duì)于單根情形的收斂階可達(dá)到9;對(duì)于重?cái)?shù)k≥2的實(shí)根,收斂階可達(dá)到9/k或更好的9/（k-1）。數(shù)值算例表明:該算法具有線性計(jì)算效率,收斂階優(yōu)于已有的有理三次裁剪方法。 

【文章來(lái)源】：杭州電子科技大學(xué)學(xué)報(bào)(自然科學(xué)版). 2020,40(03)

【文章頁(yè)數(shù)】：6 頁(yè)

【部分圖文】：

f1(t)的控制多邊形及多項(xiàng)式曲線

其中f3(t)有1個(gè)單根,f4(t)在子區(qū)間[0.12,0.31]有1個(gè)二重根,在子區(qū)間[0.57,1.00]內(nèi)有1個(gè)單根,f5(t)有1個(gè)三重根。表1給出了4種裁剪方法在多項(xiàng)式f3(t)(t∈[0,1]),f4(t)(t∈[0.12,0.34]),f5(t)(t∈[0,1])上得到的小區(qū)間長(zhǎng)度(即誤差)、對(duì)應(yīng)的收斂階及平均計(jì)算時(shí)間的比較,其中i表示第i步的誤差結(jié)果�？梢钥闯�:M1,M2和M3的收斂階(Convergence Rate,CR)分別為4/k,7/k,5/k。M4對(duì)于單根的收斂階為9,重根的收斂階為9/(k-1),其中k為根的重?cái)?shù)。M3和M4的計(jì)算時(shí)間接近,且比M1和M2快很多,M3的計(jì)算時(shí)間最短。表1 例1中誤差、收斂階及平均計(jì)算時(shí)間的比較 多項(xiàng)式 方法類別 i 平均時(shí)間/ms CR 1 2 3 4 5 f3(t) M1[1] 5.9e-2 4.5e-7 1.4e-27 1.6e-109 2.1e-437 17.5 4 M2[6] 8.7e-5 8.4e-34 6.7e-237 — — 11.5 7 M3[7] 2.5e-3 2.6e-16 3.1e-81 7.5e-406 — 3.4 5 M4 7.9e-9 1.7e-83 1.5e-755 — — 5.8 9 f4(t) M1[1] 3.5e-2 7.7e-4 3.5e-7 7.2e-14 3.1e-27 24.8 4/2 M2[6] 7.9e-3 5.6e-8 5.2e-26 4.0e-89 5.1e-310 22.0 7/2 M3[7] 1.8e-2 2.6e-5 6.0e-14 1.1e-39 6.2e-117 5.7 5/2 M4 1.5e-7 1.0e-63 3.6e-569 — — 8.2 9 f5(t) M1[1] 8.9e-2 4.6e-3 6.6e-5 2.3e-7 1.2e-10 27.7 4/3 M2[6] 1.5e-2 5.3e-6 3.8e-14 4.3e-33 2.0e-77 28.1 7/3 M3[7] 2.0e-1 1.2e-2 4.4e-5 7.5e-10 2.5e-17 6.7 5/3 M4 1.2e-3 7.0e-18 2.5e-92 4.0e-477 — 9.2 9/2

例2 給定Willkinson多項(xiàng)式 W(t)= ∏ i=1 20 ( t-i) ,多項(xiàng)式曲線及對(duì)應(yīng)的控制多邊形如圖3(a)所示。在[0,25]內(nèi)i=1,2,…,20。首先計(jì)算相應(yīng)的控制多邊形的零點(diǎn),使用這些零點(diǎn)將[0,25]分為21個(gè)子區(qū)間,選擇其中的一個(gè)區(qū)間[0.27,1.55]進(jìn)一步說(shuō)明計(jì)算細(xì)節(jié)。圖3(b)測(cè)試了點(diǎn)到Bézier曲線的最近距離計(jì)算問(wèn)題。表2給出了這4種裁剪方法得到的小區(qū)間長(zhǎng)度(即誤差)、對(duì)應(yīng)的收斂階及平均計(jì)算時(shí)間的比較,其中i表示第i步的誤差結(jié)果�？梢钥闯�:M1,M2,M3和M4的收斂階(CR)分別為4,7,5和9。M3和M4的計(jì)算時(shí)間接近,且比M1和M2更快;本文方法在所有4種方法中具有最高的收斂階及優(yōu)良的計(jì)算性能。表2 例2中誤差、收斂階及平均計(jì)算時(shí)間的比較 區(qū)間 方法類別 i 平均時(shí)間/ms CR 1 2 3 4 5 圖3(a)[0.27,1.55] M1[1] 1.2e-2 2.5e-9 4.5e-36 5.0e-143 7.4e-571 63.2 4 M2[6] 7.6e-4 1.3e-17 6.0e-114 1.2e-786 — 61.5 7 M3[7] 2.4e-4 2.6e-15 3.9e-70 3.0e-344 — 7.1 5 M4 5.6e-6 2.4e-33 4.3e-255 — — 16.3 9 圖3(b)[0,1] M1[1] 5e-2 1e-6 1e-25 1e-1100 7e-401 81.6 4 M2[6] 2e-3 5e-23 2e-160 2e-1122 — 73.4 7 M3[7] 2e-3 3e-11 1e-48 2e-234 5e-1162 9.5 5 M4 9e-5 2e-42 1e-381 1e-3422 — 19.6 9


本文編號(hào)：3317396