插值，即构造$f(x)$的近似函数$p(x)$，若$p(x)$取离散数据，称之为$f(x)$的插值函数，使得在某些点的值或者加上导数值相等

根据插值函数类型分类：代数插值（代数多项式)，样条插值

这里以王能超《数值分析简明教程》为基础，对泰勒插值、拉格朗日插值和牛顿插值等基础插值方式作介绍

泰勒插值

插值公式

取$f(x)$在$x_0$处的泰勒展开（泰勒多项式）$$p_n(x)=f(x_0)+f^{\prime }(x_0)(x-x_0)+\frac{f^{\prime \prime }(x_0)}{2!}(x-x_0{)}^2+\cdots +\frac{f^{(n)}}{n!}(x-x_0{)}^n$$在某点$x_0$逼近$f(x)$，值相等，各阶导数值相等

余项分析

插值函数$p_n(x)$的截断误差或称插值余项$R(x)=f(x)-p_n(x)$
泰勒余项定理：含有$x_0$区间$[a,b]$内有直到$n+1$阶导数，区间内
$$f(x)-p_n(x)=\frac{f^{(n+1)}(\epsilon )}{(n+1)！}(x-x_0{)}^{n+1},\epsilon \in [a,b]$$

拉格朗日插值

问题的描述

作$n$次多项式$p_n(x)$，使得在各插值节点（$n+1$个互不相同， $x_i,i=0,1,2,\cdots ,n$）上的值与函数$f(x)$节点值相等
即构造$n$次多项式$p_n(x)=a_0+a_{1}x+a_2{x}_0^2+\cdots +a_n{x}^n$使得$p_n(x_i)=y_i=f(x_i),i=0,1,\cdots ,n$

拉格朗日多插值多项式的系数的项数与插值点数相等，并对于给定的互不相同节点，插值多项式$p_n(x)$一定存在：
求解关于系数$a_0,a_1,\cdots ,a_n$的线性方程组
$$\{\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 \\ a_0+a_1{x}_n+a_2{x}_n^2+\cdots +a_n{x}_n^n=y_n\end{array}$$
注意多项式的次数其实是度数要注意零次幂常数项的存在
其系数行列式为范德蒙（Vandermonde）行列式，性质即证

插值函数求解方法

直接求解上面的线性方程组过于复杂，尝试找出显式规律

构造的思路

利用插值节点处的值，每个节点$x_i$构造对应的插值基函数$l_i(x)$（关于$x$，与系数组成插值函数），并将其与节点的值$y_i$（系数)分离，更好的体现出“基函数”性
核心思想：每个节点插值函数只在当前节点有贡献，其他节点为零，保证当前节点的值对应的同时避免对以同样方式构造的其他插值基函数负责的节点的值的干扰。注意到节点之间为各插值函数组合。
上面的构造思想道出了插值函数应满足的性质

拉格朗日插值公式的形式

根据构造思路的讨论，$y=f(x)$的插值函数$p_n(x)={\sum }_{i=0}^n{y}_i{l}_i(x)$
$i$节点$x_i$对应的插值基函数$l_i(x)$应满足:$l_i(x_j)={\delta }_{ij}=\{\begin{array}{l}1,j=i\\ 0,j\ne i\end{array}$
给出其构造形式，考虑分式，除当前节点，节点均作为零点添加进式子，当前节点与其他节点之差作为分母，使当$i=j$时分子和分母相等，且分母不为零
$$l_i(x)=\prod _{j=0,j\ne k}^n\frac{x-x_j}{x_i-x_j}$$
i和j仅代表当前处理节点不同
按照此方法构造的插值函数即拉格朗日插值公式
$$p_n(x)=\sum _{i=0}^n(\prod _{j=0,j\ne k}^n\frac{x-x_j}{x_i-x_j})y_i$$

拉格朗日余项定理

插值节点$x_0,x_1,\cdots ,x_n$在$[a,b]$内，$f(x)$在$[a,b]$有连续的直到$n+1$阶导数，在区间内有
$$f(x)-p_n(x)=\frac{f^{(n+1)}(x)}{(n+1)!}\prod _{i=0}^n(x-x_i)$$
推导过程设包含了当前项$p_n(t)$和${\prod }_{i=0}^n(x-x_i)$形式余项形式的插值表示函数，并使得辅助函数在差值节点再加上当前点$x$时值与$f(x)$相等，使用罗尔定理证明该形式合理，属于倒推

反映了若插值点落在区间$[a,b]$内，属于内插；若落在区间外，属于外推，不适用余项定理，外推结果不可靠

拓展和不足

增加插值点的做法

拉格朗日插值增加一个插值点，需要重新计算公式中所有的系数（插值基函数），引出误差的事后估计法

事后估计法

从简单的两点线性插值引入
选取点$(x_0,y_0)$和点$(x_1,y_1)$作线性插值，得到插值函数$p_1(x)$；选取点$(x_0,y_0)$和点$(x_2,y_2)$作线性插值，得到插值函数$p_2(x)$（注意不同于此前的记号，p的下标仅代表两个不同的插值函数；之所以这样记是使用$y_1$和$y_2$表示插值函数而不是$x_1$和$x_2$的值显得并不直观，但$y$仍然代表$f(x)$）
根据余项定理的估计
$y-p_1(x)\approx \frac{f’’(\epsilon )}{2}(x-x_0)(x-x_1)$
$y-p_2(x)\approx \frac{f’’(\epsilon )}{2}(x-x_0)(x-x_2)$
两式相比得$\frac{y-p_1(x)}{y-p_2(x)}\approx \frac{x-x_1}{x-x_2}$，这个结果容易与斜率的含义混淆，因此要记住刚刚约定的下标的含义，但是类比直线的两点式用基函数的方法尝试将$y$表示出来
$$y=\frac{x-x_2}{x_1-x_2}{p}_1(x)+\frac{x-x_1}{x-x_1}{p}_2(x)$$
可以看到由两个线性插值得到了新的插值公式，其含义在于
$$y-p_1(x)=\frac{x-x_1}{x_2-x_1}(p_2(x)-p_1(x))$$
插值结果$p_1(x)$的误差$y-p_1(x)$可以由两个结果的偏差给出，经过实例验证后还发现这种添加一个新点计算新的插值函数估计出来的偏差估计出的结果用来修正旧点的插值结果与高一次拉格朗日插值的结果相同，引出下面的埃特金算法

埃特金(Aitken)算法

为了描述递推形式的埃特金算法引入专门的记号，
$f_k(x_i)$表示在使用$x_0,x_1,\cdots ,x_{k-1}$进行$k-1$次拉格朗日插值的基础上，加上新的插值节点$x_i(i\ge k)$所得的插值结果，在下面的逐阶递推表达时$i$就取$k$，$f_k(x_k)$就是$k$次拉格朗日插值多项式的结果，但仍然是关于$x$的函数，不代表取值
从事后估计法的两个线性插值得到的新插值公式其实就是抛物插值的结果，归纳的有（按照基函数的构造去记忆）
$$f_k(x_i)=\frac{x-x_i}{x_{k-1}-x_i}{f}_{k-1}(x_{k-1})+\frac{x-x_{k-1}}{x_i-x_{k-1}}{f}_{k-1}(x_i)$$
含义上不是由$k-1$次插值新添加的$(x_i,y_i)$点得到$k$次插值下$(x_i,y_i)$的结果，要从递推的角度去理解，0次插值就是$f(x_0)$
因此无法给出显示形式，需要建立具有承袭性的显示的插值公式

牛顿插值

想要显示地承袭性插值公式，在$k-1$次插值的基础上，就只能根据已知插值节点去计算新的插值节点$x_i$带来的项的系数（借用插值基函数的思想，不影响其它插值节点$x_0,x_1,\cdots ,x_{k-1}$，故应是$c{\prod }_{j=0,j\ne i}^{k-1}(x-x_j)$的形式），求解出新的系数值
对比拉格朗日插值公式的插值基函数设法，其实牛顿插值是拉格朗日插值的另一表现形式，直接在上一次插值基础上递推求出当前次的拉格朗日插值（埃特金算法需要两个上一次插值且非标准化仅能由递推给出）

差商

为了表示方便引入差商的概念（P24给出了不用差商时的形式），这里的常变量（指不含$x$）$n$阶差商就对应$n$次插值的$n$次项${\prod }_{i=0}^n(x-x_i)$项的系数，而其余次项具有承袭性与前面得到的结果相同（引入$n$阶差商时$n$次项对应的式就永久成立）
一阶差商：$f(x_0,x_1)=\frac{f(x_1)-f(x_0)}{x_1-x_0}$
二阶差商：$f(x_0,x_1,x_2)=\frac{f(x_1,x_2)-f(x_0,x_1)}{x_2-x_0}$
$n$阶差商：$f(x_0,x_1,\cdots ,x_n)=\frac{f(x_1,x_2,\cdots ,x_n)-f(x_0,x_1,\cdots ,x_{n-1})}{x_n-x_0}$
可以看到差商也使用了类似递推的定义，补充零阶差商为$f(x_i)$

将差商展开成节点的形式可得到差商的对称性，任意交换节点的次序不对差商值产生影响，差商与节点的排列顺序无关

$$f(x_0,x_1,\cdots ,x_n)=\sum _{i=0}^n\frac{f(x_i)}{{\prod }_{j=0,j\ne i}^n(x_i-x_j)}$$

差商形式的插值公式（牛顿插值公式）

逆推差商定义

推导过程

根据差商的定义式尝试逆推，需要把新引进的变量$x$当作此前的常数$x_i$看，我们的目标就是求出$f(x)$
$f(x)=f(x_0)+f(x_0,x)(x-x_0)$
继续利用高阶差商项逆推下去，这时要引进的新变量不是$x$了，先参照差商定义式对节点排列
$f(x_0,x)=f(x_1,x_0)+f(x_1,x_0,x)(x-x_1)$
根据对称性写成
$f(x_0,x)=f(x_0,x_1)+f(x_0,x_1,x)(x-x_1)$
继续逆推
$f(x_0,x_1,x)=f(x_2,x_0,x_1)+f(x_2,x_0,x_1,x)(x-x_2)$
即
$f(x_0,x_1,x)=f(x_0,x_1,x_2)+f(x_0,x_1,x_2,x)(x-x_2)$
总结规律：展开含有$x$的$n-1$阶差商$f(x_0,x_1,\cdots ,x_{n-1},x)$，得到在原有常量节点上加上新节点$x_n$的常数差商加上在新的常数差商上引入变量$x$的差商与$x-x_n$之积
$f(x_0,x_1,\cdots ,x_{n-1},x)=f(x_0,x_1,\cdots ,x_{n-1},x_n)+f(x_0,x_1,\cdots ,x_{n-1},x_n,x)(x-x_n)$

结论

同样地递推得到插值公式，为了得到公式形式的一致性，遵循特定的排列顺序，运用对称性进行验证
$f(x)=f(x_0)+f(x_0,x)(x-x_0)$
$f(x_0,x)=f(x_0,x_1)+f(x_0,x_1,x)(x-x_1)$
$f(x_0,x_1,x)=f(x_0,x_1,x_2)+f(x_0,x_1,x_2,x)(x-x_2)$
$f(x_0,x_1,\cdots ,x_{n-1},x)=f(x_0,x_1,\cdots ,x_n)+f(x_0,x_1,\cdots ,x_n,x)(x-x_n)$

牛顿插值公式

逐层代入含有$x$的差商使得其只在末项作为余项$R(x)$存在
得到$p_n(x)$即牛顿插值公式

$$\begin{array}{rl}f(x)=& p_n(x)+R(x)\\ =& f(x_0)+f(x_0,x_1)(x-x_0)+f(x_0,x_1,x_2)(x-x_0)(x-x_1)\\ & +\cdots +f(x_0,x_1,\cdots ,x_n)(x-x_0)(x-x_1)\cdots (x-x_{n-1})\\ & +\begin{array}{c}\underbrace{f(x_0,x_1,\cdots ,x_n,x)(x-x_0)(x-x_1)\cdots (x-x_n)}\\ R(x)\end{array}\end{array}$$
$p_n(x)$的每一项的系数其实是由其下一项在代入时“下放”得来，因此系数是$n$阶差商但该项只有$n-1$次