GAMES001课程笔记05-插值&拟合

这个系列是GAMES001-图形学中的数学(GAMES 001: Mathematics in Computer Graphics)的同步课程笔记。课程旨在总结归纳图形学学习过程中重要的数学概念、理论和方法，并将以索引的形式在每一章节中穿插讲解该数学专题在图形学中的应用。本课程既可以作为GAMES系列其它课程学习的基础或「手册」，也可以作为站在不一样的视角复习图形学知识的平台。本节主要介绍插值与拟合技术。

插值(interpolation)与拟合(fitting)是数值分析中常用的两种技术，它们在处理数据和函数逼近方面起着重要作用。尽管在某些情况下这两个术语可以互换，但它们在数学上有着明确的区别：

插值是通过已知数据点来构建一个函数，同时要求这个函数一定要通过每个采样点。
拟合是指通过某种函数形式来逼近已知数据点，但并不要求通过每个采样点。

插值

线性插值

最简单的插值方法是线性插值(linear interpolation)。对于平面上的两个点\((x_0, y_0)\)和\((x_1, y_1)\)，我们可以用一个线段来连接它们。这条线段的参数方程可以表示为：

\[y = (1 - t) y_0 + t y_1\]

其中\(t = \frac{x - x_0}{x_1 - x_0} \in [0, 1]\)表示线段上的任一点。当有平面上的多个点时，可以通过分段插值的方法来得到连接它们的折线。

显然线性插值得到的曲线仅仅是连续的，它在每段折线的交点处会发生斜率的突变，换句话说这条曲线的导数是不连续的。这种函数值连续但导数不连续的情况称为C0连续(C0 continuity)。在很多应用场景中我们都希望插值得到的曲线有着较好的连续性，因此这种情况下线性插值并不是一个很好的选择。

多项式插值

在线性插值的基础上我们可以使用更高次的函数来进行插值。对于平面上的三个点，我们可以使用一个二次函数来进行插值，这样的插值方法称为二次插值。

对于更一般的情况，我们可以使用多项式插值(polynomial interpolation)来得到插值曲线。具体来说，对于平面上的n+1个点，我们使用一个关于\(x\)的n次多项式来进行插值：

\[y(x) = a_0 + a_1 x + \cdots + a_n x^n\]

可以证明，插值函数可以写成Lagrange多项式(Lagrange polynomial)求和的形式：

\[y = \sum_{j=0}^n y_j \prod_{i, i \neq j} \frac{x - x_i}{x_j - x_i}\]

由于使用了n次多项式，多项式插值得到的曲线是n-1阶连续的。

样条插值

多项式插值的一个问题在于尽管曲线是处处光滑的，但它很容易产生大量的震荡。这样的现象称为龙格现象(Runge’s phenomenon)。

龙格现象可以使用样条插值(spline interpolation)来进行处理，它的基本思想是使用多段低阶的多项式来进行插值。

二次样条插值

以二次样条插值(quadratic spline interpolation)为例，对于n+1个数据点我们可以用n段二次曲线来进行插值，其中每段曲线对应3个参数\((a_i, b_i, c_i)\)。根据插值条件，第i个区间的曲线经过数据点\((x_i, y_i)\)和\((x_{i+1}, y_{i+1})\)，这样可以导出2n个方程组：

\[\begin{cases} \begin{aligned} a_i x_i^2 + b_i x_i + c_i &= y_i \\ a_i x_{i+1}^2 + b_i x_{i+1} + c_i &= y_{i+1} \end{aligned} \end{cases}\]

同时我们要求数据点两侧的导数相同，得到n-1个方程：

\[2 a_{i-1} x_i + b_{i-1} x_i = 2 a_i x_i + b_i\]

最后可以指定第一段为线性函数，得到1个方程：

\[a_0 = 0\]

这样就得到了关于全部系数的线性方程组，求解后就得到了所有的二次曲线。

显然二次样条插值的结果是C1连续的，我们无法保证曲线的二阶导连续。同时需要注意的是二次样条插值没有显式解，我们需要通过求解矩阵方程来得到分段二次曲线的参数，因此它的求解效率和多项式插值相比要低一些。此外，二次样条插值曲线的形状与所有数据点都相关，改变任意一个采样点的位置都可能会影响全局的插值结果。

三次样条插值

类似二次样条插值的思想，我们可以使用分段三次函数来对数据点进行插值，这样的插值曲线可以保证是C2连续的。同样的，三次样条插值也需要求解矩阵方程，插值曲线也是牵一发而动全身的。

三次Hermite插值

我们可以放弃二阶导数的连续性来获得插值曲线更好的局部性。三次Hermite插值就是这样的一种方法，每个插值段都可以用一个显式的三次多项式来表示，而不需要求解矩阵方程。同时，三次Hermite插值会通过在每个插值段的端点处指定函数值和一阶导数(斜率)，从而确定唯一的插值多项式。通过人为调整端点处的斜率，可以直接控制插值曲线的走向和形状，从而实现更好的局部性。