动机
插值要求精确重现选定样本,另一种目标却是在整个区间上让最大误差尽可能小。两者可能不同:多项式离开样本值,将误差更平均地分配,反而可以降低最坏误差。要判断这种取舍,需要先说清楚使用什么范数、优化哪个量。
一致近似有一个具体的最优证书:最佳 次以内多项式的误差,在至少 个有序点以交替符号达到最大绝对值。这个点数来自竞争多项式之差所能具有的零点数。本节用连续性、紧致性和初等多项式事实证明两个方向,以及存在和唯一性,不要求目标可微。
定义
定义 16.1.1
(最佳一致近似)
固定非退化闭区间 、实连续函数 及整数 。 表示次数不超过 的实多项式,包括零多项式。定义
连续性和紧致性保证最大值存在。达到下确界的多项式称为最佳一致近似,也称极小极大近似:把最大绝对误差最小化。本节不加权。
定义 16.1.2
(交错极值点列)
对候选 ,记 、。当 ,若有
称它们为交错极值点列。这些点的误差达到极值,而非插值节点上的误差零点。次数界包括常数系数。若 ,则最佳误差为零,唯一最佳多项式就是 ,无需正误差的交错论证。
定义 16.1.3
(Chebyshev 多项式)
Chebyshev 多项式由 定义。递推 ,起点 ,证明它是多项式。当 ,首项系数为 ,在 的值交替为一和负一。
定理/命题
定理 16.1.4
(存在、交错与唯一性)
闭区间上的每个实连续函数,在 中都有唯一最佳一致近似。若候选 的误差 ,则它最佳,当且仅当误差具有至少 个交错极值点,等价于包含长度 的交错点列。
这里涉及整个区间及精确的极值幅度,有限网格中看到交替图案,本身不是连续问题的证书。
推论 16.1.5
(Chebyshev 极值对应实际最佳近似)
在 上, 的唯一最佳 次以内近似为
等价地, 是唯一具有最小一致范数的首一 次多项式。在 ,相应首一余项为
最佳近似为 ,误差为 。
证明思路或证明
先证明最优值确实达到
证明
(由系数空间的紧致性得出最优值达到)
取极小化序列 ,使 。去掉有限项后可假设这些误差至多 。在区间中固定 个互异点,所有 在这些点的值都被 控制。
从多项式系数到这组值的线性映射可逆:核内多项式具有 个互异零点且次数至多 ,所以只能为零。因此系数向量在有限维空间中有界,存在收敛子序列。极限系数定义多项式 ;区间有界,各单项式有界,所以系数收敛推出一致收敛。范数的反三角不等式给出 。注意无需整个极小化序列都收敛。
交错排除更好的竞争者
证明
(以差的零点数证明充分性)
设 具有 个交错极值点。若 的误差严格更小,令 。在 处, 强迫 ;在 处则强迫 。因此 在每两个相邻极值点之间变号,介值定理给出 个互异零点,与非零 次以内多项式的次数矛盾。零多项式也不具有要求的严格符号,所以不存在更好的 。
交错不足时构造一致改进
证明
(以同号扰动证明必要性)
这个方向不能只看几个局部峰值。设
它们都是紧致集, 非空。若两种符号都有,两个不交紧致集的距离严格为正。从 最左点出发,取其右方第一个反号极值点,继续重复。每次转换至少跨过该正距离,所以只能转换有限次;若只有一个符号,就只有一组。
这样将有序极值集分成连续的同号组,组间符号交替。在下一组首点之前,上一组有最后一个极值点;紧致性和正距离排除了同号点向反号点聚集的可能。因此相邻组之间存在不含 的非空间隙。若不存在长度 的交错点列,组数只能是 。
在每个间隙中选一个分隔点 。取
让它在第一组与 同号。跨过间隙时两者都翻号,所以在全部极值组同号。若仅一组,取适当常数。 次数至多 ,在 上没有零点,故紧致性给出 。另记 。
连续性保证 有相对开邻域 ,其中 同号、、。取足够小的 ,使 ,相减便不会越过零,于是 内
若补集 非空,它紧致且不含极值点,所以存在 使该处误差至多 。再要求 ,便有
两个一致上界合起来说明 的全局误差严格更小。因此最佳正误差多项式必须具有足够交错。关键不仅是移动最坏点,还要保护其他位置,避免产生新的更坏误差。
证明透视
区块数目与次数在哪里相遇
必要性的证明是逆否命题:由交错不足,构造严格更好的多项式 。它需要三个不同的成分,各自用到不同的假设。
第一,把极值集合 分成至多 个同号区块。这里 的连续性不可缺少:它使 与 紧致且不相交,因而相距为正,于是区块只有有限个,而且相邻区块之间有真正的间隙。 正是“不存在长度 的交错点列”的否定形式。
第二是关键一步:每个间隙取一个分隔点,得到次数 的 ,所以 是 中容许的方向;而且它在整个 上与 同号,不只是在几个看得见的峰值处。次数界只在这里用到,而且与充分性证明的计数相同:在那里, 个交错点迫使次数至多 的多项式有 个零点。
第三是步长。在 附近,因为符号一致,且 防止越过零,减去 会降低 。远离 时, 的紧致性给出严格余量 ,而 使扰动留在余量之内。没有这个余量,一个在 之外但 接近 的点便可能成为新的最坏点。
最佳多项式为什么唯一
证明
(以平均两个最佳近似证明唯一性)
若两个不同多项式 都最佳、误差为正数 ,其平均也最佳:凸性给出误差至多 ,最小性又迫使等号。在平均误差达到 或 的点,原来两个误差都必须等于同一个端点,因为两个 中数的平均只有这样才到达端点。因此 在平均的所有极值点相同。必要性给出 个这种点,迫使 恒零,矛盾。零误差情况已直接处理。
从节点乘积上界到真正的优化解
证明
(Chebyshev 余项是最优的)
与 的首项抵消,所以 次数至多 。其误差在有序余弦点达到 个交错极值,定理给出最佳性及唯一性。每个首一 次多项式都可写为 、,所以首一极值问题等价。仿射变换给出一般区间公式,其中系数恰保证首项为一。
例题详解
例题 16.1.6
(二次函数的最佳直线是常数)
在 近似 ,取 。误差介于 和 ,并在 取 。三个交错极值认证它不仅是最佳常数,也是 中唯一最佳。端点插值给出直线一,最大误差为一,是最优值的两倍。若在 插值,则恰得到 。所以插值与最佳近似可以相同,却不是必然。
例题 16.1.7
(最佳二次近似不一定有二次项)
,所以 在 中的最佳近似为 ,误差为 。余项在 依次为 ,也认证它在较小空间 中最佳。规定的是次数上界,不要求实际使用最高次项。
例题 16.1.8
(不可微函数也有交错证书)
对 ,取 。令 ,则
因此误差绝对值至多 。在 ,误差从负开始交替,任取连续四点便认证最佳二次近似;完整五点甚至认证它在 中最佳。零点处的尖角不影响定理,因为只要求连续,不要求导数。
常见错误
反例模式
积分误差范数小不能控制峰值
在 令 ,其中 。零多项式的一致误差为一,但平方 误差为 ,趋近零。优化积分范数与优化最大误差是不同问题。狭窄连续峰值对积分平均或粗网格可能几乎不可见。
常见错误
(变号不等于交错)
交错要求误差在每个列出的点都达到完整的 (其中 ),而不只是变号若干次。对 上的 与常数 ,误差 在 的值为 :三点的符号交替,但 。其范数 大于最优值 ,所以即使只在常数中比较,它也不是最佳近似。
误差的任何交错符号模式都给出最佳误差的下界,交换算法正是借此监控进度。
自然的下一个问题
不是最佳的候选多项式还能证明什么?
误差的任何交错符号模式都给出最佳误差的下界,交换算法正是借此监控进度。
若 在有序点 处取符号交错的非零值,则 :若某竞争者 的误差更小, 在每一点都与 同号,于是有 个零点。连同上界 ,便把 夹在中间。对上面的 ,有 。Remez 交换算法通过移动这些点来收窄这个区间。
定理提供证书,不是寻找极值点的完整数值算法。网格最大值可能漏掉中间峰值。若误差已知是 -Lipschitz,且任意点离最近检查网格点至多 ,三角不等式给出 。这才是有依据的网格到连续域上界;单有连续性不给出明确数值余量。
概念视角结构
零点规定插值,交替峰值认证最优
插值在指定节点使误差为零,极小极大近似在由解决定的位置让最大误差交替。因此最佳多项式可以不通过样本值,却降低最坏误差。两者都利用多项式维数,使用方式却不同。
总结
系数空间的紧致性证明存在,交错极值通过零点数排除更好竞争者。反之,符号组太少时可用多项式扰动实现一致改善,再用平均证明唯一。Chebyshev 余项解决首一极值问题,并产生幂函数的显式最佳近似;有尖角的连续目标也适用。
练习
快速检查
(连续实函数在紧致区间的最小最大值为 。求最佳常数及误差,包含 ,并证明唯一性。)
解答 · 答案
常数 的最大误差为 ,唯一最小值 在 达到。更小半径无法同时覆盖两个极值,而最小半径强迫中心为中点。若 ,精确常数是唯一零误差选择。
快速检查
(求 上 的最佳二次以内近似,展开系数,列出四个交错极值点及其误差。)
解答 · 答案
最优首一余项为 。因此近似为 ,误差为 。在 ,误差依次为 ,认证二次最佳性。
快速检查
(证明 是 上 的最佳二次近似。比较它与节点 插值的最大误差。)
解答 · 答案
误差为 ,范数为 。在 交替达到正负极值,故对二次空间适用定理。指定三节点的插值为 ,误差 在 与零之间,范数为 ,是最优误差的两倍。
快速检查
(对一次以内近似,两个交错极值点是否足够?检验 上目标 、候选 ,并解释定理需要的零点数。)
解答 · 答案
候选误差为 ,端点极值为一和负一,但候选范数误差为一,而零多项式完全准确。两个点只强迫竞争差有一个零点,非零一次多项式可以做到。一次空间需要三个交错极值点,强迫两个互异零点才产生矛盾。