多项式实根线性复杂度的9阶收敛计算方法
发布时间：2021-08-02 10:24
提出一种线性计算复杂度的有理五次裁剪方法,需要求解三次方程。对于单根情形的收敛阶可达到9;对于重数k≥2的实根,收敛阶可达到9/k或更好的9/（k-1）。数值算例表明:该算法具有线性计算效率,收敛阶优于已有的有理三次裁剪方法。
【文章来源】：杭州电子科技大学学报(自然科学版). 2020,40(03)
【文章页数】：6 页
【部分图文】：
f1(t)的控制多边形及多项式曲线
其中f3(t)有1个单根,f4(t)在子区间[0.12,0.31]有1个二重根,在子区间[0.57,1.00]内有1个单根,f5(t)有1个三重根。表1给出了4种裁剪方法在多项式f3(t)(t∈[0,1]),f4(t)(t∈[0.12,0.34]),f5(t)(t∈[0,1])上得到的小区间长度(即误差)、对应的收敛阶及平均计算时间的比较,其中i表示第i步的误差结果。可以看出:M1,M2和M3的收敛阶(Convergence Rate,CR)分别为4/k,7/k,5/k。M4对于单根的收敛阶为9,重根的收敛阶为9/(k-1),其中k为根的重数。M3和M4的计算时间接近,且比M1和M2快很多,M3的计算时间最短。表1 例1中误差、收敛阶及平均计算时间的比较 多项式 方法类别 i 平均时间/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多项式 W(t)= ∏ i=1 20 ( t-i) ,多项式曲线及对应的控制多边形如图3(a)所示。在[0,25]内i=1,2,…,20。首先计算相应的控制多边形的零点,使用这些零点将[0,25]分为21个子区间,选择其中的一个区间[0.27,1.55]进一步说明计算细节。图3(b)测试了点到Bézier曲线的最近距离计算问题。表2给出了这4种裁剪方法得到的小区间长度(即误差)、对应的收敛阶及平均计算时间的比较,其中i表示第i步的误差结果。可以看出:M1,M2,M3和M4的收敛阶(CR)分别为4,7,5和9。M3和M4的计算时间接近,且比M1和M2更快;本文方法在所有4种方法中具有最高的收敛阶及优良的计算性能。表2 例2中误差、收敛阶及平均计算时间的比较 区间 方法类别 i 平均时间/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
本文编号：3317396
【文章来源】：杭州电子科技大学学报(自然科学版). 2020,40(03)
【文章页数】：6 页
【部分图文】：
f1(t)的控制多边形及多项式曲线
其中f3(t)有1个单根,f4(t)在子区间[0.12,0.31]有1个二重根,在子区间[0.57,1.00]内有1个单根,f5(t)有1个三重根。表1给出了4种裁剪方法在多项式f3(t)(t∈[0,1]),f4(t)(t∈[0.12,0.34]),f5(t)(t∈[0,1])上得到的小区间长度(即误差)、对应的收敛阶及平均计算时间的比较,其中i表示第i步的误差结果。可以看出:M1,M2和M3的收敛阶(Convergence Rate,CR)分别为4/k,7/k,5/k。M4对于单根的收敛阶为9,重根的收敛阶为9/(k-1),其中k为根的重数。M3和M4的计算时间接近,且比M1和M2快很多,M3的计算时间最短。表1 例1中误差、收敛阶及平均计算时间的比较 多项式 方法类别 i 平均时间/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多项式 W(t)= ∏ i=1 20 ( t-i) ,多项式曲线及对应的控制多边形如图3(a)所示。在[0,25]内i=1,2,…,20。首先计算相应的控制多边形的零点,使用这些零点将[0,25]分为21个子区间,选择其中的一个区间[0.27,1.55]进一步说明计算细节。图3(b)测试了点到Bézier曲线的最近距离计算问题。表2给出了这4种裁剪方法得到的小区间长度(即误差)、对应的收敛阶及平均计算时间的比较,其中i表示第i步的误差结果。可以看出:M1,M2,M3和M4的收敛阶(CR)分别为4,7,5和9。M3和M4的计算时间接近,且比M1和M2更快;本文方法在所有4种方法中具有最高的收敛阶及优良的计算性能。表2 例2中误差、收敛阶及平均计算时间的比较 区间 方法类别 i 平均时间/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
本文编号：3317396
本文链接：https://www.wllwen.com/kejilunwen/yysx/3317396.html
