Remez 交换算法

等幅方程让当前参考点的峰同高，交换则把被遗漏的更高峰放进来。交错下界理路Chebyshev 交错定理Chebyshev alternation theorem · Equioscillation theorem · 等振荡定理用交替达到最大误差的点认证最佳多项式，完整证明必要、充分、唯一性及近最佳下界。与全域上界理路一致误差的全区间证书Uniform error certification · Continuous supremum error bounds把临界点、连续模或非负基包围变成全区间误差上界，并说明有限采样本身不能证明上确界。始终承担不同任务：前者证明所有候选都不能优于 $L$，后者证明当前候选不差于 $U$。

交换确实提高下界。对新参考点 $y_0<\cdots <y_{n+1}$，令

次数至多 $n$ 的多项式 $q$ 满足 $\sum _i{w}_{i}q(y_i)=0$，因为这是它在 $n+2$ 点的 Lagrange 表示中 $x^{n+1}$ 的系数，而该系数为零。$w_i$ 的符号为 $(-1{)}^{n+1-i}$，故 $w_i(-1{)}^i$ 全同号。对新等幅方程相加，得到

可将分子中的 $f$ 换成旧残差 $e$，因为旧 $p$ 的和为零。若新点上旧残差仍交替，所有绝对值至少为 $|h|$，并有一点严格更大，上式的绝对值是这些绝对误差以 $|w_i|$ 加权的平均，因而严格大于 $|h|$。这证明精确交换的进步，不等于证明任意浮点实现都会收敛。

对 $f=x^3$、$[-1,1]$、$n=1$，取初始参考点 $(-1,0,1/2)$。等幅方程的解为

三个参考误差为 $(-1/8,+1/8,-1/8)$。残差导数仍为 $3x^2-3/4$；完整检查端点及 $\pm 1/2$ 得

所以 $L_0=1/8$、$U_0=3/8$。最大点并列时取较左的 $-1/2$，它位于 $-1$ 和零之间，误差为正，故替换同号的零。新参考为 $(-1,-1/2,1/2)$，重解得

再次检查全区间临界点，得 $U_1=1/4=L_1$，算法凭上下界相合结束。这是实际改变参考点的一次交换，不是先给出最优解再画等高峰。

若初始参考反而取 $(-1,0,1)$，系统给 $p=x,h=0$。三个采样误差全为零，区间内却在 $\pm 1/\sqrt{3}$ 有大小 $2/(3\sqrt{3})$ 的误差。零幅表示当前符号交换退化，只有另外证明 $f=p$ 才能称为精确成功；否则应重选互异参考点，例如上面的非对称三点。

一个可复核的实现至少返回候选多项式、参考点、方程残差、$L,U$、全域搜索方法和退出理由。输入无效、非有限函数值、病态系统导致求解不可靠、无法找到足够交替点、点合并、重复参考集合、进步停滞或达到预定工作预算，都应返回失败或未认证候选，保留当前证据。

已认证的停止规则可以是 $U-L\le {\tau }_{\mathrm{a}\mathrm{b}\mathrm{s}}+{\tau }_{\mathrm{r}\mathrm{e}\mathrm{l}}U$，其中容差由任务给定，$U$ 必须真为全域上界。它认证当前误差与最佳误差的差距，不一定认证所有多项式系数都已接近最优系数。浮点参考误差若只“近似等高”，应用已验证符号和实际绝对误差的最小下界，而非直接把求解器打印的 $|h|$ 当作严密下界。

在平滑、非退化的极值结构附近，适当的 Remez 变体可以很快；一般连续函数可能有尖点、平坦极值或许多局部峰，搜索与交换规则需要相应处理。工程上常用缩放后的 Chebyshev 基或重心表示，避免把高次单项式系统的病态误当成逼近问题无解。本文不把有理函数的非线性分母问题纳入这一线性系统。