CAGD 学习笔记 | 插值和拟合
这一系列笔记是笔者在准备 CAGD 期末考试期间所做的记录. 笔记主要内容来自陈仁杰教授于 2022 年秋季在中国科学技术大学开设的《计算机辅助几何设计》课程的课件, 笔者补全了部分推导过程, 并按照自己的理解调整了顺序, 增加了一些内容.
写这份笔记的主要目的是加深笔者自己的理解. 如果这份笔记对您有所帮助, 那再好不过; 如果您发现其中有错误或是逻辑不通畅的地方, 希望您能为我指出.
插值和拟合都是根据一组数据构造一个近似函数, 但二者近似的要求. 插值是指函数在多个离散点上的函数值或导数信息, 要求近似函数经过所已知的所有数据点. 拟合是指函数在多个离散点上的函数值或导数信息, 不要求近似函数经过所有数据点, 而是要求它能较好地反映数据变化规律, 通常使用最小二乘法或其他优化方法来求解.
插值
本文中只介绍要求插值函数经过数据点的情形, 即 Lagrange 插值. 若要求插值函数在某一点处的导数满足某种条件, 请搜索 Hermite 插值, 这是 Newton 多项式插值的推广.
问题背景
空间中存在一组数据点, 我们希望求一条光滑的曲线, 使得它恰好经过这些点.
问题设定
对于一组插值点 $(x_i, \mathbf{y}_i), 1 \le i \le n, x_i \in \mathbb{R}, \mathbf{y}_i \in \mathbb{R}^d$, 求一个函数 $f: \mathbb{R} \rightarrow \mathbb{R}^d$ 使得 $f(x_i)=y_i$.
构造一组光滑的基函数 $\{b_j: \mathbb{R} \rightarrow \mathbb{R}, b_j \in C(\mathbb{R}), 1 \le j \le m\}$ , 例如多项式基函数 $b_j (x) = x^{j-1}$ 和径向基函数 $b_j (x) = \frac{1}{|x-x_i|^p + d}$. 设 $f$ 在这一组基函数所张成的线性空间中, 即 $f$ 是它们的的线性组合: $f(x) = \sum_{j=1}^{m} c_j b_j(x), c_j \in \mathbb{R}^d$, 则有
$$ y_i = f(x_i) = \sum_{j=1}^{m} c_j b_j(x) = \left( c_1, \cdots, c_m \right) \left( \begin{matrix} b_1(x_i) \\ \vdots \\ b_m(x_i) \end{matrix} \right), 1 \le i \le n $$问题求解
方法1 求解线性方程组
$$ \left( y_1, \cdots, y_n \right) = \left( c_1, \cdots, c_m \right) \left( \begin{matrix} b_1(x_1) & \cdots & b_1(x_n) \\ \vdots & \ddots & \vdots \\ b_m(x_1) & \cdots & b_m(x_n) \end{matrix} \right) =: \left( c_1, \cdots, c_m \right) \mathbf{B} $$则问题为求解 $\left(c_1, \cdots, c_m\right)$ 的值.
要使式 (2) 总有解, 只需 $\text{rank} \mathbf{B} = n$, 不妨令 $m=n$, 再选取适当的基函数即可. 当 $m > n$ 时这一问题能给出多个解.
这一方法的问题在于, 矩阵 $\mathbf{B}$ 往往是稠密矩阵, 会占用很大的内存空间. 此外, 当基函数个数较多时, 矩阵 $\mathbf{B}$ 的条件数会很大, 此时难以进行求解. 综合以上两点, 这一方法不具备实用性.
方法2 用 Lagrange 插值法构造基函数
$$ b_j(x_i) = \begin{cases} 1, & i = j \\ 0, & i \neq j \end{cases} $$则 $f(x) = \sum_{j = 1}^{n} y_j b_j(x)$ 就是满足条件的插值函数.
$$ l_j (x) = \frac{\prod_{i = 1, i \neq j}^n (x - x_i)}{\prod_{i = 1, i \neq j}^n (x_j - x_i)}, j = 1, \dots, n $$容易证明, Lagrange 插值法和求解线性方程组构造的插值函数是相同的.
Runge 现象
均匀节点上的多项式插值函数会在区间边缘出现震荡, 并且在插值点增多时误差会趋于无穷大. 这一问题被称为 Runge 现象. 这一现象的详细数学解释可参见 https://numanal.com/runge-mathematical-proof/. 值得注意的是, 使用 Chebyshev 节点进行多项式插值可以保证插值函数一致收敛到被插值函数, 但这不是
拟合
问题背景
在某些情况下, 数据点包含噪声, 因此精确地插值每个数据点会造成过拟合. 同时为了快速计算, 避免 Runge 现象, 我们希望采用更少的基函数来拟合数据点.
问题设定
本文中只介绍最小二乘拟合, 这是要求拟合函数和原始数据的均方误差最小.
对于一组数据点 $(x_i, \mathbf{y}_i), 1 \le i \le n, x_i \in \mathbb{R}, \mathbf{y}_i \in \mathbb{R}^d$, 求一个函数 $f: \mathbb{R} \rightarrow \mathbb{R}^d$, 使得 $\sum_{i=1}^n\|f(x_i)-y_i\|^2$ 最小.
拟合函数 $f$ 的定义与上一节中相同, 但基函数的个数会更少, 即我们有 $m < n$.
问题求解
$$ \begin{aligned} \sum_{i=1}^n(f(x_i)-y_i)^2 & = \sum_{i=1}^n (\sum_{j=1}^m c_j b_j(x_i) - y_i)^2 \\ & = \|\mathbf{cB} - \mathbf{y}\|^2 \\ & = \mathbf{c B B^\top c^\top} - 2 \mathbf{c B y^\top} + \mathbf{y y^\top} \\ & = \|\mathbf{c B} - \mathbf{y B^\top} (\mathbf{B B^\top})^{-1} \mathbf{B}\|^2 - \mathbf{y B^\top} (\mathbf{B B^\top})^{-1} \mathbf{B B^\top} ((\mathbf{B B^\top})^{-1})^\top \mathbf{B y^\top} + \mathbf{y y^\top} \\ & = \|(\mathbf{c} - \mathbf{y B^\top} (\mathbf{B B^\top})^{-1}) \mathbf{B}\|^2 - \mathbf{y B^\top} ((\mathbf{B B^\top})^{-1})^\top \mathbf{B y^\top} + \mathbf{y y^\top} \end{aligned} $$$$ \underset{\mathbf{c}}{\text{argmin}} \sum_{i=1}^n(f(x_i)-y_i)^2 = \mathbf{y B^\top} (\mathbf{B B^\top})^{-1} $$注意到, 若 $m = n$ 即基函数个数等于数据点个数, 我们有 $\mathbf{y B^\top} (\mathbf{B B^\top})^{-1} = \mathbf{y B^\top} \left( \mathbf{B} ^\top\right)^{-1} \mathbf{B}^{-1} = \mathbf{y} \mathbf{B}^{-1}$, 这就是式 (2) 的解, 也就是说这时拟合问题就退化为插值问题.