Definition 14.3. 设函数\(f\)在\([a,b]\)上有定义，且已知在点\(a\leqslant x_0<x_1<\cdots<x_n\leqslant b\)上的值\(y_0,y_1,\dots,y_n\)。若存在一个简单函数\(P(x)\)使得：
\[\begin{equation*}
P(x_i)=y_i,\quad i=0,1,\dots,n
\end{equation*}\]
则称\(P\)为\(f\)的插值函数（interpolating function），点\(x_0,x_1,\dots,x_n\)被称为插值节点（interpolation nodes），\([a,b]\)为插值区间（interpolation interval），求插值函数\(P\)的方法称为插值法（interpolation method）。若\(P\)是不超过\(n\)次的多项式，即：
\[\begin{equation*}
P(x)=\sum_{i=0}^{n}a_ix^i,\quad a_i\in\mathbb{R}^{},\;i=0,1,\dots,n
\end{equation*}\]
则称\(P\)为插值多项式（interpolation polynomial），对应的插值法被称为多项式插值（polynomial interpolation）。若\(P\)是分段的多项式，则称对应的插值法为分段插值（piecewise interpolation）。
Lagrange插值多项式
Definition 14.4. 若\(n\)次多项式\(l_i(x),\;i=0,1,\dots,n\)在\(n+1\)个节点\(x_0<x_1<\cdots<x_n\)上满足：
\[\begin{equation*}
l_i(x_j)=
\begin{cases}
1,& i=j \\
0,& i\ne j
\end{cases},\quad
i,j=0,1,\dots,n
\end{equation*}\]
则称\(l_0(x),l_1(x),\dots,l_n(x)\)为节点\(x_0,x_1,\dots,x_n\)上的\(n\)次插值基函数（interpolation basis functions）。
Definition 14.5. 设函数\(f\)在\([a,b]\)上有定义，且已知在点\(a\leqslant x_0<x_1<\cdots<x_n\leqslant b\)上的值\(y_0,y_1,\dots,y_n\)。定义：
\[\begin{equation*}
l_i(x)=\frac{(x-x_0)(x-x_1)\dots(x-x_{i-1})(x-x_{i+1})\dots(x-x_n)}{(x_i-x_0)(x_i-x_1)\dots(x_i-x_{i-1})(x_i-x_{i+1})\dots(x_i-x_n)},\quad i=0,1,\dots,n
\end{equation*}\]
称：
\[\begin{equation*}
L_n(x)\coloneq\sum_{i=0}^{n}y_il_i(x)
\end{equation*}\]
为\(f\)在节点\(x_0,x_1,\dots,x_n\)上的拉格朗日插值多项式（Lagrange interpolation polynomial）。
Property 14.2.1. 设函数\(f\)在\([a,b]\)上有定义，且已知在点\(a\leqslant x_0<x_1<\cdots<x_n\leqslant b\)上的值\(y_0,y_1,\dots,y_n\)，\(f\in C^n([a,b])\)，\(f^{(n+1)}\)在\((a,b)\)上存在，\(L_n\)为\(f\)在节点\(x_0,x_1,\dots,x_n\)上的Lagrange插值多项式。\(L_n\)具有如下性质：
记\(w_{n+1}(x)=(x-x_0)(x-x_1)\cdots(x-x_n)\)，则：
\[\begin{equation*}
L_n(x)=\sum_{i=0}^{n}y_i\frac{w_{n+1}(x)}{(x-x_i)w_{n+1}'(x_i)}
\end{equation*}\]
对于任意的\(x\in[a,b]\)，有误差估计：
\[\begin{equation*}
f(x)-L_n(x)=\frac{f^{(n+1)}(\xi)}{(n+1)!}w_{n+1}(x)
\end{equation*}\]
其中\(\xi\in(a,b)\)；
\(\sum\limits_{i=0}^{n}x_i^ml_i(x)=x^m(m\leqslant n)\)；
\(L_n\)有如下形式：
\[\begin{equation*}
L_n(x)=\frac{\sum\limits_{i=0}^{n}y_i\dfrac{1}{(x-x_i)w_{n+1}'(x_i)}}{\sum\limits_{i=0}^{n}\dfrac{1}{(x-x_i)w_{n+1}'(x_i)}}
\end{equation*}\]
证明. (1)由乘积的微分可知：
\[\begin{equation*}
w_{n+1}'(x_i)=(x_i-x_0)(x_i-x_1)\dots(x_i-x_{i-1})(x_i-x_{i+1})\dots(x_i-x_n)
\end{equation*}\]
于是：
\[\begin{equation*}
l_i(x)=\frac{w_{n+1}(x)}{(x-x_i)w_{n+1}'(x_i)}
\end{equation*}\]
(2)由条件可设\(f(x)-L_n(x)=K(x)w_{n+1}(x)\)，其中\(K(x)\)是一个待定函数。作辅助函数：
\[\begin{equation*}
\varphi(t)=f(t)-L_n(t)-K(x)w_{n+1}(t)
\end{equation*}\]
由性质 3.3.3(5.b)和性质 4.1.1(4)可知\(\varphi^{(n)}\)在\([a,b]\)上连续，\(\varphi^{(n+1)}\)在\((a,b)\)上存在。因为\(\varphi\)在\(x_0,x_1,\dots,x_n\)和\(x\)处均为\(0\)，所以\(\varphi\)在\([a,b]\)上有\(n+2\)个零点，根据性质 3.3.3(5.b)、性质 4.1.1(4)和定理 4.2可知\(\varphi'\)在\(\varphi\)的两个零点间至少存在一个零点，所以\(\varphi'\)在\([a,b]\)上至少存在\(n+1\)个零点。对\(\varphi'\)再使用定理 4.2可知\(\varphi''\)在\([a,b]\)上至少存在\(n\)个零点。依此类推可知\(\varphi^{(n+1)}\)在\((a,b)\)上至少存在一个零点\(\xi\)，即：
\[\begin{equation*}
\varphi^{(n+1)}(\xi)=f^{(n+1)}(\xi)-K(x)(n+1)!=0
\end{equation*}\]
于是：
\[\begin{equation*}
K(x)=\frac{f^{(n+1)}(\xi)}{(n+1)!}
\end{equation*}\]
即：
\[\begin{equation*}
f(x)-L_n(x)=\frac{f^{(n+1)}(\xi)}{(n+1)!}w_{n+1}(x)
\end{equation*}\]
(3)设\(f=x^m\)，由(2)即可得出结论。
(4)在(3)中取\(m=0\)，由(1)(3)可得：
\[\begin{equation*}
1=\sum_{i=0}^{n}l_i(x)=\sum_{i=0}^{n}\frac{w_{n+1}(x)}{(x-x_i)w_{n+1}'(x_i)}=w_{n+1}(x)\sum_{i=0}^{n}\frac{1}{(x-x_i)w_{n+1}'(x_i)}
\end{equation*}\]
所以：
\[\begin{equation*}
w_{n+1}(x)=\frac{1}{\sum\limits_{i=0}^{n}\dfrac{1}{(x-x_i)w_{n+1}'(x_i)}}
\end{equation*}\]
于是有：
\[\begin{align*}
L_n(x)&=\sum_{i=0}^{n}y_i\frac{w_{n+1}(x)}{(x-x_i)w_{n+1}'(x_i)}=w_{n+1}(x)\sum_{i=0}^{n}y_i\frac{1}{(x-x_i)w_{n+1}'(x_i)} \\
&=\frac{\sum\limits_{i=0}^{n}y_i\dfrac{1}{(x-x_i)w_{n+1}'(x_i)}}{\sum\limits_{i=0}^{n}\dfrac{1}{(x-x_i)w_{n+1}'(x_i)}}
\end{align*}\]
◻
note 14.1. 性质 14.2.1(4)中\(L_n\)的形式又被称为Barycentric形式。该表示形式在数学上与拉格朗日插值多项式完全等价，但在数值计算中避免了高次多项式乘积的显式计算，即计算：
\[\begin{equation*}
w_{n+1}(x)=(x-x_0)(x-x_1)\cdots(x-x_n)
\end{equation*}\]
从而减少了由大数乘积和相消所引起的数值误差，具有显著更优的稳定性。基于上述原因，在实际数值计算中通常优先采用Barycentric形式来实现多项式插值。
import numpy as np
from scipy.interpolate import BarycentricInterpolator
x_nodes = np.array([0.0,1.0,2.0,3.0])
y_nodes = np.array([1.0,2.0,0.0,5.0])
interp = BarycentricInterpolator(x_nodes,y_nodes)
print(interp(1.5))
Newton插值多项式
Definition 14.6. 设函数\(f\)在\([a,b]\)上有定义，\(a\leqslant x_0<x_1<\cdots<x_n\leqslant b\)。记\(f[x_0]=f(x_0)\)，称：
\[\begin{equation*}
f[x_0,x_n]=\frac{f(x_n)-f(x_0)}{x_n-x_0}
\end{equation*}\]
为\(f\)关于点\(x_0,x_n\)的一阶均差（first-order divided difference）。称：
\[\begin{equation*}
f[x_0,x_1,\dots,x_n]=\frac{f[x_1,x_2,\dots,x_n]-f[x_0,x_1,\dots,x_{n-1}]}{x_n-x_0}
\end{equation*}\]
为\(f\)的n阶均差（n-th order divided difference）。
Property 14.2.2. 设函数\(f\)在\([a,b]\)上有定义，\(a\leqslant x_0<x_1<\cdots<x_n\leqslant b\)。均差具有如下性质：
\(f\)的\(n\)阶均差可以表示为\(f(x_0),f(x_1),\dots,f(x_n)\)的线性组合：
\[\begin{equation*}
f[x_0,x_1,\dots,x_n]=\sum_{i=0}^{n}\frac{f(x_i)}{(x_i-x_0)(x_i-x_1)\dots(x_i-x_{i-1})(x_i-x_{i+1})\dots(x_i-x_n)}
\end{equation*}\]
\(f[x_0,x_1,\dots,x_n]\)对\(\{x_0,x_1,\dots,x_n\}\)的任意顺序置换保持不变；
对任意的\(\alpha,\beta\in\mathbb{R}^{}\)和\([a,b]\)上的函数\(g\)，有：
\[\begin{equation*}
(\alpha f+\beta g)[x_0,x_1,\dots,x_n]=\alpha f[x_0,x_1,\dots,x_n]+\beta g[x_0,x_1,\dots,x_n]
\end{equation*}\]
若\(f\in C^n([a,b])\)，则存在\(\xi\in[a,b]\)使得：
\[\begin{equation*}
f[x_0,x_1,\dots,x_n]=\frac{f^{(n)}(\xi)}{n!}
\end{equation*}\]
证明. (1)使用数学归纳法。当\(n=1\)时有：
\[\begin{equation*}
f[x_0,x_1]=\frac{f(x_1)-f(x_0)}{x_1-x_0}=\frac{f(x_0)}{x_0-x_1}+\frac{f(x_1)}{x_1-x_0}
\end{equation*}\]
结论成立。设结论对\(n-1\)成立，下面证明结论对\(n\)也成立。
根据归纳假设：
\[\begin{align*}
&f[x_0,x_1,\dots,x_n]=\frac{f[x_1,x_2,\dots,x_n]-f[x_0,x_1,\dots,x_{n-1}]}{x_n-x_0} \\
=&\frac{1}{x_n-x_0}\left[\sum_{i=1}^{n}\frac{f(x_i)}{(x_i-x_1)(x_i-x_2)\dots(x_i-x_{i-1})(x_i-x_{i+1})\dots(x_i-x_n)}\right. \\
&\left.-\sum_{i=0}^{n-1}\frac{f(x_i)}{(x_i-x_0)(x_i-x_1)\dots(x_i-x_{i-1})(x_i-x_{i+1})\dots(x_i-x_{n-1})}\right] \\
=&\frac{f(x_n)}{(x_n-x_0)(x_n-x_1)\dots(x_n-x_{n-1})}+\frac{f(x_0)}{(x_0-x_1)(x_0-x_2)\dots(x_0-x_n)} \\
&+\sum_{i=1}^{n-1}\left[\frac{f(x_i)}{(x_n-x_0)(x_i-x_1)(x_i-x_2)\dots(x_i-x_{i-1})(x_i-x_{i+1})\dots(x_i-x_n)}\right. \\
&\left.-\frac{f(x_i)}{(x_n-x_0)(x_i-x_0)(x_i-x_1)\dots(x_i-x_{i-1})(x_i-x_{i+1})\dots(x_i-x_{n-1})}\right]
\end{align*}\]
对于最后一项：
\[\begin{align*}
&\sum_{i=1}^{n-1}\left[\frac{(x_i-x_0)f(x_i)}{(x_n-x_0)(x_i-x_0)(x_i-x_1)(x_i-x_2)\dots(x_i-x_{i-1})(x_i-x_{i+1})\dots(x_i-x_n)}\right. \\
&\left.-\frac{(x_i-x_n)f(x_i)}{(x_n-x_0)(x_i-x_0)(x_i-x_1)\dots(x_i-x_{i-1})(x_i-x_{i+1})\dots(x_i-x_{n-1})(x_i-x_n)}\right] \\
=&\sum_{i=1}^{n-1}\frac{(x_i-x_0)f(x_i)-(x_i-x_n)f(x_i)}{(x_n-x_0)(x_i-x_0)(x_i-x_1)(x_i-x_2)\dots(x_i-x_{i-1})(x_i-x_{i+1})\dots(x_i-x_n)} \\
=&\sum_{i=1}^{n-1}\frac{(x_n-x_0)f(x_i)}{(x_n-x_0)(x_i-x_0)(x_i-x_1)(x_i-x_2)\dots(x_i-x_{i-1})(x_i-x_{i+1})\dots(x_i-x_n)} \\
=&\sum_{i=1}^{n-1}\frac{f(x_i)}{(x_i-x_0)(x_i-x_1)\dots(x_i-x_{i-1})(x_i-x_{i+1})\dots(x_i-x_n)}
\end{align*}\]
所以结论成立。
(2)由(1)立即可得。
(3)由(1)立即可得。
(4)令\(L_{n-1}\)为\(f\)在节点\(x_0,x_1,\dots,x_{n-1}\)上的Lagrange插值多项式，作辅助函数：
\[\begin{equation*}
\varphi(x)=f(x)-L_{n-1}(x)-f[x_0,x_1,\dots,x_n]w_n(x)
\end{equation*}\]
由\(L_{n-1}\)的定义可知\(f-L_{n-1}\)在节点\(x_0,x_1,\dots,x_{n-1}\)上为\(0\)，而\(w_n\)在节点\(x_0,x_1,\dots,x_{n-1}\)上为\(0\)，所以\(x_0,x_1,\dots,x_{n-1}\)是\(\varphi\)的零点。注意到：
\[\begin{align*}
&f(x_n)-L_{n-1}(x_n)-f[x_0,x_1,\dots,x_n]w_n(x_n) \\
=&f(x_n)-\sum_{i=0}^{n-1}\frac{f(x_i)(x_n-x_0)(x_n-x_1)\dots(x_n-x_{i-1})(x_n-x_{i+1})\dots(x_n-x_{n-1})}{(x_i-x_0)(x_i-x_1)\dots(x_i-x_{i-1})(x_i-x_{i+1})\dots(x_i-x_{n-1})} \\
&-\sum_{i=0}^{n}\frac{f(x_i)(x_n-x_0)(x_n-x_1)\cdots(x_n-x_{n-1})}{(x_i-x_0)(x_i-x_1)\dots(x_i-x_{i-1})(x_i-x_{i+1})\dots(x_i-x_n)} \\
=&f(x_n)-\sum_{i=0}^{n-1}\frac{f(x_i)(x_n-x_0)(x_n-x_1)\dots(x_n-x_{i-1})(x_n-x_{i+1})\dots(x_n-x_{n-1})}{(x_i-x_0)(x_i-x_1)\dots(x_i-x_{i-1})(x_i-x_{i+1})\dots(x_i-x_{n-1})} \\
&-f(x_n)-\sum_{i=0}^{n-1}\frac{f(x_i)(x_n-x_0)(x_n-x_1)\cdots(x_n-x_{n-1})}{(x_i-x_0)(x_i-x_1)\dots(x_i-x_{i-1})(x_i-x_{i+1})\dots(x_i-x_n)} \\
=&-\sum_{i=0}^{n-1}\frac{f(x_i)(x_n-x_0)(x_n-x_1)\dots(x_n-x_{n-1})}{(x_i-x_0)(x_i-x_1)\dots(x_i-x_{i-1})(x_i-x_{i+1})\dots(x_i-x_{n-1})(x_n-x_i)} \\
&-\sum_{i=0}^{n-1}\frac{f(x_i)(x_n-x_0)(x_n-x_1)\cdots(x_n-x_{n-1})}{(x_i-x_0)(x_i-x_1)\dots(x_i-x_{i-1})(x_i-x_{i+1})\dots(x_i-x_n)}=0
\end{align*}\]
所以\(x_n\)也是\(\varphi\)的零点。根据性质 3.3.3(5.b)、性质 4.1.1(4)和定理 4.2可知\(\varphi'\)在\([a,b]\)上存在\(n\)个零点。对\(\varphi'\)再使用定理 4.2可知\(\varphi''\)在\([a,b]\)上存在\(n-1\)个零点。依此类推可知\(\varphi^{(n)}\)在\([a,b]\)上存在一个零点\(\xi\)，即：
\[\begin{equation*}
\varphi^{(n)}(\xi)=f^{(n)}(\xi)-f[x_0,x_1,\dots,x_n]n!=0
\end{equation*}\]
所以：
\[\begin{equation*}
f[x_0,x_1,\dots,x_n]=\frac{f^{(n)}(\xi)}{n!}
\end{equation*}\]
◻
Definition 14.7. 设函数\(f\)在\([a,b]\)上有定义，且已知在点\(a\leqslant x_0<x_1<\cdots<x_n\leqslant b\)上的值\(y_0,y_1,\dots,y_n\)。称：
\[\begin{equation*}
P_n(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,\dots,x_n]\prod_{i=0}^{n-1}(x-x_i)
\end{equation*}\]
为\(f\)在节点\(x_0,x_1,\dots,x_n\)上的牛顿插值多项式（Newton interpolation polynomial）。
Property 14.2.3. Newton插值多项式与Lagrange插值多项式等价。
证明. 设函数\(f\)在\([a,b]\)上有定义，且已知在点\(a\leqslant x_0<x_1<\cdots<x_n\leqslant b\)上的值\(y_0,y_1,\dots,y_n\)。因为\(f\)在节点\(x_0,x_1,\dots,x_n\)上的Newton插值多项式\(P_n\)的次数不超过\(n\)，根据定理 14.3只需证明\(P_n(x_i)=f(x_i),\;i=0,1,\dots,n\)。
使用数学归纳法。当\(i=0\)时由\(P_n\)的定义可知\(P_n(x_0)=f(x_0)\)，设结论对\(n-1\)成立，下面证明结论对\(n\)也成立。
对于：
\[\begin{equation*}
P_n(x)=P_{n-1}(x)+f[x_0,x_1,\dots,x_n]w_n(x)
\end{equation*}\]
因为对任意的\(i=0,1,\dots,n-1\)有\(w_n(x_i)=0\)，所以由归纳假设可知：
\[\begin{equation*}
P_n(x_i)=P_{n-1}(x_i)=f(x_i),\quad i=0,1,\dots,n-1
\end{equation*}\]
下面证明\(P_n(x_n)=f(x_n)\)。
作辅助函数\(R(x)=f(x)-P_{n-1}(x)\)，于是有：
\[\begin{equation*}
\frac{R(x_n)}{w_n(x_n)}=\frac{f(x_n)-P_{n-1}(x_n)}{w_n(x_n)}
\end{equation*}\]
由性质 14.2.2(1)可得：
\[\begin{equation*}
R[x_0,x_1,\dots,x_n]=\sum_{i=0}^{n}\frac{R(x_i)}{(x_i-x_0)(x_i-x_1)\dots(x_i-x_{i-1})(x_i-x_{i+1})\dots(x_i-x_n)}=\frac{R(x_n)}{w_n(x_n)}
\end{equation*}\]
所以：
\[\begin{equation*}
\frac{f(x_n)-P_{n-1}(x_n)}{w_n(x_n)}=R[x_0,x_1,\dots,x_n]
\end{equation*}\]
根据性质 14.2.2(3)可知：
\[\begin{equation*}
R[x_0,x_1,\dots,x_n]=f[x_0,x_1,\dots,x_n]-P_{n-1}[x_0,x_1,\dots,x_n]
\end{equation*}\]
因为\(P_{n-1}\)的次数不超过\(n-1\)，由性质 14.2.2(4)可知\(P_{n-1}[x_0,x_1,\dots,x_n]=0\)，于是有：
\[\begin{equation*}
R[x_0,x_1,\dots,x_n]=f[x_0,x_1,\dots,x_n]
\end{equation*}\]
所以：
\[\begin{equation*}
\frac{f(x_n)-P_{n-1}(x_n)}{w_n(x_n)}=f[x_0,x_1,\dots,x_n]
\end{equation*}\]
即：
\[\begin{equation*}
P_{n-1}(x_n)=f(x_n)-f[x_0,x_1,\dots,x_n]w_n(x_n)
\end{equation*}\]
于是：
\[\begin{equation*}
P_n(x_n)=P_{n-1}(x_n)+f[x_0,x_1,\dots,x_n]w_n(x_n)=f(x_n)
\end{equation*}\]
◻
note 14.2. 根据性质 14.2.3，Newton插值多项式和Lagrange插值多项式是等价的，于是它具有了Lagrange插值多项式的全部性质。既然等价，那为什么要研究它呢？
从构造方式看，Lagrange插值是一次性使用全部节点进行整体构造，而Newton插值具有天然的递推性。当新增插值节点时，Lagrange插值多项式通常需要重新计算，而Newton插值多项式只需增加一个新的均差项即可完成更新，这使其在逐点插值与在线计算中具有明显优势。
