数值分析

状态：已有 FFT 简介，其余主题待补充。

内容规划

长度为 \(N\) 的离散傅里叶变换为

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

直接计算所有 \(X_k\) 需要 \(O(N^2)\) 次运算。若 \(N\) 为偶数，把输入按奇偶下标拆开：

\[ X_k =\sum_{r=0}^{N/2-1}x_{2r}\omega_{N/2}^{rk} +\omega_N^k\sum_{r=0}^{N/2-1}x_{2r+1}\omega_{N/2}^{rk}. \]

右侧是两个长度 \(N/2\) 的 DFT。利用 \(X_{k+N/2}\) 与 \(X_k\) 共享这两个子问题，得到递归

\[ T(N)=2T(N/2)+O(N), \]

因而

\[ T(N)=O(N\log N). \]

FFT 改变的是计算同一个 DFT 的方式，不是新的变换。它也不等同于压缩感知：FFT 利用 Fourier 矩阵的递归结构加速完整变换；压缩感知利用信号在某个基下的稀疏性，从少量测量恢复信号。

给定节点 \(x_0,\ldots,x_n\)，Lagrange 插值基函数为

\[ \ell_i(x)=\prod_{j\ne i}\frac{x-x_j}{x_i-x_j}, \qquad p_n(x)=\sum_{i=0}^n f(x_i)\ell_i(x). \]

若 \(f\) 足够光滑，插值余项写成

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

增加全局多项式次数不保证误差处处下降；等距节点上的高次插值可能在端点附近出现 Runge 振荡。有限元采用“划分网格 + 每个单元使用低阶多项式”，正是把全局高次逼近改成局部、稀疏且可控制的逼近。

这也说明数值分析里必须分开两个选择：

二者可以组合，但误差、条件数和计算量的变化并不相同。

对权函数 \(w(x)\)，若 \(p_n\) 是 \(n\) 次正交多项式，以其零点 \(x_i\) 作为求积节点，可以构造

\[ \int_a^b f(x)w(x)\,dx \approx \sum_{i=1}^n\omega_i f(x_i). \]

合适的 Gauss 求积对次数不超过 \(2n-1\) 的多项式精确。有限元装配需要在每个单元上反复计算积分，因此通常先把物理单元映射到参考单元，再使用固定求积点和权重。

“求积公式阶数高”不等于整个 PDE 数值解同阶：总误差还受几何近似、有限元空间、网格质量和线性系统求解精度影响。

工业仿真中的误差可以分成几层：

\[ \text{总误差} \lesssim \text{几何误差} +\text{离散误差} +\text{代数求解误差} +\text{舍入误差}. \]

若离散系统为 \(Ax=b\)，相对扰动的放大与条件数

\[ \kappa(A)=\|A\|\,\|A^{-1}\| \]

有关。网格加密虽然减小离散误差，却可能增加未知量并恶化条件数，因此需要预条件、合适的停止准则和误差估计，而不是一味把线性系统解到机器精度。

离散化并不会自动修复连续问题的不适定性。若积分算子或离散矩阵存在很小的奇异值，直接求逆会放大数据噪声。截断 SVD 舍弃过小奇异值，Tikhonov 正则化则求解

\[ \min_u\ \|Ku-f^\delta\|_2^2+\lambda\|Lu\|_2^2. \]

这里 \(\lambda\) 平衡数据拟合与解的稳定性。正则化参数、离散尺度和噪声水平需要协同选择；把网格无限加密或把残差压到极小，反而可能开始拟合噪声。

进一步的有限元、逆问题和工程背景分别见有限元方法与逆问题和高维计算。