计算方法（四）：插值与拟合_综合

文章目录

插值与拟合
- 插值概念与基础理论
- - 插值问题的提法
  - 插值多项式的存在唯一性
  - 插值余项
- 插值多项式的求法
- - 拉格朗日(Lagrange)型插值多项式
  - 差商与牛顿基本插值多项式
  - 差分与等距结点下的牛顿公式
- 埃尔米特（Hermite）插值
- 分段低次插值
- - 分段线性插值与分段二次插值
  - 三次样条插值
  - - 三斜率（三转角）方程组
    - 三弯矩方程组（M关系式）
- 曲线拟合的最小二乘法
- - 最小二乘解的求法
  - - 线性最小二乘问题的求法
    - 多项式拟合最小二乘法
  - 加权技巧的应用

插值与拟合

插值概念与基础理论

插值问题的提法

给定函数 $f (x)$ 在区间 $[a, b]$ 上的 $n + 1$ 个函数值：
$\begin{array}{c|ccccc}x & x_0 & x_1 & \cdots & x_n\\ \hline f(x) & f(x_0) & f(x_1) & \cdots & f(x_n)\end{array}$
$x_0,x_1,\cdots,x_n$ 互不相同。 $\Phi$ 为给定的某一个函数类。若 $\Phi$ 上有函数 $\varphi(x)$ ，满足
$\varphi(x_i)=f(x_i),i=0,1,2,\cdots,n$
则称 $\varphi(x)$ 为 $f (x)$ 关于结点 $x_0,x_1,\cdots,x_n$ 在 $\Phi$ 上的插值函数， $x_0,x_1,\cdots,x_n$ 称为插值结点， $[a, b]$ 称为插值区间， $f (x)$ 称为被插函数。

根据插值定义，插值函数实际上是一条经过平面上点 $(x_i,f(x_i))_{i=0,1,\cdots,n}$ 的曲线，这条平面曲线函数，就可以作为 $f (x)$ 的逼近函数。

插值函数的存在唯一性：插值函数类 $\Phi$ 为一个函数空间，若插值结点数为 $n + 1$ ，实际上给出了 $n + 1$ 个限制条件，为了保证插值函数的存在唯一性，给出的插值函数空间应是 $n + 1$ 维的，即 $dim\Phi=n+1$ 。

任取 $\Phi$ 上 $n + 1$ 个线性无关函数 $\varphi_0(x),\varphi_1(x),\cdots,\varphi_n(x)$ ，它们可作为 $\Phi$ 的一组基，记为：
$\Phi=span\{\varphi_0(x),\varphi_1(x),\cdots,\varphi_n(x)\}$
于是，任取 $\varphi(x)\in\Phi$ ，则 $\varphi(x)$ 可唯一地表为：
$\varphi(x)=a_0\varphi_0(x)+a_1\varphi_1(x)+\cdots+a_n\varphi_n(x)$
这里 $(a_0,a_1,\cdots,a_n)$ 称之为 $\varphi(x)$ 在基 $\{\varphi_i(x)\}^n_{i=1}$ 下的坐标。

^（*）定理： $\{x_i\}^n_{i=0}$ 为 $[a, b]$ 上 $n + 1$ 个互异点， $\Phi=span\{\varphi_0(x),\varphi_1(x),\cdots,\varphi_n(x)\}$ 为 $n + 1$ 维函数空间，定义在 $[a, b]$ 上的函数 $f (x)$ 关于结点 $\{x_i\}^n_{i=0}$ 在 $\Phi$ 上的插值函数存在且唯一的充要条件为行列式：
$\left|\begin{matrix}\varphi_0(x_0) & \varphi_1(x_0) & \cdots & \varphi_n(x_0)\\\varphi_0(x_1) & \varphi_1(x_1) & \cdots & \varphi_n(x_1)\\&\cdots&\cdots\\\varphi_0(x_{n-1}) & \varphi_1(x_{n-1}) & \cdots & \varphi_n(x_{n-1})\\\varphi_0(x_n) & \varphi_1(x_n) & \cdots & \varphi_n(x_n)\end{matrix}\right|\neq0$

插值多项式的存在唯一性

记 $P_n=\{a_0+a_1x+\cdots+a_nx^n|a_i\in R\}$ ，则 $P_n$ 为一个 $n + 1$ 维的线性空间（ $n$ 次多项式空间）。

若 $\{x_i\}^n_{i=0}$ 为 $[a, b]$ 上互异点， $f (x)$ 为定义在 $[a, b]$ 上的函数，若有 $P_n(x)\in P_n$ ，满足 $P_n(x_i)=f(x_i),i=0,1,\cdots,n$ ，则称 $P_n(x)$ 为 $f (x)$ 关于结点 $\{x_i\}^n_{i=0}$ 的 $n$ 次插值多项式。

定理1： $f (x)$ 关于 $n + 1$ 个互异结点 $\{x_i\}^n_{i=0}$ 的 $n$ 次插值多项式存在且唯一。

证明：设插值多项式： $P_n(x)=a_0+a_1x+\cdots+a_nx^n$ ，满足 $a_0+a_1x_i+\cdots+a_nx_i^n=f(x_i),i=0,1,\cdots,n$ ，而
$D=\left|\begin{matrix}1&x_0&x_0^2&\cdots&x_0^n\\1&x_1&x_1^2&\cdots&x_1^n\\\vdots&\vdots&\vdots&&\vdots\\1&x_n&x_n^2&\cdots&x_n^n\end{matrix}\right|=\prod_{n\geq i>j\geq0}(x_i-x_j)\neq0$
由克莱姆法则得 $a_0,a_1,\cdots,a_n$ 存在唯一，即 $P_n$ 上存在且唯一的有 $P_n(x)$ ，满足 $P_n(x_i)=f(x_i),i=0,1,\cdots,n$ 。

同时， $n$ 次插值多项式 $P (x)$ 可表示为 $P_n(x)=a_0+a_1x+\cdots+a_nx^n$ ，其中 $a_i=\frac{D_i}{D},i=0,1,2,\cdots,n$ 。
$D_i=\left|\begin{matrix}1&x_0&\cdots&x_0^{i-1}&f(x_0)&x_0^{i+1}&\cdots&x_0^n\\1&x_1&\cdots&x_1^{i-1}&f(x_1)&x_1^{i+1}&\cdots&x_1^n\\&&&\cdots&\cdots\\1&x_n&\cdots&x_n^{i-1}&f(x_n)&x_n^{i+1}&\cdots&x_n^n\end{matrix}\right|$

插值余项

$R_n(x)=f(x)-P_n(x)$ 称为插值余项（或称误差）。

定理2：若 $f\in C^{n+1}[a,b]$ ，互异点 $\{x_i\}^n_{i=0}\subset[a,b]$ ，则 $f (x)$ 以 $\{x_i\}^n_{i=0}$ 为插值结点的 $n$ 次插值多项式余项：
$R_n(x)=\frac{f^{(n+1)}(\xi)}{(n+1)!}(x-x_0)(x-x_1)\cdots(x-x_n)\\其中：min\{x_0,x_1,\cdots,x_n,x\}\leq\xi=\xi(x)\leq max\{x_0,x_1,\cdots,x_n,x\}$
推论： 若 $f(x)\in C^{(n+1)}[a,b]$ ，且 $|f^{(n+1)}(x)|\leq M_{n+1}(a\leq x\leq b)$ ，则 $f (x)$ 以 $\{x_i\}^n_{i=0}$ 为插值结点的 $n$ 次插值多项式余项
$|R_n(x)|\leq\frac{M_{n+1}}{(n+1)!}|\omega_{n+1}(x)|$
其中： $\omega_{n+1}(x)=\prod^n_{i=0}(x-x_i)$

注：若插值点 $x$ 位于插值区间 $[min_{1\leq i\leq n}x_i,max_{1\leq i\leq n}x_i]$ 内，则该插值过程称为内插，否则称为外插。一般情况下，内插效果要比外插好一点，所以，插值结点尽可能选取在插值区间内。

插值多项式的求法

拉格朗日(Lagrange)型插值多项式

对于给定的 $n + 1$ 个互异结点 $\{x_i\}^n_{i=0}$ ，如果能找到 $P_n$ 上 $n + 1$ 个多项式 $\{l_i(x)\}^n_{i=0}$ ，满足
$l_i(x_j)=\delta_{ij}=\begin{cases}1,i=j\\0,i\neq j\end{cases},i,j=0,1,\cdots,n$
那么 $L_n(x)=\sum^n_{i=0}l_i(x)f(x_i)$ 就是 $f (x)$ 关于结点 $\{x_i\}^n_{i=0}$ 的 $n$ 次插值多项式。其中， $\{l_i(x)\}^n_{i=0}\subset P_n$ ，有 $\sum^n_{i=0}l_i(x)f(x_i)\in P_n$ ，且有
$L_n(x_k)=\sum^n_{i=0}l_i(x_k)f(x_i)=f(x_k),k=0,1,\cdots,n$
$l_i(x)$ 的构造： $l_i(x_j)=0(j\neq i)$ ：
$l_i(x)=\prod^n_{j=0,j\neq i}\frac{x-x_j}{x_i-x_j}=\frac{(x-x_0)\cdots(x-x_{i-1})(x-x_{i+1})\cdots(x-x_n)}{(x_i-x_0)\cdots(x_i-x_{i-1})(x_i-x_{i+1})\cdots(x_i-x_n)}$
$\{l_i(x)\}^n_{i=0}$ 是一组线性无关的函数，可作为 $P_n$ 的一组基，称为关于结点 $\{x_i\}^n_{i=0}$ 的Lagrange基，其插值多项式称为Lagrange型插值多项式，记为 $L_n(x,f)$ 或 $L_n(x)$ ，即
$L_n(x)=\sum^n_{i=0}l_i(x)f(x_i)=\sum^n_{i=0}(\prod^n_{j=0,j\neq i}\frac{x-x_j}{x_i-x_j})f(x_i)$
记 $\omega_{n+1}(x)=(x-x_0)(x-x_1)\cdots(x-x_n),\omega'_{n+1}(x_i)=\prod^n_{j=0,j\neq i}(x_i-x_j)$ ，得
$l_i(x)=\frac{\omega_{n+1}(x)}{(x-x_i)\omega'_{n+1}(x_i)}\\L_n(x)=\sum^n_{i=0}\frac{\omega_{n+1}(x)}{(x-x_i)\omega'_{n+1}(x_i)}f(x_i)$
当 $n = 1$ 时，可得 $f (x)$ 关于 $x_0,x_1$ 的线性插值多项式的Lagrange型式：
$L_1(x)=\frac{x-x_1}{x_0-x_1}f(x_0)+\frac{x-x_0}{x_1-x_0}f(x_1)$
当 $n = 2$ 时，可得 $f (x)$ 关于 $x_0,x_1,x_2$ 的线性插值多项式的Lagrange型式：
$L_2(x)=l_0(x)f(x_0)+l_1(x)f(x_1)+l_2f(x_2)\\=\frac{(x-x_1)(x-x_2)}{(x_0-x_1)(x_0-x_2)}f(x_0)+\frac{(x-x_0)(x-x_2)}{(x_1-x_0)(x_1-x_2)}f(x_1)+\frac{(x-x_0)(x-x_1)}{(x_2-x_0)(x_2-x_1)}f(x_2)$

三点插值又称抛物插值。

误差的事后估计方法： 定理 2 给出了当被插函数充分光滑时的插值误差表达式，推论给出了误差的界。但在实际计算中，涉及到高价导数，很难给出较精确的估计，所以常用误差的事后估计。

记 $L_n(x)$ 为 $f (x)$ 以 $x_0,x_1，\cdots,x_n$ 为结点的插值多项式，对确定的 $x$ ，我们需要对误差 $f(x)-L_n(x)$ 做出估计。为此，另取一个结点 $x_{n+1}$ ，记 $L^{(1)}_n(x)$ 为 $f (x)$ 以 $x_1,x_2,\cdots,x_n,x_{n+1}$ 为结点的插值多项式，由定理2，可得到：
$f(x)-L_n(x)=\frac{f^{(n+1)}(\xi)}{(n+1)!}(x-x_0)(x-x_1)\cdots(x-x_n)\\f(x)-L^{(1)}_n(x)=\frac{f^{(n+1)}(\xi_2)}{(n+1)!}(x-x_1)(x-x_2)\cdots(x-x_n)(x-x_{n+1})$
若 $f^{(n+1)}(x)$ 在插值区间上变化不大时，则：
$\frac{f(x)-L_n(x)}{f(x)-L^{(1)}_n(x)}\approx\frac{x-x_0}{x-x_{n+1}}\\(x-x_{n+1})(f(x)-L_n(x))\approx(x-x_0)(f(x)-L^{(1)}_n(x))\\f(x)\approx\frac{x-x_{n+1}}{x_0-x_{n+1}}L_n(x)+\frac{x-x_0}{x_{n+1}-x_0}L^{(1)}_n(x)\\即：f(x)-L_n(x)\approx\frac{x-x_0}{x_0-x_{n+1}}(L_n(x)-L^{(1)}_n(x))$
上式较好地给出了插值误差的实际估计。

差商与牛顿基本插值多项式

对于给定的 $n + 1$ 个结点 $x_0,x_1,\cdots,x_n$ ，考虑 $n$ 次多项式： $N_n(x)=a_0+a_1(x-x_0)+a_2(x-x_0)(x-x_1)+\cdots+a_n(x-x_0)(x-x_1)\cdots(x-x_{n-1})$ 满足插值条件： $N_n(x_i)=f(x_i)=y_i,i=0,1,\cdots,n$ ，称 $N_n(x)$ 是以 $x_0,x_1,\cdots,x_n$ 为结点的 $n$ 次牛顿型插值多项式。

定义1：设函数 $f (x)$ 在点 $x_0,x_1,x_2,\cdots$ 上的值依次为 $f(x_0),f(x_1),f(x_2),\cdots$ ，则称
$f[x_i,x_j]=\frac{f(x_j)-f(x_i)}{x_j-x_i}$
为 $f (x)$ 在 $x_i,x_i$ 处的一阶差商。称
$f[x_i,x_j,x_k]=\frac{f[x_j,x_k]-f[x_i,x_j]}{x_k-x_i}$
为 $f (x)$ 在 $x_i,x_j,x_k$ 处的二阶差商。一般地，称 $m ? 1$ 阶差商的差商：
$f[x_{i0},x_{i1},\cdots,x_{im}]=\frac{f[x_{i1},\cdots,x_{im}]-f[x_{i0},\cdots,x_{im-1}]}{x_{im}-x_{i0}}$
为 $f (x)$ 在 $x_{i0},x_{i1},\cdots,x_{im}$ 处的 $m$ 阶差商。

特别的，规定零阶差商为： $f[x_i]=f(x_i)$ 。

通过归纳法， $m$ 阶差商可表示成 $f(x_0),f(x_1),\cdots,f(x_m)$ 的线性组合：
$f[x_0,x_1,\cdots,x_m]=\sum_{j=0}^m\frac{f(x_j)}{(x_j-x_0)\cdots(x_j-x_{j-1})(x_j-x_{j+1})\cdots(x_j-x_m)}$

差商具有对称性：任意调换结点的次序，不影响差商的值。 例如：
$f[x_0,x_1,x_2]=f[x_1,x_2,x_0]=f[x_1,x_0,x_2]$
由插值条件 $N_n(x_i)=f(x_i)$ ，可得
$N_n(x_0)=a_0=f(x_0)\rightarrow a_0=f(x_0)\\N_n(x_1)=a_0+a_1(x_1-x_0)=f(x_1)\rightarrow a_1=\frac{f(x_1)-f(x_0)}{x_1-x_0}=f[x_0,x_1]\\N_n(x_2)=a_0+a_1(x_2-x_0)+a_2(x_2-x_0)(x_2-x_1)=f(x_2)\rightarrow a_2=\frac{f[x_0,x_2]-f[x_0,x_1]}{x_2-x_0}=f[x_0,x_1,x_2]$
由归纳法可得：
$a_k=f[x_0,x_1,\cdots,x_k](k=0,1,\cdots,n)$
以 $x_0,x_1,\cdots,x_n$ 为结点的 $n$ 次牛顿型插值多项式：
$N_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,\cdots,x_n](x-x_0)(x-x_1)\cdots(x-x_{n-1})$
当新增加一个结点 $x_{n+1}$ 时：
$N_{n+1}(x)=N_n(x)+f[x_0,x_1,\cdots,x_n,x_{n+1}](x-x_0)(x-x_1)\cdots(x-x_{n-1})(x-x_n)$
插值多项式的误差(差商形式)表示：
$f(x)\equiv f(x_0)+f[x_0,x_1](x-x_0)+\cdots+f[x_0,x_1,\cdots,x_n](x-x_0)\cdots(x-x_{n-1})+f[x_0,x_1,\cdots,x_n,x](x-x_0)\cdots(x-x_n)\\=N_n(x)+f[x_0,x_1,\cdots,x_n,x](x-x_0)\cdots(x-x_n)$
若 $f(x)\in C^{n+1}[a,b]$ ，则有
$R_n(x)=f(x)-N_n(x)=f[x_0,x_1,\cdots,x_n,x](x-x_0)\cdots(x-x_n)\\f[x_0,x_1,\cdots,x_n,x]=\frac{f^{(n+1)}(\xi)}{(n+1)!}$
一般地，若 $f(x)\in C^{n+1}[a,b]$ ，则存在 $\xi\in(a,b)$ ，使得
$f[x_0,x_1,\cdots,x_n]=\frac{f^{(n)}(\xi)}{n!}$

差分与等距结点下的牛顿公式

设函数 $f (x)$ 在等距结点 $x_k=x_0+kh(k=0,1,2,\cdots)$ 上的值 $f(x_k)$ 已知，步长 $h$ 为常数。

定义2：函数 $y = f (x)$ 在 $x_k$ 处以 $h$ 为步长的一阶向前差分与二阶向前差分：
$\Delta y_k=\Delta f(x_k)=f(x_{k+1})-f(x_k)\\\Delta^2y_k=\Delta^2f(x_k)=\Delta(\Delta f(x_k))=\Delta f(x_{k+1})-\Delta f(x_k)=f(x_{k+2})-2f(x_{k+1})+f(x_k)$
一般性， $m$ 阶向前差分：
$\Delta^my_k=\Delta^mf(x_k)=\Delta(\Delta^{m-1}f(x_k))=\Delta^{m-1}f(x_{k+1})-\Delta^{m-1}f(x_k)$

定义3：函数 $y = f (x)$ 在 $x_k$ 处以 $h$ 为步长的一阶向后差分与二阶向后差分：
$\triangledown y_k=\triangledown f(x_k)=f(x_k)-f(x_{k-1})\\\triangledown^2y_k=\triangledown^2f(x_k)=\triangledown(\triangledown f(x_k))=\triangledown f(x_k)- \triangledown f(x_{k-1})=f(x_k)-2f(x_{k-1})+f(x_{k-2})$
一般性， $m$ 阶向后差分：
$\triangledown^my_k=\triangledown^mf(x_k)=\triangledown(\triangledown^{m-1}f(x_k))=\triangledown^{m-1}f(x_k)-\triangledown^{m-1}f(x_{k-1})$

差商与差分关系：
$f[x_0,x_1,\cdots,x_m]=\frac{\Delta^mf(x_0)}{m!h^m}\\f[x_n,x_{n-1},\cdots,x_{n-m}]=\frac{\triangledown^mf(x_n)}{m!h^m}$

等距结点的Newton型多项式插值的差分形式：引入变量 $t$ ，设 $x=x_0+th$ （有 $x-x_i=(t-i)h$ ），则等距结点的Newton插值公式：
$N_n(x_0+th)=f(x_0)+t\Delta f(x_0)+\frac{t(t-1)}{2!}\Delta^2f(x_0)+\cdots+\frac{t(t-1)\cdots(t-n+1)}{n!}\Delta^nf(x_0)$
若 $f(x)\in C^{n+1}[a,b]$ ，则插值误差可表示为
$R_n(x)=R_n(x_0+th)=\frac{t(t-1)\cdots(t-n)}{(n+1)!}h^{n+1}f^{(n+1)}(\zeta),\zeta\in(x_0,x_n)$
(1)牛顿表初公式或牛顿向前差分公式：若 $x$ 在 $x_0$ 附近，选取的牛顿型插值公式为
$N_n(x_0+th)=f(x_0)+t\Delta f(x_0)+\frac{t(t-1)}{2!}\Delta^2f(x_0)+\cdots+\frac{t(t-1)\cdots(t-n+1)}{n!}\Delta^nf(x_0)$
(2)牛顿表末公式或牛顿向后差分公式：若 $x$ 在 $x_n$ 附近，选取的牛顿型插值公式为
$N_n(x)=N_n(x_n+th)=f(x_n)+f[x_n,x_{n-1}](x-x_n)+f[x_n,x_{n-1},x_{n-2}](x-x_n)(x-x_{n-1})\\+f[x_n,x_{n-1},\cdots,x_0](x-x_n)(x-x_{n-1})\cdots(x-x_1)\\=f(x_n)+t\triangledown f(x_n)+\frac{t(t+1)}{2!}\triangledown^2f(x_n)+\cdots+\frac{t(t+1)\cdots(t+n-1)}{n!}\triangledown^nf(x_n)\\其中，x_k=x_n-(n-k)h\\R_n(x)=R_n(x_n+th)=\frac{t(t+1)\cdots(t+n)}{(n+1)!}h^{n+1}f^{(n+1)}(\zeta),\zeta\in(x_0,x_n)$
(3)牛顿表中插值公式：

定义4： $\delta y_k=f(x_k+\frac{h}{2})-f(x_k-\frac{h}{2})=y_{k+\frac{1}{2}}-y_{k-\frac{1}{2}}$ 称为一阶中心差分。

$\delta^my_k=\delta^{m-1}y_{k+\frac{1}{2}}-\delta^{m-1}y_{k-\frac{1}{2}}$ 称为 $m$ 阶中心差分。

埃尔米特（Hermite）插值

插值在给定的结点处，不但要求插值多项式的函数值与被插函数的函数值相同，同时还要求在结点处，插值多项式的一阶直至指定阶的导数值也与被插函数的相应阶导数值相等。

设 $f (x)$ 为 $[a, b]$ 上充分光滑函数，对给定的插值结点 $\{x_i\}^n_{i=0}$ 及相应的重数标号 $\{m_i\}^n_{i=0}$ ，当 $\sum_{i=0}^nm_i=N+1$ 时，若有 $H(x)\in P_n$ 满足：
$H^{(l)}(x_i)=f^{(l)}(x_i),l=0,1,\cdots,m_i-1,i=0,1,\cdots,n$
则称 $H (x)$ 为 $f (x)$ 关于结点 $\{x_i\}^n_{i=0}$ 及重数标号 $\{m_i\}^n_{i=0}$ 的埃尔米特插值多项式。

二重（ $m_i=2$ ）： $f(x)\in C^2[a,b]$ ，若有 $H_{2n+1}(x_i)=f(x_i),H'_{2n+1}(x_i)=f'(x_i),i=0,1,\cdots,n$ ，称 $H_{2n+1}(x)$ 为 $f (x)$ 关于结点 $\{x_i\}^n_{i=0}$ 的二重埃尔米特插值多项式，其存在且唯一（由克拉默法则易得）。

基函数构造法：
$H_{2n+1}(x)=\sum_{i=0}^nA_i(x)f(x_i)+\sum_{i=0}^nB_i(x)f'(x_i)$
在 $P_{2n+1}$ 上构造 $2 n + 2$ 个基函数 $\{A_i(x),B_i(x)\}^n_{i=0}$ ，分别满足
$\begin{cases}A_i(x_j)=\delta_{ij}\\A'_i(x_j)=0\end{cases},j=0,1,\cdots,n,i=0,1,\cdots,n\\\begin{cases}B_i(x_j)=0\\B'_i(x_j)=\delta_{ij}\end{cases},j=0,1,\cdots,n,i=0,1,\cdots,n$
可得 $x_0,x_1,\cdots,x_{i-1},x_{i+1},\cdots,x_n$ 为 $A_i(x)$ 的二重零点， $A_i(x)\in P_{2n+1}$ ，有：
$A_i(x)=(a_ix+b_i)[(x-x_0)^2(x-x_1)^2\cdots(x-x_{i-1})^2(x-x_{i+1})^2\cdots(x-x_n)^2]\\也可设:A_i(x)=[a_i(x-x_i)+b_i]\prod_{j=0,j\neq i}^n(x-x_j)^2$
由 $A_i(x_i)=1,A'_i(x_i)=0$ 得
$b_i=1/\prod_{j=0,j\neq i}^n(x_i-x_j)^2\\A_i(x)=[1-2(x-x_i)\sum_{j=0,j\neq i}^n\frac{1}{x_i-x_j}]l_i^2(x)$
其中， $l_i(x)$ 为关于点 $\{x_i\}^n_{i=0}$ 的Lagrange 基函数。用类似的方法，可得到
$B_i(x)=(x-x_i)l_i^2(x)\\H_{2n+1}(x)=\sum_{i=0}^nA_i(x)f(x_i)+\sum_{i=0}^nB_i(x)f'(x_i)$
二重埃尔米特插值多项式的误差分析：若 $f\in C^{2n+2}[a,b]$ ，则 $f (x)$ 关于 $[a, b]$ 上结点 $\{x_i\}^n_{i=0}$ 的二重埃尔米特插值多项式误差为
$f(x)-H_{2n+1}(x)=\frac{f^{(2n+2)}(\xi)}{(2n+2)!}\omega^2_{n+1}(x)\\min\{x_0,x_1,\cdots,x_n,x\}\leq\xi=\xi(x)\leq max\{x_0,x_1,\cdots,x_n,x\}$
具有两个结点 $x_0,x_1$ 的二重埃尔米特插值为一个三次多项式，基函数分别为：
$A_0(x)=[1-2\frac{x-x_0}{x_0-x_1}](\frac{x-x_1}{x_0-x_1})^2\\A_1(x)=[1-2\frac{x-x_1}{x_1-x_0}](\frac{x-x_1}{x_0-x_1})^2\\B_0(x)=(x-x_0)(\frac{x-x_1}{x_0-x_1})^2\\B_1(x)=(x-x_1)(\frac{x-x_1}{x_0-x_1})^2$
所以，二重埃尔米特插值多项式为：
$H_3(x)=A_0(x)f(x_0)+A_1(x)f(x_1)+B_0(x)f'(x_0)+B_1(x)f'(x_1)$
若 $f\in C^4[a,b]$ ，则有误差表达式：
$R_3(x)=f(x)-H_3(x)=\frac{f^{(4)}(\xi)}{4!}(x-x_0)^2(x-x_1)^2$

一般形式的Hermite插值问题：求一个次数不大于 $n + r + 1$ 的代数多项式 $H (x)$ ，满足：
$H(x_i)=f(x_i),i=0,1,2,\cdots,n\\H'(x_i)=f'(x_i),i=0,1,2,\cdots,r(r\leq n)$
令 $H(x)=\sum_{k=0}^nh_k(x)f(x_k)+\sum_{k=0}^r\bar{h}_k(x)f'(x_k)$ ，其中 $h_k(x)、\bar{h}_k(x)$ 都是 $n + r + 1$ 次待定多项式，并且满足：
$h_k(x_i)=\begin{cases}1\ \ i=k\\0\ \ i\neq k\end{cases}\ \ \ \ i,k=0,1,\cdots,n\\h'_k(x_i)=0,\ \ k=0,1,\cdots,n;i=0,1,\cdots,r\\\bar{h}_k'(x_i)=\begin{cases}1\ \ i=k\\0\ \ i\neq k\end{cases}\ \ \ \ i,k=0,1,\cdots,r\\\bar{h}_k(x_i)=0,\ \ k=0,1,\cdots,r;i=0,1,\cdots,n$
1、求解 $h_k(x)(k=0,1,\cdots,n)$ ：由条件可得， $x_i(i=0,1,\cdots,r;i\neq k)$ 是 $h_k(x)$ 的二重零点， $x_i(i=r+1,r+2,\cdots,n;i\neq k)$ 是 $h_k(x)$ 的零点。

当 $0\leq k\leq r$ 时：
$h_k(x)=(Ax+B)(x-x_0)^2\cdots(x-x_{k-1})^2(x-x_{k+1})^2\cdots(x-x_r)^2(x-x_{r+1})\cdots(x-x_n)\\=(Ax+B)\prod_{i=0,i\neq k}^r(x-x_i)^2\prod_{i=r+1}^n(x-x_i)$

又由 $h_k(x_k)=1,h_k'(x_k)=0$ 得：
$(Ax_k+B)\prod_{i=0,i\neq k}^r(x_k-x_i)^2\prod_{i=r+1}^n(x_k-x_i)=1\\A\prod_{i=0\\i\neq k}^r(x_k-x_i)^2\prod_{i=r+1}^n(x_k-x_i)+2(Ax_k+B)\sum_{j=0}^r(x_k-x_j)\prod_{i=0\\i\neq j\\i\neq k}^r(x_k-x_i)^2\prod_{i=r+1}^n(x_k-x_i)+(Ax_k+B)\sum_{j=r+1}^n\prod_{i=0\\i\neq k}^r(x_k-x_i)^2\prod_{i=r+1\\i\neq j}^n(x_k-x_i)=0$
解得
$A=-\frac{2\sum_{j=0}^r\frac{1}{x_k-x_j}+\sum_{j=r+1}^n\frac{1}{x_k-x_j}}{\prod_{i=0\\i\neq k}^r(x_k-x_i)^2\prod_{i=r+1}^n(x_k-x_i)}\\B=-\frac{1-Ax_k}{\prod_{i=0\\i\neq k}^r(x_k-x_i)^2\prod_{i=r+1}^n(x_k-x_i)}\\h_k(x)=\{1-(x-x_k)[l'_{kn}(x_k)+l'_{kr}(x_k)]\}l_{kn}(x)l_{kr}(x),k=0,1,\cdots,r\\其中：l_{kn}(x)=\prod_{i=0\\i\neq k}^n\frac{x-x_i}{x_k-x_i}\\l_{kr}(x)=\prod_{i=0\\i\neq k}^r\frac{x-x_i}{x_k-x_i}\\l'_{kn}(x_k)=\prod_{i=0\\i\neq k}^n\frac{1}{x_k-x_i}\\l'_{kr}(x_k)=\prod_{i=0\\i\neq k}^r\frac{1}{x_k-x_i}$