高级检索
陈小雕, 徐明国, 叶阳天, 段晓慧. 多项式方程区间内求根基于$\mathbb{R}^2$空间的3次裁剪方法[J]. 计算机辅助设计与图形学学报, 2014, 26(11): 1923-1929.
引用本文: 陈小雕, 徐明国, 叶阳天, 段晓慧. 多项式方程区间内求根基于$\mathbb{R}^2$空间的3次裁剪方法[J]. 计算机辅助设计与图形学学报, 2014, 26(11): 1923-1929.
Chen Xiaodiao, Xu Mingguo, Ye Yangtian, Duan Xiaohui. Cubic Tangent Method in $\mathbb{R}^2$ Space for Computing Real Roots of Polynomials Within an Interval[J]. Journal of Computer-Aided Design & Computer Graphics, 2014, 26(11): 1923-1929.
Citation: Chen Xiaodiao, Xu Mingguo, Ye Yangtian, Duan Xiaohui. Cubic Tangent Method in $\mathbb{R}^2$ Space for Computing Real Roots of Polynomials Within an Interval[J]. Journal of Computer-Aided Design & Computer Graphics, 2014, 26(11): 1923-1929.

多项式方程区间内求根基于\mathbbR^2空间的3次裁剪方法

Cubic Tangent Method in \mathbbR^2 Space for Computing Real Roots of Polynomials Within an Interval

  • 摘要: 多项式方程的求根问题在求交、最近距离计算等方面有着广泛的应用.3次裁剪求根方法充分利用了Bernstein基函数较好的计算稳定性,避免了数值迭代求解的不稳定性,同时具有4次收敛的速度.不同于传统的基于\mathbbR^1空间内的3次裁剪方法,提出了基于\mathbbR^2空间内的3次裁剪方法.首先引入\mathbbR^2空间中一条曲线(t,f(t)),在该曲线给定的区间上选取3个点,并计算这3个点及其对应的切向;然后求解3次多项式曲线Ai(u),满足同时插值这3个点及其中2个点处的切向;最后选择适当的重新参数化函数φ(t),使得Ai(φ(t))和f(t)之间具有5次逼近阶.若给定的参数区间Φ充分小,A1(φ(t))和A2(φ(t))可以在区间Φ内直接包住f(t),从而节省了用于求解包围多项式的大量计算.实例结果表明,该方法具有更好的逼近效果、更快的收敛速度和更高的计算效率.

     

    Abstract: The root finding problem has wide applications in intersection, minimum distance computation, and so on.The cubic clipping method utilizes the stability of the computation by using Bernstein basis functions and avoids the unstability of the numerical solution.It also has the convergence rate of order 4.Different from previous clipping methods approximating f(t) in \mathbbR^1 space, this paper presents an improved cubic clipping method approximating (t, f(t)) in \mathbbR^2 space instead, which has a higher convergence rate of order 5 for a single root.It selects three points on the curve (t, f(t)), and constructs two cubic polynomial curves Ai(u), i=1, 2 which interpolate both three points and two of their three directional tangent vectors.By using a suitable reparameterization function φ(t), Ai(φ(t)) and f(t) have the approximation of order 5. Furthermore, when the length of the given interval is small enough, the two polynomials Ai(u) can be directly used as the two bounding polynomials, which avoids the corresponding time-consuming computation needed in the previous cubic clipping method.Examples show the better efficiency, approximation effect and convergence rate of the new method.

     

/

返回文章
返回