一种用于优化多项式近似中近似误差和有限精度评估误差的交换算法

《ACM Transactions on Mathematical Software》：An Exchange Algorithm for Optimizing both Approximation and Finite-Precision Evaluation Errors in Polynomial Approximations

本文提出一种半无限线性优化问题解决方法，结合迭代交换算法处理多项式近似中的舍入误差和计算误差，并给出基于Sollya库的C语言实现及实验验证。

　　

摘要

数学函数的有限精度实现通常依赖于多项式逼近。这种方法的一个关键特点是，在用有限数量的比特表示多项式的系数时，以及在有限精度算术中计算该多项式时，都会产生舍入误差。因此，为了找到给定固定度数、范数和区间下的最佳多项式，必须同时考虑逼近误差和浮点计算误差。虽然已经开发出了有效的算法来处理逼近误差，但计算部分通常是以一种“事后”的、特定的方式处理的。在这里，我们提出了一个半无限线性优化问题，其解是使得两种误差之和的上确界范数最小的多项式。然后使用迭代交换算法来解决这个问题，该算法可以看作是著名的Remez交换算法的扩展。本文提供了一个使用Sollya库的开源C语言实现，并通过几个示例对其进行了测试和与现有的Sollya程序进行了比较。