一. 介绍

经常在某乎看见此类问题：“数字找规律题，数字1、2、4、6、8、( )，请问括号内应填几？”。我觉得这个问题很2B，不知道是哪个傻叉250问的。

那我在括号里随手填个250，对不对？

对！没毛病！

原因：假设整个数列通项符合某个 f(x) ，其中 x 从0开始计数，代入第0-5项可以找出这个通项公式为：

如果继续填下一个：1、2、4、6、8、250、( )

嘿，那我还可以填：114514

原因：

这种不讲武德的找规律填数字方法叫“多项式插值”。理论上给定n+1个x值不同的点，都可以找到一个对应的n次多项式，它可以通过所有这些点。

比如上面的找规律问题，我把它转换成了两个插值问题：求过点(0,1)、(1,2)、(2,4)、(3,6)、(4,8)、(5,250) 的5次多项式，以及求过点(0,1)、(1,2)、(2,4)、(3,6)、(4,8)、(5,250)、(6,114514) 的6次多项式。

本文将介绍两种通过已知点求多项式的方法。

二.多项式唯一

首先有个结论要了解：有n+1个点，他们的x值各不相同。那么过所有这些点的n次多项式存在且唯一。

左侧的矩阵通常叫作范德蒙矩阵（Matrice de Vandermonde），它的行列式不为零（因为xi各不相同），这也就证明了唯一性定理：存在唯一的一个插值多项式。

所以对于同一系列的点，用拉格朗日插值法和牛顿插值法得到的多项式完全一致。

三. 拉格朗日插值法

先说插值法。插值法是做什么用的？插值法是通过已知点，求过这些点的未知函数的数学方法。

所以我们输入的，是一堆点，也就是一堆x和一堆y。

我们想要得到的，是一个函数，这个函数能完美的通过这一堆x和这一堆y。

那你要怎么解决这个问题呢？说白了很简单，就是一个开开关的问题。

这就是拉格朗日插值法的想法。

假设有三个点，可以通过“开关”的方式构造通过这三个点的二次函数P(x):

这个三个开关有什么性质呢？它们的值只能是0或1。

    1. 将x1带入P(x)，开关1的值为1，开关2和开关3的值为0。

         这样就保证P(x)了过第一个点。

    2. 将x2带入P(x)，开关2的值为1，开关1和开关3的值为0。

         保证P(x)过第二个点。

    3. 将x3带入P(x)，开关3的值为1，开关1和开关2的值为0。

         保证P(x)过第三个点。

那么开关的状态是开（值为1）还是关（值为0），取决于什么呢？带入的x值。

——任何数除自己都是1，零除任何数都是0。

以开关2为例，可以这样构造：

            

        我们会发现，带入x=x2，分子和分母的值相同，即开关为1。如果带入x1或x3，则分子为0，即开关为0。

同理可得开关1和开关3的表达式。

进过简单类推，我们就得到了拉格朗日插值法（Interpolation de Lagrange）的公式。

把它翻译成人话：

，其中任一开关i的表达式是分式，分子为：该开关对应的x值减其他非该点的x值，全部乘起来：

  

这样带入非该点的x值时，分子为0，开关的值为0。

分母则把上式中所有x替换成xi，这样就保证带入xi时，分子和分母一模一样，开关的值为1：    

 

 另外补充与拉格朗日插值法相关的两个点：

    1. 一般i从0开始取，以适应计算机编程时的算法逻辑。

    2. 开关i一般用表示，它被称为为拉格朗日基本多项式（或称插值基函数）。      

来一道例题：用拉格朗日插值法求经过 （1,1），（2,4），（3,9）三个点的插值多项式。

解：

1. 首先构造出这个多项式的基本结构：

    注意这里第一个点表示为（x0,y0），以此类推...

   
   

2. 写出每一个开关结构：

    

   简单验算下：代入x=x0，L0(x)=1；代入x=x1 或 x=x2，L0(x)=0。没问题。

   同理得剩余两个开关：

   

   
   

3. 代入，化简，得结果：     

四.牛顿插值法

承接上面的例题，在有三个点的基础上，增加第四个点（4,16），求经过这四个点的插值多项式。如果继续用拉格朗日插值法构造开关的方法，会发现一个问题：每个开关都需要重新构造，它们的分子和分母都要接纳第四个点的x3和y3。

以第二个点的开关L1(x)为例，原本构造为：

由于新增了一个点，需要重新构造为以下形式：

原有的三个开关都要重新构造，还要加构造一个新的开关L3(x)。如果再增加一个点，则前四个开关都要重新构造，再加构一个L4(x)。如果再增加一个点，前五个开关又双叒叕要重新构造......

很明显，拉格朗日插值法不具备递归性（Récursivité），每次插入新的点都会带来大量的计算。而牛顿插值法则（Interpolation de Newton）可以解决这个问题。

牛顿插值法也用到了类似构造开关的思想，考虑递归性，可以这样构造：

它要表达的意思是：某一项的值 = 前一项的值 + ai×开关。

现在开关的作用是，根据x的值决定要不要加上两个多项式之间的差ai。每次新增一个插值点只需要多计算一个ai，之前算好的ai值不再变化。

以三个点为例：

如果增加第四个点的话，直接在原式后面增加第四项即可。之前算出的a0、a1、a2的值可保留：

按照这个逻辑，分别带入x值算算a：

1. 

2. 

3. 

观察到a0的值为y0，它被称为0阶差商。可表示为f(x0)。

a1的值为点（x0,y0）和点（x1,y1）之间的斜率。它被称为1阶差商。可表示为f[x0,x1]。

a2的值为 【点（x0,y0）和点（x1,y1）之间的斜率】和【点（x1,y1）和点（x2,y2）之间的斜率】 的斜率（好绕啊...），它被称为2阶差商。可表示为f[x0,x1,x2]。

...

以此类推，可以得出ai的值为i阶差商。可以表示为f[x0,x1, ... ,xi]。

为了方便计算（不被绕晕），我们一般用差商表（Table de différences divisées）来计算每一阶差商：

来个例题展示下这个方法的过程：用牛顿插值法求经过 点1（1,1），点2（2,4），点3（3,9）的插值多项式。

在此基础上，增加第四个点（4，16）。用牛顿插值法只需要多算下一阶差商，再带入到新增项后加入原式即可。

五.龙格现象

用前面两种插值法，n个点需要得到n-1次的多项式。点越多，多项式的次数也越高。通过计算得到的多项式，并不只是给本文开头扯淡的找规律题编一个像样的理由。它更多地会被用于预测还没有出现的点的位置。

为了预测准确，我们希望这条曲线尽可能平滑自然、保持当前趋势。

举个例子，有如下已知四点，预测第五个点x4的纵坐标y4：

比较理想的情况是用前四点得到一条平滑的插值多项式，带入x=x4来预测第五个点的纵坐标：

不理想的情况是得到的多项式弯弯扭扭地通过前四点。用这样的曲线来预测第五点的位置不具备说服力。尤其是多项式次数高了的话就容易出这个问题。

龙格现象（Phénomène de Runge）就是描述了这样的不理想情况。

在科学计算领域，龙格现象（Runge）指的是对于某些函数，使用均匀节点构造高次多项式差值时，在插值区间的边缘的误差可能很大的现象。它是由Runge在研究多项式差值的误差时发现的，这一发现很重要，因为它表明，并不是插值多项式的阶数越高，效果就会越好。

我会在下一篇文章用另一种插值法来回避这个问题。

至于本文这两种插值法，预测未知点可能会出问题，但用来在某乎上回答找规律的题肯定绰绰有余咯。

六.参考资料

1. 在线计算器: 拉格朗日多项式计算器 (planetcalc.com)
   

2. 在线计算器: 牛顿多项式插值 (planetcalc.com)
   

3. Analyse_Numerique__Slides_Etu_1x2.pdf (univ-lorraine.fr)

4. 多项式插值 - 维基百科，自由的百科全书 (wikipedia.org)
   

5. 如何直观地理解拉格朗日插值法？ - 知乎 (zhihu.com)

6. 拉格朗日插值法 - 维基百科，自由的百科全书 (wikipedia.org)

7. 牛顿多项式 - 维基百科，自由的百科全书 (wikipedia.org)

8. 龙格现象(Runge Phenomenon) - 知乎 (zhihu.com)

9. 找规律的数列问题真的没有任何意义吗？ - 知乎 (zhihu.com)