给定最大误差的分段多项式阶数和节点数+位置优化

Question

我试图用一组分段多项式来近似数字滤波器脉冲响应：

1. 分段数（结数）是整个区间[0,1]上的一个自由参数。为了给出问题大小的透视图，我希望有256到1024个分段作为一个良好的近似值
2. 节点位置必须落在间隔[0,1]上的2整数网格的幂上，以便于多项式选择的硬件实现
3. 每个段的多项式阶数可以不同，越低越好。已知最大阶数（可以设置为2或3）
4. 只要遵守（2），每个段的长度就不必相等

例如，[0,1/256]上的线性段后跟[1/256,22/256]上的三阶段，再后跟[22/256,1]上的二阶段就可以了

其目标是在拟合曲线和理想曲线之间的均方误差或最大误差低于给定值的情况下，最小化分段数量及其顺序的某种组合，以降低总体计算/内存成本（折衷待定义）

我知道我可以对整个空间进行暴力搜索，并计算每个允许的多项式阶和每个允许的段的最大误差。然后，我可以通过遍历这个大表来“构造”最终的分段曲线-尽管我不完全确定如何精确地进行最终构造

我想知道这是否是一个已经存在算法的“已知”类型的问题。欢迎任何评论

Answer 1

您可以尝试Ramer–Douglas–Peucker algorithm的变体。这是一个易于实现的简化多边形线的算法。在您的上下文中，多边形线是网格点处过滤曲线的样本，算法证明最大误差小于某个阈值

如果需要平滑曲线，可以修改算法以实现二次样条插值，而不是多段线近似（对应于线性样条插值）和类似的三次样条插值以实现二阶连续性。在每次迭代中，将最远的采样点添加到插值点集中，并重新计算插值样条曲线

另一个稍有不同的选择是使用least-square approximating spline代替插值样条线。在每次迭代中，在距离最远的网格点处添加一个新的结，但曲线不需要通过它

这种方法虽然简单，但满足了大多数需求，并在实践中取得了良好的效果。 然而，它可能不会给出理论上的最优解（尽管我目前没有反例）