CS205A Lecture 14 Interpolation

课程主页：https://graphics.stanford.edu/courses/cs205a-13-fall/schedule.html

这次回顾第十三讲，这一讲介绍了插值。

Chapter 11 插值

之前讨论了函数求根以及极值的问题，但是在实际中函数常常未知，所以就要根据已有的值估计未知的值，这就是这一讲插值所需要解决的问题。

单变量插值

首先讨论单变量的插值问题，首先给出问题的形式：

$$f:\mathbb R\to \mathbb R 是单变量函数，已知(x_i,y_i),i=1,\ldots ,k,y_i =f(x_i)\\ 计算f(x), x\neq x_i ,i=1,\ldots ,k$$

这里假设

$$x_1<x_2<\ldots < x_k$$

多项式插值

首先考虑多项式插值，我们知道$k$个点可以唯一确定一个$k-1​$次多项式，所以设

$$f(x)= a_{0}+a_{1} x+a_{2} x^{2}+\cdots+a_{k-1} x^{k-1}$$

由

$$f(x_i)=y_i$$

得到如下线性系统：

$$\left( \begin{array}{ccccc} {1} & {x_{1}} & {x_{1}^{2}} & {\cdots} & {x_{1}^{k-1}} \\ {1} & {x_{2}} & {x_{2}^{2}} & {\cdots} & {x_{2}^{k-1}} \\ {\vdots} & {\vdots} & {\vdots} & {\cdots} & {\vdots} \\ {1} & {x_{k}} & {x_{k}^{2}} & {\cdots} & {x_{k}^{k-1}} \end{array}\right) \left( \begin{array}{c} {a_{0}} \\ {a_{1}} \\ {\vdots} \\ {a_{k-1}} \end{array}\right)= \left( \begin{array}{c}{y_{1}} \\ {y_{2}} \\ {\vdots} \\ {y_{k}}\end{array}\right)$$

系数矩阵对应的行列式被称为范德蒙行列式，所以求解上述方程即可。

另一种视角是将$f(x)$视为一组基构成的函数，多项式插值中，我们的基为

$$\left\{1, x, x^{2}, \ldots, x^{k-1}\right\}$$

在插值问题中，我们可以选择拉格朗日插值多项式作为基：

$$\phi_{i}(x) = \frac{\prod_{j \neq i}\left(x-x_{j}\right)}{\prod_{j \neq i}\left(x_{i}-x_{j}\right)}$$

其中$\phi_i(x)​$满足

$$\phi_{i}\left(x_{\ell}\right)= \left\{\begin{array}{ll} {1} & {\ell=i} \\ {0} & {\text {其他}} \end{array}\right.$$

所以

$$f(x) = \sum_{i} y_{i} \phi_{i}(x)$$

但是这个方法有如下两个问题：

1. 每次计算一个插值点需要的时间为$O(k^2)$，而计算系数后求一个插值点只需要$O(k)$的时间。
2. 如果存在$x_i\approx x_j$，那么$\phi_i(x )\to \infty$，这就会产生数值问题。

还有常用的多项式基为牛顿多项式：

$$\psi_{i}(x)=\prod_{j=1}^{i-1}\left(x-x_{j}\right)$$

这里补充

$$\psi_1 (x)=1$$

不难看出我们有

$$\psi_{i}\left(x_{\ell}\right)=0,\ell <i$$

所以如果我们假设

$$f(x)=\sum_{i} c_{i} \psi_{i}(x)$$

那么令$x=x_i$可以得到如下等式：

$$\begin{aligned} f\left(x_{1}\right) &=c_{1} \psi_{1}\left(x_{1}\right) \\ f\left(x_{2}\right) &=c_{1} \psi_{1}\left(x_{2}\right)+c_{2} \psi_{2}\left(x_{2}\right) \\ f\left(x_{3}\right) &=c_{1} \psi_{1}\left(x_{3}\right)+c_{2} \psi_{2}\left(x_{3}\right)+c_{3} \psi_{3}\left(x_{3}\right) \\ &\vdots \end{aligned}$$

即

$$\left( \begin{array}{ccccc} {\psi_{1}\left(x_{1}\right)} & {0} & {0} & {\cdots} & {0} \\ {\psi_{1}\left(x_{2}\right)} & {\psi_{2}\left(x_{2}\right)} & {0} & {\cdots} & {0} \\ {\psi_{1}\left(x_{3}\right)} & {\psi_{2}\left(x_{3}\right)} & {\psi_{3}\left(x_{3}\right)} & {\cdots} & {0} \\ {\vdots} & {\vdots} & {\vdots} & {\cdots} & {\vdots} \\ {\psi_{1}\left(x_{k}\right)} & {\psi_{2}\left(x_{k}\right)} & {\psi_{3}\left(x_{k}\right)} & {\cdots} & {\psi_{k}\left(x_{k}\right)}\end{array}\right) \left( \begin{array}{c}{c_{1}} \\ {c_{2}} \\c_3\\ {\vdots} \\ {c_{k}}\end{array}\right) =\left( \begin{array}{c}{y_{1}} \\ {y_{2}} \\y_3\\ {\vdots} \\ {y_{k}} \end{array}\right)$$

最后再介绍有理分式插值：

$$f(x)=\frac{p_{0}+p_{1} x+p_{2} x^{2}+\cdots+p_{m} x^{m}}{q_{0}+q_{1} x+q_{2} x^{2}+\cdots+q_{n} x^{n}}$$

令$x=x_i$得到如下方程：

$$y_{i}\left(q_{0}+q_{1} x_{i}+\cdots+q_{n} x_{i}^{n}\right)=p_{0}+p_{1} x_{i}+\cdots+p_{m} x_{i}^{m}$$

求解该线性方程组即可，但是注意，有理分式插值会产生一些问题，具体例子见讲义。

分段插值

多项式插值的一个问题在于局部改变有全局影响，于是就产生了分段插值的想法，首先给出如下定义：

定义11.1

$$称函数g(x)有紧支集，如果存在C\in \mathbb R,\\ 使得\forall x, |x|>C，g(x)=0$$

将紧支集应用在插值问题中就是使用分段差值：

左图对应了分段常数插值，右图对应了分段线性插值：

1. 分段常数插值：$\forall x$，找到$x_i$最小化$|x-x_i|$，定义$f(x)=y_i$

2. 分段线性插值：如果$xx_k$，定义$f(x)=y_k$；其余情形找到$x\in [x_i,x_{i+1}]$所在的区间，定义

   $$f(x)=y_{i+1} \cdot \frac{x-x_{i}}{x_{i+1}-x_{i}}+y_{i} \cdot\left(1-\frac{x-x_{i}}{x_{i+1}-x_{i}}\right)$$

多变量插值

此时的函数为

$$f:\mathbb R^n \to \mathbb R$$

多变量插值比较常用的为最邻近法插值，解释之前，给出如下定义：

Voronoi cells

$$给定点集S=\left\{\vec{x}_{1}, \vec{x}_{2}, \ldots, \vec{x}_{k}\right\} \subseteq \mathbb{R}^{n},关于\vec x_i的\text{Voronoi cell}定义为\\ V_{i}=\left\{\vec{x} :\left\|\vec{x}-\vec{x}_{i}\right\|_{2}<\left\|\vec{x}-\vec{x}_{j}\right\|_{2} \text { for all } j \neq i\right\}\\ 即距离\vec x_i最近的点构成的集合$$

如果$x\in V_i$，取$f(x)=y_i$。

还有一种常用的方法为Barycentric Interpolation，即找到$a_i$，使得

$$\begin{aligned} \sum_{i} a_{i} \vec{x}_{i} &=\vec{x} \\ \sum_{i} a_{i} &=1 \end{aligned}$$

然后计算

$$f(\vec{x})=\sum_{i} a_{i}(\vec{x}) y_{i}$$

来看一个具体例子：

Barycentric Interpolation

$$\begin{array}{l}{f(0,0)=1} \\ {f(0,1)=-3} \\ {f(1,0)=5} \\ {f(1,1)=-11}\end{array}$$

为了计算$f(\frac 1 4 ,\frac 12)$，可以使用如下方法：

$$\begin{aligned} f\left(\frac{1}{4}, 0\right) &=\frac{3}{4} f(0,0)+\frac{1}{4} f(1,0)=2 \\ f\left(\frac{1}{4}, 1\right) &=\frac{3}{4} f(0,1)+\frac{1}{4} f(1,1)=-5\\ f\left(\frac{1}{4}, \frac{1}{2}\right)&=\frac{1}{2} f\left(\frac{1}{4}, 0\right)+\frac{1}{2} f\left(\frac{1}{4}, 1\right)=-\frac{3}{2} \end{aligned}$$

插值理论介绍的比较简洁，这里略过。