《诗》云：“他人有心，予忖度之。”夫子之谓也。

这次谈的是插值。

做任何研究工作，总是要抓住主要矛盾。想要研究某种现象，就要先看看它如何随着某个因素变化。这个因素不会是随便瞎蒙的，更可能是根据以前的经验或者初期的观察而猜测的，最常见的因素是时间或者距离。某种现象（用$y$来衡量其大小、表示其数量）随某个因素（用$x$来表示）的变化关系就是函数$y=f(x)$。

我们研究的现象，通常是连续地依赖于其主导因素的。也就是说，诱因的差别越小（$x$的差别$\Delta x$越小），结果的差别也就越小（$y$的差别$\Delta y$越小）。数学分析里碰到的那些怪了吧唧的函数，其实都是用来对付“杠精”的——处处不连续的函数（例如，在有理数上等于1、在无理数上等于0的函数），几乎处处不连续的函数（例如，在有理数$p/q$上等于$1/q$、在无理数上等于0的函数），处处连续、但处处不可微的函数（例子就不举了）。“杠精”确实需要对付，但是在开始的时候，我们没必要用主要精力处理这些细枝末节，smilence足矣。

想要了解某件事$y$，先要在一些位置$x$处测量$y$，也就是说，在$x_1 < x_2<\cdots < x_i<\cdots < x_n$处的各个$y_i$，这就是采样。采样的数目$n$总是有限的：至少是1，最大值则取决于你耐心的程度和钱包的厚度。你只能测量有限个位置上的数值，但是你可能需要知道更多位置（或者说任意位置$x$）上的数值，这就是插值问题。怎么解决插值问题呢？很简单，猜一个就是了——不是瞎猜而是有根据的猜。

最简单的猜法是“铁路警察，各管一段”。对于任意的$x$，看看那个测量位置$x_i$离得最近，就用哪个$y_i$来表示$y$的数值。这种方法太独裁了，猜出来的函数$y$就是一系列的台阶、看起来磕磕巴巴的样子。

更好一些的猜法引入了民主。对于任意的$x$，找到离得最近的两个位置$x_i<x<x_{i+1}$，听取双方的意见，根据“杠杆法”得到相应的

$y=[(x_{i+1}-x)y_i+(x-x_i)y_{i+1}]/(x_{i+1}-x_i)$。这种方法猜出来的函数$y$就是一系列的斜坡，虽然倾斜的程度有差别，但是至少不会绊人了。类似的，你还可以采用更大程度的民主，听听离$x$最近的三个、四个乃至更多位置的意见，猜出来的函数$y$也会更好看一些。

更一般性地讨论一下插值问题。我们有了在$x_1 < x_2<\cdots < x_i<\cdots < x_n$处的各个值$y_i$，想要得到任意位置$x$处的$y$值。“民主集中制”是一种好办法：$x$依赖于所有的$x_i$，但是靠得越近的$x_i$，发言权越大。

$x=x_i$的时候，选择$y=y_i$，因为我们不希望白瞎了$x_i$这次测量。为了满足这个要求，考虑一个简单的函数$w'(x)=w(x)/(x-x_i)$，其中，$w(x)=(x-x_1)(x-x_2)\cdots (x-x_n)$。显然，对于不是$x_i$的取值点，$w'(x)$等于零，采用适当的归一化，就可以用$y_i(x)=y_iw'(x)/w'(x_i)$来表示插值函数了。对于每一个$i$，都做这样的处理，就可以得到整个范围内的插值函数$y(x)=\sum _i y_i(x)$，其中，$i$是对所有的取样点$x_i$求和。这就是拉格朗日插值法。如果有$n+1$个取样点，拉格朗日插值函数就是一个$n$阶多项式。

如果取样的时候，不仅测量了$x_i$处的值$y_i$，还测量了该处的导数值$y'_i$，那么，选择插值函数的时候，就不再是$(x-x_i)$的连乘形式了，而是$(x-x_i)^2$的连乘形式。这就是厄密插值法，选取$n+1$个取样点，厄密插值函数就是一个$2n+1$阶多项式。

前面说的插值方法是广种薄收（在很多位置上取样，然后再猜），还有一种方法是精耕细作，在一个位置上测量很多数据：不仅有该点的数值，还有该点的一阶导数、二阶导数乃至$n$阶导数，然后用泰勒公式来推算其余位置的函数值。这种方法在原则上是可行的，但是执行起来可能更难——导数不容易测量，高阶导数就更难了。牛顿提供了一种估计各阶导数的方法，仍然是测量$n$个取样点的数值，然后用“差商”来近似“微分”，用“高阶差商”来近似“高阶微分”，这就是牛顿插值法。与拉格朗日方法相比，牛顿法还有节省运算次数的优点，具体细节就不展开讨论了。

这些插值方法都很简单，但是，当$n$很大的时候，就可能出现“过度民主化”的问题。每个取样点上的插值都没问题，但是取样点之间的插值，可能跟实际情况偏离得很大，特别是在取样区间的两头（靠近$x_1$或$x_n$的位置），这就是所谓的龙格现象。原因也很简单。以等间距取样（$\Delta x=\delta $）的拉格朗日插值法为例，在整个取样区间的中间部分，差别大致是$[(n/2)!\delta ^{n/2}]^2$，而在取样区间的两侧，差别则是$n!\delta ^n$——龙格现象的原因就是$[(n/2)!]^2\ll n!$。

所以，采样点不能取得太多。如果真的需要了解很大范围里的变化情况，也应该分而治之，把大范围切割为很多小区间，然后在每个小区间里插值。在相邻的小区间，分段的插值函数要想办法保证连续甚至可微。这就是“分段低次插值法”。

既然已经分段了，那么，在小区间里，最好是怎么方便怎么来了——通常采用“样条函数”。样条函数是分段的多项式，而各段多项式之间具有适当的连接性质，从而保证“样条曲线”不但光滑优美而且转折如意。

关于插值，大概就讲这么多了。需要补充的是，上面这些插值方法都是内插法，需要猜测插值的位置都在取样范围以内。超出取样范围的猜测（外插法），除非离采样区间很近，基本上都不靠谱——只有万不得已的时候才会考虑。

至于说，在确定的采样区间里，如何选择具体的采样点，那就是另外一个故事了——请看下回“计算方法之弱水三千”。