第6章：插值、逼近与傅里叶方法

插值条件

n+1 个不同节点确定唯一次数至多 n 的插值多项式。唯一性证明是：两候选之差有 n+1 个不同零点，但次数至多 n，只能恒零。

Lagrange 表达式为 $p(x)=\sum_i f(x_i)\ell_i(x)$ ，其中 $\ell_i(x_j)=\delta_{ij}$ 。实际多次求值常采用重心形式，避免直接展开高次幂系数所带来的成本和误差。

足够光滑时，插值误差可写为

f(x)-p_n(x)=\frac{f^{(n+1)}(\xi)}{(n+1)!}\prod_{i=0}^n(x-x_i).

提高 n 同时改变高阶导数和节点乘积，不保证误差单调下降。Runge 现象表明某些光滑函数在等距节点上高次插值可在端点附近恶化。

Chebyshev 节点在端点较密，改善节点多项式等性质。它缓解一类问题，不表示任意不光滑函数都能获得指数收敛。

样条用低次多项式拼接，施加连续性条件。三次样条常要求函数、一阶和二阶导数在内节点连续，边界条件如自然边界或指定导数还需另给。

插值精确通过数据点，最小二乘逼近允许偏差以减少噪声影响。测量有噪声时，强行提高阶数穿过所有点可能只是在拟合噪声。

离散傅里叶变换可写为

X_k=\sum_{j=0}^{N-1}x_j e^{-2\pi i jk/N}.

FFT 利用结构把计算从直接的 $O(N^2)$ 降为常见情况下的 $O(N\log N)$ ，计算的是同一 DFT，不是换一种近似目标。

有限采样无法区分所有连续频率。混叠由采样引入，频谱泄漏与有限窗口及边界延拓有关；提高 FFT 算法速度不消除这些建模误差。