切比雪夫和 minimax 逼近

Minimax 逼近旨在寻找最大误差尽可能小的逼近函数，从而提供统一的精度保证；切比雪夫多项式和 Remez 算法是计算和理解这种最佳一致逼近的核心工具。

Definition

Minimax 逼近是确定在定义域上使最大绝对误差最小的逼近函数，而切比雪夫逼近是围绕切比雪夫多项式建立的理论和方法体系，它能实现或非常接近这种最佳一致拟合。

Scope

本主题涵盖最大范数下的最佳一致（minimax）逼近、切比雪夫等振荡定理、切比雪夫多项式和切比雪夫插值的作用及其近最优性，以及用于计算 minimax 多项式和有理逼近的 Remez 交换算法。

Core questions

• 最佳一致逼近的特征是什么？为什么它是唯一的？
• 为什么切比雪夫多项式在近最优多项式逼近中居于核心地位？
• Remez 算法如何迭代计算真正的 minimax 逼近？
• Minimax 拟合何时优于最小二乘拟合？其计算成本如何？

Key theories

等振荡定理

一个次数至多为 n 的多项式是连续函数的最佳一致逼近，当且仅当其误差在至少 n+2 个点上以交替符号达到其最大幅值；这一特征使得最佳逼近是唯一的且可计算的。

切比雪夫逼近的近最优性

在切比雪夫点处进行切比雪夫多项式插值或展开所得到的逼近，其最大误差与最佳可能误差之间仅相差一个小的、对数增长的因子，因此切比雪夫方法是真实 minimax 拟合的一种廉价替代方案。

Remez 交换算法

Remez 算法迭代调整候选参考点集，以强制满足等振荡条件，从而快速收敛到精确的最佳多项式或有理 minimax 逼近。

Mechanisms

Remez 算法首先猜测等振荡点，然后求解一个小型线性系统，使误差在该参考集上以相等幅度和交替符号进行等振荡，接着将参考点重新定位到新的误差极值点并重复；该过程以二次收敛速度收敛到 minimax 解。切比雪夫逼近则通过切比雪夫多项式展开函数——可通过快速傅里叶变换高效计算——利用其最小上确界范数特性，无需迭代即可获得接近最佳的精度。

Clinical relevance

Minimax 和切比雪夫逼近用于构建数学库中的基本函数例程，设计具有均匀频率响应误差的数字滤波器，以及为嵌入式和实时计算构建紧凑、均匀精确的逼近，在这些应用中，最坏情况误差界比平均误差更重要。

History

该理论起源于切比雪夫在19世纪对最佳一致逼近和等振荡原理的研究；Evgeny Remez 在20世纪30年代设计了他的交换算法，而基于切比雪夫的计算在20世纪后期成为数值软件的实用支柱，特别是通过现代系统中无需自动微分的切比雪夫技术。

Key figures

• Pafnuty Chebyshev
• Evgeny Remez
• Lloyd N. Trefethen

Seminal works

• trefethen2013
• powell1981
• cheney1966

Frequently asked questions

等振荡的直观含义是什么？

它意味着最佳一致逼近会分配其误差，使得误差曲线在足够多的点上反复触及其最大高度，并在正负之间交替。任何其他候选方案都可以改进，因此这种平衡的误差模式标志着最优性。

为什么使用切比雪夫插值而不是精确的 minimax 多项式？

计算精确的 minimax 多项式需要迭代的 Remez 算法，而切比雪夫插值快速且非迭代，并且其误差与最佳可能误差之间仅相差一个小的因子，因此它通常是实际的选择。