Novel Range Functions via Taylor Expansions and Recursive Lagrange Interpolation with Application to Real Root Isolation
Novel Range Functions via Taylor Expansions and Recursive Lagrange Interpolation with Application to Real Root Isolation
复制标题
DOI：
10.1145/3452143.3465532
复制
发表时间：
2021-07
期刊：
影响因子：
--
通讯作者：
K. Hormann;Lucas Kania;C. Yap
中科院分区：
文献类型：
--
作者：
K. Hormann;Lucas Kania;C. Yap
范围函数是间隔计算的重要工具，可以用于根部隔离问题。在本文中，我们首先引入了两个新的范围函数，以实现实际功能。它们基于Cornelius和Lohner [7]的其余形式，并为此形式的其余部分提供了不同的改进。一方面，我们使用集中的泰勒膨胀来得出具有高于二次收敛的经典泰勒形式的概括。另一方面，我们提出了一个递归插值程序，尤其是基于二次拉格朗日插值，从而导致具有立方和四分之一收敛的递归拉格朗日形式。然后，我们使用这些形式与算法eval隔离无方形多项式的真实根，这是一种相对较新的算法，已被证明是有效且实用的。最后，我们将新范围函数的性能与标准泰勒形式进行了比较。范围函数通常是孤立比较的；相比之下，我们的整体比较是基于它们在应用程序中的性能。具体而言，eval可以利用我们的递归拉格朗日形式的特征，这些特征是基于泰勒扩展的范围函数中未找到的。在实验上，这在评估中至少产生了两倍的速度。
Range functions are an important tool for interval computations, and they can be employed for the problem of root isolation. In this paper, we first introduce two new classes of range functions for real functions. They are based on the remainder form by Cornelius and Lohner [7] and provide different improvements for the remainder part of this form. On the one hand, we use centered Taylor expansions to derive a generalization of the classical Taylor form with higher than quadratic convergence. On the other hand, we propose a recursive interpolation procedure, in particular based on quadratic Lagrange interpolation, leading to recursive Lagrange forms with cubic and quartic convergence. We then use these forms for isolating the real roots of square-free polynomials with the algorithm Eval, a relatively recent algorithm that has been shown to be effective and practical. Finally, we compare the performance of our new range functions against the standard Taylor form. Range functions are often compared in isolation; in contrast, our holistic comparison is based on their performance in an application. Specifically, Eval can exploit features of our recursive Lagrange forms which are not found in range functions based on Taylor expansion. Experimentally, this yields at least a twofold speedup in Eval.