CS205A Lecture 14 Interpolation

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

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

Chapter 11 插值

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

单变量插值

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

这里假设

多项式插值

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

得到如下线性系统:

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

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

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

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

所以

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

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

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

这里补充

不难看出我们有

所以如果我们假设

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

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

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

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

分段插值

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

定义11.1

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

左图对应了分段常数插值,右图对应了分段线性插值:

  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}]$所在的区间,定义

多变量插值

此时的函数为

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

Voronoi cells

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

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

然后计算

来看一个具体例子:

Barycentric Interpolation

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

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

本文标题:CS205A Lecture 14 Interpolation

文章作者:Doraemonzzz

发布时间:2019年04月30日 - 20:08:00

最后更新:2019年04月30日 - 20:16:08

原始链接:http://doraemonzzz.com/2019/04/30/CS205A Lecture 14 Interpolation/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。