零误差计算

On zero-error computation

研究采用有误差的数值计算来获得无误差的准确值具有重要的理论价值和应用价值.这种通过近似的数值方法获得准确结果的计算被称为零误差计算.本文首先指出,只有一致离散集合中的数才能够开展零误差计算,即有非零隔离界的数集,这也是"数"可以进行零误差计算的一个充要条件.以此为基本出发点,本文分析代数数零误差计算的最低理论精度,该精度对应于恢复近似代数数的准确值时必要的误差控制条件,但由于所采用恢复算法的局限性,这一理论精度往往不能保证成功恢复出代数数的准确值.为此,本文给出采用PSLQ (partial-sum-LQ-decomposition)算法进行代数数零误差计算所需的精度控制条件,与基于LLL (Lenstra-Lenstra-Lovász)算法相比,该精度控制条件关于代数数次数的依赖程度由二次降为拟线性,从而可降低相应算法的复杂度.最后探讨零误差计算未来的发展趋势.

It is important both in theory and in practice to study how to obtain exact results via numeric computation, which we call zero-error computation. In this paper, we firstly indicate which kind of numbers are suitable for zero-error computation: One can compute the exact value from its approximate values for every element in a uniformly discrete set, in which there exists a nonzero separation bound between two distinct elements.Based on this observation, we give such a separation bound for algebraic numbers, which can be seen as a necessary condition on error control for zero-error computation of algebraic numbers. However, this condition may not be sufficient, depending on different algorithms. For the PSLQ(partial-sum-LQ-decomposition)-based algorithm,we give a sufficient condition on the precision that is quasi-linear in the degree of the algebraic number to be recovered, while the corresponding condition for the LLL(Lenstra-Lenstra-Lovász)-based algorithm is quadratic.We also suggest several potential research areas in the future.