插值是啥？我们先来看这样一个例子，中学阶段我们都会计算三角函数值，如\sin 0^{\circ}, \sin 15^{\circ}, \sin 30^{\circ}, \sin 45^{\circ}, \sin 60^{\circ}, \sin 75^{\circ}, \sin 90^{\circ}\\ 这些我们都能够求出具体的数值，但是如果我们想知道 \sin 33^{\circ} 的值怎么办呢？也许你是个巨佬，可以通过各种倍角公式、和差化积、对称性质来求出它的精确表达式，但那样不仅费时费力，而且如果稍微变换下角度，就又得推翻重来，这个时候插值就站出来帮忙了。插值的基本思路就是，已知一些点，以及目标函数在该点的函数值，通过找到某个简单的函数，使得它在这些点上的函数值恰好与目标函数在这些点的函数值相同。进而，求目标函数在给定点之外的函数值就可以将其代入简单函数得到一个近似值。而怎样的函数才算得上简单呢？对了，多项式函数！在这门课程中，我们也只研究多项式函数的插值方法，下面给出问题的一般提法：给出 n+1 个点上的一张函数表，要构造一个多项式 \varphi(x) 满足下面两个条件(1) \varphi(x) 的次数不超过 n 次(2) 在给定的点 x_{i}(i=0,1, \cdots, n) 上与 f(x_{i}) 取值相同我们称这样的多项式 \varphi(x) 为插值函数，点 x_{i} 为插值节点并且假定它们是互异的.我们的目的是求目标函数在给定点之外的函数值，现在我们面临着一个很大的问题：我们求出的插值多项式可以是近乎笔直地通过平面上的这些点，也可以是“振荡”地通过，如果我们分别求出两个插值多项式，我们应该用哪个作为目标函数值得近似呢？同时如果对于特定的点，这样的多项式我们根本就求不出来呢？不不，先等下，下面这个定理告诉我们求出两个是不可能的，并且这样的多项式一定存在！定理 对于给定 n+1 个点的函数表，存在唯一多项式满足上面两个条件.证明
利用待定系数法假设所求插值多项式为p_{n}(x)=a_{0}+a_{1} x+a_{2} x^{2}+\cdots+a_{n} x^{n}\\ 该多项式要经过 n+1 个点，因此有\left\{\begin{array}{l} a_{0}+a_{1} x_{0}+a_{2} x_{0}^{2}+\cdots+a_{n} x_{0}^{n}=y_{0} \\ a_{0}+a_{1} x_{1}+a_{2} x_{1}^{2}+\cdots+a_{n} x_{1}^{n}=y_{1} \\ \cdots \cdots \cdots \cdots \\ a_{0}+a_{1} x_{n}+a_{2} x_{n}^{2}+\cdots+a_{n} x_{n}^{n}=y_{n} \end{array}\right.\\ 这个方程组有 n+1 个方程和 n+1 个未知量，存在唯一解等价于系数行列式不为0，而系数行列式为D=\left|\begin{array}{ccccc} 1 & x_{0} & x_{0}^{2} & \cdots & x_{0}^{n} \\ 1 & x_{1} & x_{1}^{2} & \cdots & x_{1}^{n} \\ \cdots & \cdots & \cdots & \cdots & \cdots \\ 1 & x_{n} & x_{n}^{2} & \cdots & x_{n}^{n} \end{array}\right|=\prod_{0 \leq j<i \leq n}\left(x_{i}-x_{j}\right)\\ 这是范德蒙（Vandermonde）行列式，由于插值节点 x_{i} 互异，所以其不为0，进而得到定理的结论.这个定理给我们打了一针强心剂，让我们对于任意给定的函数表都可以不加思索地上手求插值多项式，可是具体我们该如何求呢？我们线性代数课上学过可以利用克莱姆法则来求解线性方程组，即a_{i}=D_{i} / D\\ 其中D_{i}=\left|\begin{array}{ccccccccc} 1 & x_{0} & x_{0}^{2} & \cdots & x_{0}^{i-1} & y_{0} & x_{0}^{i} & \cdots & x_{0}^{n} \\ 1 & x_{1} & x_{1}^{2} & \cdots & x_{1}^{i-1} & y_{1} & x_{1}^{i} & \cdots & x_{1}^{n} \\ \cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots \\ 1 & x_{n} & x_{n}^{2} & \cdots & x_{n}^{i-1} & y_{0} & x_{0}^{i} & \cdots & x_{0}^{n} \end{array}\right|\\ 但我们知道，计算一个行列式的时间复杂度是阶乘级别的，而且范德蒙行列式通常是病态的，舍入误差会造成很大影响，因此很少会使用这样的公式！下面给出拉格朗日插值法的思路：※拉格朗日插值基本思路是构造 n 次多项式基函数 l_{i}(x) 使得p_{n}(x)=y_{0} l_{0}(x)+y_{1} l_{1}(x)+\cdots+y_{n} l_{n}(x)\\ 为了使 p_{n}(x) 通过 n+1 个点，基函数应该满足下面的条件l_{i}\left(x_{i}\right)=1, \quad l_{i}\left(x_{j}\right)=0, j \neq i\\ 如何求基函数呢？首先我们利用它的非常多的零点，待定系数如下l_{i}(x)=c\left(x-x_{0}\right)\left(x-x_{1}\right) \cdots\left(x-x_{i-1}\right)\left(x-x_{i+1}\right) \cdots\left(x-x_{n}\right)\\ 然后利用它所满足的 l_{i}\left(x_{i}\right)=1 可以解出待定系数并得到l_{i}(x)=\frac{\left(x-x_{0}\right)\left(x-x_{1}\right) \cdots\left(x-x_{i-1}\right)\left(x-x_{i+1}\right) \cdots\left(x-x_{n}\right)}{\left(x_{i}-x_{0}\right)\left(x_{i}-x_{1}\right) \cdots\left(x_{i}-x_{i-1}\right)\left(x_{i}-x_{i+1}\right) \cdots\left(x_{i}-x_{n}\right)}\\ 这个形式可以这样记忆：分子为 x 减去插值节点的连乘，分母为 x_{i} 减去插值节点的连乘，并且分子分母都不减 x_{i} ，这是因为如果分子有减 x_{i} ，那么就有 l_{i}(x_{i}) 就为0了，如果分母有减 x_{i} ，那么分母就为0了.但这个基函数的形式上还是比较长的，为了简便，我们记 n+1 项连乘为\omega_{n+1}(x)=\left(x-x_{0}\right)\left(x-x_{1}\right) \cdots\left(x-x_{n}\right)\\ 这个式子求导之后有很多项，但是在插值节点上的导数值很漂亮\omega_{n+1}^{\prime}\left(x_{i}\right)=\left(x_{i}-x_{0}\right)\left(x_{i}-x_{1}\right) \ldots\left(x_{i}-x_{i-1}\right)\left(x_{i}-x_{i+1}\right) \cdots\left(x_{i}-x_{n}\right)\\ 这样一来，基函数就可以表示成l_{i}(x)=\frac{\omega_{n+1}(x)}{\left(x-x_{i}\right) \omega_{n+1}^{\prime}\left(x_{i}\right)}\\ 进而p_{n}(x)=\sum_{j=0}^{n} y_{j} l_{j}(x)=\sum_{j=0}^{n} y_{j} \frac{\omega_{n}(x)}{\left(x-x_{j}\right) \omega_{n}^{\prime}\left(x_{j}\right)}\\ 通过一些计算可以得到\begin{array}{c} p_{n}(x)=\omega_{n}(x) \sum_{j=0}^{n} y_{j} \frac{1}{\left(x-x_{j}\right) \omega_{n}^{\prime}\left(x_{j}\right)} \\ p_{n}(x)=\frac{\sum_{j=0}^{n} y_{j} \frac{1}{\left(x-x_{j}\right) \omega_{n}^{\prime}\left(x_{j}\right)}}{\sum_{j=0}^{n} \frac{1}{\left(x-x_{j}\right) \omega_{n}^{\prime}\left(x_{j}\right)}} \end{array}\\ 最后一个式子得出需要注意到 \sum_{j=0}^{n} \frac{\omega_{n+1}(x)}{\left(x-x_{j}\right) \omega_{n}^{\prime}\left(x_{j}\right)} 是节点函数值全为1的插值多项式，因此该插值多项式也恒等于1，利用这个式子计算可以减小相近数相减的风险.我们已经通过构造出插值多项式来得到了函数值的近似，那么这个近似的效果如何呢？要研究近似的效果，就免不了扯上误差，下面给出多项式插值的余项以及误差估计：定理 设 p_{n}(x) 为 f(x) 在区间 [a,b] 上的 n 次插值多项式，那么对每个 x \in[a, b] ，存在 \xi \in(a, b) 使得f(x)-p_{n}(x)=\frac{f^{(n+1)}(\xi)}{(n+1) !}\left(x-x_{0}\right)\left(x-x_{1}\right) \cdots\left(x-x_{n}\right)\\ 证明 首先给出一个巧妙的构造，对 x \neq x_{i} ，令\phi(t)=f(t)-p_{n}(t)-\frac{f(x)-p_{n}(x)}{\omega_{n+1}(x)} \omega_{n+1}(t)\\ 可以验证 x, x_{0}, x_{1}, \cdots, x_{n} 都是 \phi(t) 的零点，反复利用罗尔定理，得到 n+1 阶导数至少有一个零点\phi^{(n+1)}(\xi)=0\\ 进而得到定理结论.顺便提一句：利用这个误差估计式也能够证明插值多项式的唯一性。具体来说，如果存在两个插值多项式，那么可以将其中一个看成是另外一个的插值多项式(因为插值条件是相同的)，进而误差估计式中的导数项恒为0，即二者相等.例1 设 f(x) \in C^{2}[a, b], f(a)=f(b)=0 ，求证\max _{a \leq x \leq b}|f(x)
\leq \frac{(b-a)^{2}}{8} \max _{a \leq x \leq b}\left|f^{\prime \prime}(x)\right|\\ 在数学分析中大家应该有见过类似的题目，但这里我们用插值的误差估计式可以给出更为简单的证明.解 0多项式显然是一个插值多项式，而存在即唯一，进而f(x)=f(x)-p_{1}(x)=\frac{f^{\prime \prime}(\xi)}{2}(x-a)(x-b)\\ 而利用基本不等式有\max _{a \leq x \leq b}|(x-a)(x-b)|=\left(\frac{b-a}{2}\right)^{2}\\ 可知结论成立.例2 求函数 f(x)=\sin (\pi x)+x^{4} 在节点 -1,0,1,2
的三次插值多项式.我们可以按定义来计算，但我们也可以结合多项式插值的线性性质：插值满足线性 若 f(x), g(x) 的插值多项式为 p(x), q(x) 则 f(x)+g(x) 的插值多项式为 p(x)+q(x) 解函数 f_{1}(x)=\sin (\pi x) 在节点处函数值均为0，因此其插值多项式为0多项式.记 f_{2}(x)=x^{4} 的三次插值多项式为 Q(x) ，利用误差估计式有x^{4}-Q(x)=\frac{\left(\xi^{4}\right)^{(4)}}{4 !}\left(x-x_{0}\right)\left(x-x_{1}\right)\left(x-x_{2}\right)\left(x-x_{3}\right)\\ 注意到 \left(\xi^{4}\right)^{(4)}=1 ，进而可得Q(x)=x^{4}-x(x-1)(x+1)(x-2)=2 x^{3}+x^{2}-2 x\\ 最后所求 p(x)=0+Q(x)=2 x^{3}+x^{2}-2 x .学习完拉格朗日插值法，你应该会觉得拉格朗日的基函数形式比较有规律性，适合记忆，这实际上也是拉格朗日法的一个优点；但是，你应该也能发现，如果我们要新增加一个节点，那么得到插值多项式可不是多添一项那么简单，而是要把所有基函数重写一遍，这也是它的不足之处。而我们接下来要介绍的牛顿插值法，就很好地弥补了这一不足。※牛顿插值法牛顿插值本质上也是构造基函数，只不过它要构造的基函数有着如下特定的形式：1, x-x_{0},\left(x-x_{0}\right)\left(x-x_{1}\right), \ldots,\left(x-x_{0}\right)\left(x-x_{1}\right)\left(x-x_{2}\right) \cdots\left(x-x_{n-1}\right)\\ 这其实也是我们之前定义过的 \omega_{i}(x),i=0,1,...,n ，利用待定系数法设出插值多项式的形式为\begin{aligned} Q(x) &=c_{0}+c_{1}\left(x-x_{0}\right)+c_{2}\left(x-x_{0}\right)\left(x-x_{1}\right)+\cdots \\ &+c_{n}\left(x-x_{0}\right)\left(x-x_{1}\right)\left(x-x_{2}\right) \cdots\left(x-x_{n-1}\right) \end{aligned}\\ 将已知的函数表中的点代入可以得到系数\begin{aligned} Q\left(x_{0}\right) &=c_{0}=f\left(x_{0}\right) \Longrightarrow c_{0}=f\left(x_{0}\right) \\ Q\left(x_{1}\right) &=c_{0}+c_{1}\left(x_{1}-x_{0}\right)=f\left(x_{1}\right) \Longrightarrow c_{1}=\frac{f\left(x_{1}\right)-f\left(x_{0}\right)}{x_{1}-x_{0}} \\ Q\left(x_{2}\right) &=c_{0}+c_{1}\left(x_{2}-x_{0}\right)+c_{2}\left(x_{2}-x_{0}\right)\left(x_{2}-x_{1}\right)=f\left(x_{2}\right) \\ & \Longrightarrow c_{2}=\left[\frac{f\left(x_{2}\right)-f\left(x_{0}\right)}{x_{2}-x_{0}}-\frac{f\left(x_{1}\right)-f\left(x_{0}\right)}{x_{1}-x_{0}}\right] \frac{1}{x_{2}-x_{1}} \end{aligned}\\...\\...\\...\\ 你会发现，这些系数有着类似的形式，就是先两个差，再作商，因此我们有必要先将这个形式弄明白，下面给出它的定义:差商（均差）对于函数 f(x) ，将其 n 次插值多项式的首项系数定义为 f(x) 的 n 阶差商，记为f\left[x_{0}, x_{1}, \cdots, x_{n}\right]\\ 它可以递推的表示成f\left[x_{0}, x_{1}, \cdots, x_{n}\right]=\frac{f\left[x_{1}, x_{2}, \cdots, x_{n}\right]-f\left[x_{0}, x_{1}, \cdots, x_{n-1}\right]}{x_{n}-x_{0}}\\ f\left[x_{0}\right]=f\left(x_{0}\right)\\ 这个递推形式需要记忆，其实也就是后 n 个节点的差商减前 n 个节点的差商，再除以最后的数减最前的数，可以看看自己写出的式子有没有下面方框中的形式进而根据类比递推得到牛顿插值多项式为\begin{aligned} P_{n}(x)=& f\left(x_{0}\right)+f\left[x_{0}, x_{1}\right]\left(x-x_{0}\right)+f\left[x_{0}, x_{1}, x_{2}\right]\left(x-x_{0}\right)\left(x-x_{1}\right) \\ &+\cdots+f\left[x_{0}, x_{1}, \cdots, x_{n}\right]\left(x-x_{0}\right)\left(x-x_{1}\right) \cdots\left(x-x_{n-1}\right) \end{aligned}\\ 差商有三个重要的性质：(1) 线性性质若 f(x)=a \varphi(x)+b \psi(x) ，则对任意正整数 k 有f\left[x_{0}, x_{1}, \cdots, x_{k}\right]=a \varphi\left[x_{0}, x_{1}, \cdots, x_{k}\right]+b \psi\left[x_{0}, x_{1}, \cdots, x_{k}\right]\\ (2) 可以表示成函数值得线性组合根据插值多项式的唯一性，牛顿插值法得到的多项式与拉格朗日得到的应该是相同的，考察两者的最高次项系数就可以得到f\left[x_{0}, x_{1}, \cdots, x_{n}\right]=\sum_{i=0}^{n} \frac{f\left(x_{i}\right)}{\omega_{n+1}^{\prime}\left(x_{i}\right)}\\ (3) 对称性：将其中的节点顺序改变，不影响差商的，即f\left[x_{0}, x_{1}, \cdots, x_{k}\right]=f\left[x_{i_{0}}, x_{i_{1}}, \cdots, x_{i_{k}}\right]\\ 牛顿插值的一个很大的好处就是，如果我们增加一个节点，那么只需要在原形式上添一项即可。即如果我们求出了 P_{k-1}(x) ，增加节点 x_{k} 后只需要在后面增加f\left[x_{0}, x_{1}, \cdots, x_{k}\right]\left(x-x_{0}\right)\left(x-x_{1}\right) \cdots\left(x-x_{k-1}\right)\\ 就可以得到 P_{k}(x) ，对于一个具体的问题，如果要求出牛顿插值多项式，可以通过构建如下差商表得出基函数前面的系数： 差商表通过 n+1 个函数值算出 n 个一阶差商，再通过 n 个一阶差商算出 n-1 个二阶差商，不断下去最后得到 n 阶差商.现在我们通过估计牛顿插值多项式的误差，来得到差商与导数之间的关系。首先由插值多项式的唯一性可以得到余项的唯一性，而牛顿法的余项可以用差商表示：定理 牛顿插值余项可以表示为\begin{aligned} R_{n}(x) &=f(x)-P_{n}(x) \\ &=f\left[x_{0}, x_{1}, \cdots, x_{n}, x\right]\left(x-x_{0}\right)\left(x-x_{1}\right) \cdots\left(x-x_{n-1}\right)\left(x-x_{n}\right) \end{aligned}\\ 证明 思路是通过增加一个节点，然后利用插值条件在定义域中任取与插值节点不同的 z ，则新增节点 z 后插值多项式变成\begin{aligned} Q(x)=& f\left(x_{0}\right)+f\left[x_{0}, x_{1}\right]\left(x-x_{0}\right)+f\left[x_{0}, x_{1}, x_{2}\right]\left(x-x_{0}\right)\left(x-x_{1}\right)+\cdots \\ &+f\left[x_{0}, x_{1}, \cdots, x_{n}\right]\left(x-x_{0}\right)\left(x-x_{1}\right) \cdots\left(x-x_{n-1}\right) \\ &+f\left[x_{0}, x_{1}, \cdots, x_{n}, z\right]\left(x-x_{0}\right)\left(x-x_{1}\right) \cdots\left(x-x_{n-1}\right)\left(x-x_{n}\right) \end{aligned}\\ 根据插值条件有Q(z)=f(z)\\ 由于 z 的任意性，将其换成 x 即得定理结论.而前面已经求得拉格朗日插值的余项为\frac{f^{(n+1)}(\xi)}{(n+1) !}\left(x-x_{0}\right)\left(x-x_{1}\right) \cdots\left(x-x_{n}\right)\\ 利用两个余项相等，可以得到差商与导数的关系1：f\left[x_{0}, x_{1}, \cdots, x_{n}, x\right]=\frac{f^{(n+1)}(\xi)}{(n+1) !}\\ 这里再补充差商与导数的关系2，即f\left[x_{0}, x_{1}, \cdots, x_{n}\right]=\frac{f^{(n)}(\xi)}{n !}\\ 证明思路与拉格朗日误差估计类似，也是通过构造一个具有比较多零点的函数，然后反复利用罗尔定理，这里构造的函数就是余项：R_{n}(x) =f(x)-P_{n}(x) \\ 利用罗尔定理可以得到 f 的 n 阶导数，而 P_{n}(x) 的 n 阶导数刚好就是差商.}