多项式插值为何会小于n次

插值
告诉你一个函数会经过 n 个点（n个点各不相同），然后让你计算其余几个位置的取值。
一般情况下可能会用在一些数据统计中函数的拟合。（不然为什么会有这么多乱七八糟的拟合啊QAQ）
当然，这里主要涉及的是多项式插值，即利用经过这n个点的最高次项次数小于n的关于x的那个多项式，通过代入或者其他方法求出这几个位置的取值。
当然，这里给出一道模板题，在拉格朗日插值和牛顿插值时就是用这个模板题的。
模板题
当然，这种题目暴力用高斯消元也是能做的，可惜A不了，毕竟时间复杂度时O(n3)
下文都认为给出的是n+1个点，点的标号从0开始，同时设第k个点为(xk,yk)。
拉格朗日插值法
普通拉格朗日插值法
观察模板题和高斯消元，你会发现我们把这个多项式解出来真的太浪费啦。
有没有不用求出多项式也能求值的方法呢？
有！
拉格朗日发表了这么一个方法：
L(x)=
n
∑
i=0
ℓi(x)yi
其中ℓi(x)叫 拉格朗日基本多项式 ，L(n)叫 拉格朗日插值多项式 。
ℓi(x)=
n
∏
j=0,j≠i

(x−xj)
(xi−xj)
这个多项式有个非常NB的性质（其实也非常显然）
就是ℓi(x)在xj(j≠i)处为0，在xi处为1。
那么显然，L(x)经过这n个点。
这样，我们就只需要把k代入，就可以在O(n2)的时间内求解了。
显然，我们节省的是求出这个多项式的时间。
当然，可以证明的是，这个拉格朗日插值多项式是唯一一个次数≤n的经过这n+1个点的多项式。
唯一性
假设存在两个n次多项式，都经过这n+1个点，假设这两个多项式为P1,P2
P3=P2−P1
那么P3显然≠0。
而且因为都经过n+1个点，所以有n+1个根，所以P3的次数为n。
而且可以写成
那么P3可以写成k
n
∏
i=0
(x−xi)
但是这样次数是n+1的，显然不对，矛盾，证毕。
所以最多存在这样唯一一个多项式。
存在性
首先，不一定存在次数为 n 的多项式，举个例子：
(1,1),(2,2),(3,3)就不能被一个二次方程经过。
当然，能经过这n+1个点的也不一定要是个次数大于0的多项式，比如你给n+1个y值相等的点，怎么可能存在一个n次多项式能够经过n+1个y值相同的点啊（因为这和一个多项式能有n+1个点的命题是等价的，这个命题先让错误，不然可以写成(x−xi)的形式，证明这个形式次数大于n）。
所以下面假定至少存在两个点 y 值不同。
在这个条件下，我们可以证明L(x)是一个次数大于0的多项式。
我们假设存在一组a0,a1,a2,an+1系数，使得：
P(x)=
n
∑
i=0
aiℓ(i)=an+1
首先，因为ℓi(x)函数只有在xi处为1，其余xj处都是为0的，所以显然P(xi)=ai，但是呢，这个函数的值又是恒定的，所以a0=a1=a2==an+1。
又因为yi并不相同，所以证毕。
代码
当然，这道题目我还是有