An Approach for Certifying Homotopy Continuation Paths: Univariate Case
An Approach for Certifying Homotopy Continuation Paths: Univariate Case
复制标题
证明同伦连续路径的方法：单变量情况
DOI：
10.1145/3208976.3209010
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
C. Yap
中科院分区：
文献类型：
--
作者：
Juan Xu;M. Burr;C. Yap
同伦延拓是一种著名的数值求根方法。最近，基于Smale的α-理论的同伦延拓的认证算法已经开发出来。这种方法在每一步都有非常严格的要求，导致步长很小。在本文中，我们提出了一种独立于α理论的方法。它是基于较弱的概念，以及孤立的近似的根源。我们将其应用到一元多项式，并提供其可行性的实验证据。
Homotopy continuation is a well-known method in numerical root-finding. Recently, certified algorithms for homotopy continuation based on Smale's alpha-theory have been developed. This approach enforces very strong requirements at each step, leading to small step sizes. In this paper, we propose an approach that is independent of alpha-theory. It is based on the weaker notion of well-isolated approximations to the roots. We apply it to univariate polynomials and provide experimental evidence of its feasibility.