1.3 多项式Remez算法

前面我们使用 L ² 距离的好处就是在这个定义下，两个函数 f，g 自然定义了一个二次型

在这个二次型下面，函数构成了希尔伯特空间。在希尔伯特空间下就可以定义垂直等概念。

除了这个 L ² 距离以外，还可以定义其他的距离，例如，重新定义两个函数的距离为

这个定义称为 L ^∞ 距离。在这个距离下，得到的最佳逼近也就有所不同了。一般对于这样的问题，首先要考虑最佳逼近是否存在，其次考虑最佳逼近是否具有特殊的性质。下面的定理回答了这个问题。

定理1.1 已知连续函数 f （ x ），一个 n 次多项式函数 g （ x ）在 L ^∞ 距离下的最佳逼近函数

存在且应满足以下形式：函数 f （ x ）- g （ x ）满足有 x ₀ ＜ x ₁ ＜···＜ x _{n +1} ，使得对于每个0≤ i ≤ n +1，有

同时对于每个0≤ i ≤ n ，有

证明 这里先证明满足上述性质的函数必然是最佳逼近。至于存在性的证明，将在定理1.2中阐述。假设已经存在函数 g （ x ），则这个函数是最佳函数。否则，一定有另外一个 n 次多项式函数 h （ x ）可以进行更好的逼近。这个函数应满足

因此有

不妨假设

从而得到

以此类推，可以看到函数 h （ x ）- g （ x ）作为 n 次多项式，竟然有至少 n +1个零点，除非 h （ x ）= g （ x ）。至此，我们就证明了这个定理。证毕

L ^∞ 逼近如图1.3所示。

上述定理说明，在多项式的空间中有一个最佳逼近函数。最佳逼近函数应该是一个 n 次多项式，其性质是存在 n +2个点，这些点距离多项式函数值的差别都一致，且符号逐个相反。例如，使用4次多项式，那么就应该有6个点 y ₁ ，y ₂ ，··· ，y ₆ ，使得

且（ g （ x _{i -1} ）- f （ x _{i -1} ））·（ g （ x _i ）- f （ x _i ））＜0。

定理1.1 讲述了这个最佳逼近函数的充分条件。但是，并没有说明如何得到这个充分条件。下面介绍Remez算法。这个算法可以帮助我们找到这个函数，同时也就证明了这个函数的存在及其必要条件。首先，任意选取一组点

x ₀ ＜ x ₁ ＜···＜ x _{n +1}

然后求解方程

上面是一个线性方程组，有 n +2个方程，同时有 n +2个未知数。解方程组以后决定的多项式 g （ x ）未必是最佳，因为有些点如 上有

这时把上述 点取代其最临近的一个点，且应保持和该点上函数值的差同样的符号，再次重复上述步骤。这个步骤不断重复，得到的 ϵ 也会不断增加逐渐收敛。每次取到的点 x _i 在闭区间上也会不断收敛，而得到的 f （ x ）也会不断收敛到一个 n 次多项式。这个过程就是Remez算法。

我们使用的是多项式逼近连续函数的语言，但是在实际操作中往往针对一组离散的点集，所以下面在点集是离散的情况下证明Remez迭代算法的收敛性，事实上是迭代算法的有限步就结束性。

定理1.2（Remez算法） Remez算法一定收敛。在有限个点的情况下，Remez算法一定在有限步内收敛。

证明 对于 f （ x ） ，g （ x ）以及 x ₀ ，x ₁ ，··· ，x _{n +1} ，已经满足了以下条件

但是函数 g （ x ）还不是最佳逼近。此时若有点 （为了不失一般性，假设 x ₀ ＜ ）满足

而 ϵ ，用 来解方程

得到的 ϵ ₁ 必然满足 ϵ ₁ ＜ ϵ ，否则 f （ x ）- g （ x ）会在 处变号从而矛盾。如果每次都不能得到最佳逼近，就有一系列的 ϵ _k 单调递增，由此得到的 x _i 应该收敛，但是因为有限集合，所以有限次以后得到的点必然是固定的，从而不可再递降。证毕

通过上面的分析，我们得到几个结论，为了控制过分拟合，需要控制多项式的次数，在限定多项式次数时，在不同距离函数下面，会有不同的最佳逼近。上面两个例子的背后就对应着线性回归和支持向量机。同时Remez算法也具有机器学习的想法和特征，即通过不断迭代的方法找到最佳的逼近函数。 WKPIox9GGc0eTEaZ4/v4wPR8OlGLRgGaRjmwGTrFLmRhYKHm5+mnX0phAmoniqGR