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算法也具有机器学习的想法和特征，即通过不断迭代的方法找到最佳的逼近函数。

习题

（1）在计算机上安装Anaconda 3版本。在Spyder环境下使用Python。

（2）自己生成一个定义在（0，10）的线性函数，如

f（x）=2x+5

然后随机从这个区间中选取20个点，在这些点上加一些白噪声，如一个均值为0的正态分布

y_i=2x_i+5+ω_i

这里ω_i∼N（0，σ）。依次使用1，2，3，4，···，10次多项式，使得

达到最小。同时使用不同的σ重新计算函数g（x），并画图观察不同多项式逼近函数的表现。

（3）在第（2）题的基础上，使用

使其达到极小。同时使用不同的σ重新计算函数g（x），并画图观察不同多项式逼近函数的表现。在完成上面两个优化时，可以使用Python中的优化函数。

（4）在第（2）题的基础上，使用

使其达到极小。同时使用不同的σ重新计算函数g（x），并画图观察不同多项式逼近函数的表现。在完成上面两个优化时，可以使用Python中的优化函数。

（5）在第（2）题的基础上，用Remez算法使得

达到极小，而不是使用现有的优化函数库。