CAGD 学习笔记 | 01 插值和拟合

写在前面

这一系列笔记是笔者在准备 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 求解线性方程组

式 (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, 1 \le j \le n$, 有

$$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)$ 就是满足条件的插值函数.

对于多项式函数空间, 可以采用 Lagrange 插值法构造这样的基函数

$$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$.

问题求解

不妨设维度 $d=1$. 注意到若 $\mathbf{B}$ 行满秩, 则 $\mathbf{B B^\top}$ 可逆, 因而有

$$\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) 的解, 也就是说这时拟合问题就退化为插值问题.